La progettazione per composizione
Da Hacknowledge.
Indice |
[modifica] La progettazione per composizione
A volte la progettazione di una macchina risulta più agevole se fatta mediante la composizione di macchine già progettate in un precedente progetto, la composizione tra macchine può effettuarsi sia per le macchine combinatorie che per quelle sequenziali. Le macchine usate per la composizione si dicono macchine componenti. E’ utile un attenta valutazione del numero di componenti che si andrà ad impiegare qualora il progetto sia effettuato per composizione; in altre parole è buona norma considerare la progettazione della macchina seguendo anche il suo tipico schema fin qui adottato e passando quindi per le varie fasi di progettazione (un analisi quantitativa è opportuna per stabilire quale delle due strade intraprendere, ovviamente è preferibile una progettazione che impiega il minor numero di componenti possibili, mentre a parità di componente sarebbe più idonea una progettazione per composizione, in tal caso la scelta spetta comunque al progettista). Un parametro importante da non sottovalutare è la velocità di elaborazione della macchina, componendo più macchine i tempi di ritardo della macchina complessiva saranno influenzati dai rispettivi ritardi delle macchine componenti. E’ allora necessario fare un grosso sforzo iniziale per definire in modo chiaro gli obiettivi del progetto e le specifiche facendo attenzione alle limitazione che vengono imposte al progettista. Ricordarete, infine, che allo stesso problema esistono spesso molte soluzioni!
[modifica] Composizione di macchine combinatorie
La metodologia di composizione per le macchine combinatorie prevede due connessioni fondamentali: la composizione serie e la composizione parallelo. Nella composizione serie le macchine vengono poste una dietro l’altra e l’uscita di una è l’ingresso della successiva, in particolare per due sole macchine combinatorie la connessione serie prevede il seguente schema:
La connessione duale alla connessione serie è invece la connessione parallelo in cui le macchine operano in modo indipendente e producono ciascuna una parte dell’ingresso. Nella composizione parallelo di macchine combinatorie è spesso necessaria una ricombinazione delle uscite, ciò richiede la progettazione di un’altra macchina combinatoria che presi in ingresso le uscite delle macchine componenti produca le uscite della macchina composizionale. Con riferimento a due sole macchine combinatorie, la connessione parallelo di macchine combinatorie prevede il seguente schema:
[modifica] Composizione per semiselezione di decodificatori
I decodificatori costituiscono insieme ai multiplexer le macchine combinatorie più usate in fase di progettazione. A volte può capitare di effettuare una composizione anche per queste macchine. Nella configurazione per semiselezione si utilizzano 2 decodificatori di metà ampiezza ed una porta AND per ciascuna uscita. Ogni uscita del decoder è intrecciata con tutte le altre uscite dell’altro decoder mediante una porta AND. Se ad esempio facciamo riferimento a 2 decodificatori da 2 ingressi e 4 uscite, mediante questo tipo di composizione si realizzerà un nuovo decodificatore da 4 ingressi e 16 uscite come mostrato in figura:
[modifica] Composizione ad albero di decodificatori
La composizione di decodificatori può avvenire anche secondo una struttura nota come struttura ad albero dove per realizzare un decodificatore da n uscite e log2n ingressi, utilizzando decodificatori da:
- n uscite;
- log2m ingressi;
Si impiegano un numero di decoder pari ad:
- 1 + m + m2 + mk;
Dove k identifica il numero di livelli dell’albero.
Ad esempio:
Nella combinazione di più decoder secondo la struttura ad albero, come è mostrato in figura, le prime linee sono utili a selezionare il decoder da attivare (in figura a0 ed a1 sono le linee che ci permettono di selezionare uno dei quattro decoder), mentre le restanti linee servono invece a selezionare una delle linee in uscita del decoder attivato (in figura a2 ed a3 permettono di selezionare le linee in uscita che vanno da 0 a 3).
[modifica] Composizione di multiplexer
Altra macchina combinatoria largamente usata è il multiplexer. Le considerazioni fatte per le macchine combinatorie a proposito della progettazione si estendono anche per questa macchina. E’ possibile realizzare un multiplexer da 16 ingressi con 5 multiplexer da 4 ingressi, adottando una struttura ad albero.(in realtà lo schema si presenta come un albero capovolto e può essere visto anche come un ramo dalle tante ramificazioni). Due degli stati di selezione permettono di scegliere il multiplexer da leggere o da abilitare, con 2 bit possiamo abilitare 4 multiplexer le cui uscite sono raccolte in ingresso da un altro multiplexer. Altri due bit permettono per ciascun multiplexer di selezionare una delle sue quattro linee come ingresso:
Oppure, è possibile realizzare un Multiplexer composto a 16 ingressi con 2 multiplexer da 8. In tal caso è opportuno realizzare una rete combinatoria che ri-elabora l’uscita.
La rete combinatoria avrà 3 ingressi con:
- m0, m1 e c3;
- 1 bit di uscita y;
tale che:
- y=m0 se c3=0;
- y=m1 se c3=1;
Risulta:
- y=m0 • c3 + m1 • c3;
Una volta che un dispositivo sia stato costruito, esso può fungere da componente di sistemi più complessi o comunque da “base” per una sua evoluzione verso dispositivi più sofisticati. Nella connessione in parallelo è consentita l’esecuzione contemporanea di più operazioni. Le linee di ingresso vengono fornite a tutte le macchine connesse in parallelo ed i tempi di elaborazione dipendano soltanto dalla macchina più lenta, a differenza della connessione in serie in cui i tempi di elaborazione sono più alti in quanto il tempo di elaborazione è la somma dei tempi di elaborazione di tutte le singole macchine!
[modifica] Composizioni di macchine sequenziali
Una macchina sequenziale può essere realizzata mediante apposito collegamento di due o più macchine sequenziali, con particolare riferimento a due sole macchine sequenziali è allora possibile realizzare una composizione serie ed una parallela. Nella connessione serie lo stato di una viene comunicata all’altra, infine gli stati delle due macchine vengono composti per ricavarne le uscite, quello che segue è uno schema tipico di una connessione serie tra due macchine sequenziali:
Nella connessione parallela, non c’è scambio di stato tra le due macchine, ma vi è soltanto la composizione finale degli stati (notare infatti l’assenza della linea di connessione che permette la comunicazione degli stati).
[modifica] Riconoscitore 8421 mediante composizione
La progettazione di un riconoscitore 8421 è stata già affrontata quando abbiamo introdotto la progettazione delle macchine sequenziali. La progettazione che effettueremo sarà basata sulla metodologia di composizione delle macchine, in particolare si farà uso di un contatore modulo 4. Un riconoscitore 8421 è una macchina che riceve in ingresso un flusso di bit ed emette un segnale alto ogni 4 bit,se questi corrispondono ad un numero valido della sequenza 0,1,2,3…9. I valori di input sono:
- le sequenze di bit, gli ingressi possono essere 0 o 1;
I valori di output sono:
- 0 se ho un valore valido o una sequenza incompleta;
- 1 se ho un valore valido nella codifica 8421;
La progettazione dell’automa è la stessa di quella già affrontata in alcune lezioni precedenti, per comodità riportiamo di seguito il grafo dell’automa e la sua tabella di transizione per gli stati:
L’automa può essere visto, mediante una linea separatrice immaginaria, come uno spaccato di due blocchi di macchina, lo spaccato a sinistra sarà denotato con la lettera A e lo spaccato a destra sarà denotato con la lettera B. La parte A dell’automa (quella a sinistra) si compone degli stati S0,S1,S2 ed S4 mentre la parte B (quella a destra) si compone degli stati S3 ed S5. La prima parte procede in maniera autonoma mentre la seconda evolve in funzione della prima.
Per realizzare l’automa si dovranno allora realizzare due macchine: la macchina 1 e la macchina 2. La macchina 1 ha un comportamento noto, essa è infatti riconducibile ad un contatore modulo 4, ad ogni passo la macchina cambia stato passando in quello successivo,infine dall’ultimo stato passa al primo come un comune contatore. La macchina 1 permette all’automa di spostarsi in verticale ed occupare quindi uno degli stati della macchina (livelli). La macchina 2 invece permette all’automa di spostarsi in orizzontale, il suo comportamento non è riconducibile a macchine note e deve pertanto essere elaborato con i metodi tradizionali. Gli ingressi della macchina sono:
- lo stato della macchina 1;
- l’ingresso della macchina completa;
L’uscita è lo stato. L’automa che realizza la macchina 2 è:
La lettura dell’automa è il seguente, occorre ricordare che A è la parte di macchina a sinistra mentre B è la parte di macchina a destra. Ci troviamo in A (parte o macchina sinistra), proseguendo per i livelli a,b,c e d si considerano i diversi possibili ingressi: con gli ingressi a,1 ed a,0 la macchina procede in verticale rimanendo nella parte sinistra dell’automa; per l’ingresso b,1 la macchina procede in verticale e rimane quindi in A mentre per b,0 la macchina si sposta a destra portandosi in B; per gli ingressi c,0 e c,1 la macchina si porta in uno stato posto a sinistra dell’automa rimanendo quindi in A; per l’ingresso d,1 la macchina si porta in uno stato a sinistra della machina e quindi continua rimanere in A, per l’ingresso d,0 la macchina si porta sempre in a (stato posto a sinistra dell’automa) ma questa volta con un valore dell’uscita alto. Supponiamo adesso il caso in cui ci si trova in B, ossia in uno stato a destra dell’automa: per gli ingressi dei livelli a e b (quindi a,0 a,1 b,0 ed b,1) la parte B non è interessata (don’t care); per l’ingresso c,1 la macch9ina si porta in A mentre per l’ingresso c,0 la macchina si porta in B; per gli ingressi d,1 e d,0 la macchina si porta in A con uscita 1. La tabella degli stati che riassume quanto detto è:
Occorre allora svolgere il progetto della macchina 2 che ha due soli stati: essa entra nello stato B solo quando la macchina 1 è nello stato B e l’ingresso è 0; ritorna poi in A se la macchina 1 è in C e l’ingresso è 1 e tutte le volte che l’ingresso è 1. Gli stati vengono così codificati:
- A = 0;
- B = 1;
ed i valori che permettono di scegliere la macchine A o quella B (che chiamiamo valori set e di reset) sono:
- Set=B*NOT(I);
- Reset=CI+D;
Il tipo di composizione che andiamo ad effettuare è di tipo seriale, la macchina M2 evolve in funzione di M1 poiché ha come ingresso proprio uno stato di M1. Per l’uscita: l’uscita è alta quando la macchina 1 è nello stato d e l’ingresso è 0, oppure quando la macchina 2 è nello stato d e l’ingresso è 0 od 1:
- z=D*NOT(I)+d;
