Progettazione di una rete combinatoria - approccio gerarchico e porte NAND-NOR

Finora abbiamo visto gli strumenti: porte, algebra di Boole, mappe di Karnaugh. Qui si usano per progettare un circuito dalla specifica al diagramma logico.

Combinatorio e sequenziale

Si introduce la variabile tempo e si considera la situazione stazionaria di ingressi e uscite a un istante $t$.

Definizione (circuito combinatorio e sequenziale)

• Un circuito è combinatorio se le sue uscite dipendono solo dal valore presente degli ingressi, non dai valori assunti in passato. Non ha memoria; è formato da porte logiche interconnesse senza percorsi di retroazione (dall'uscita all'ingresso): è un circuito aciclico.
• Un circuito è sequenziale se le uscite dipendono dagli ingressi presenti e dalla loro storia (lo stato). Contiene blocchi combinatori ed elementi di memoria, con almeno un percorso di retroazione che riporta lo stato in ingresso (Elementi di memoria - latch SR, latch D e flip-flop DUn circuito sequenziale ha uscite che dipendono da ingressi e stato (memoria); è un circuito combinatorio con elementi di memoria in retroazione; stato presente = uscite dei FF, stato futuro = ingressi dei FF. Sincrono (clock) o asincrono. Latch SR (NOR): S=1,R=0 set; S=0,R=1 reset; 00 memoria; 11 proibito. Latch D: C=1 trasparente (Q=D), C=0 memoria, sensibile al livello. Flip-flop D edge-triggered = due latch D in cascata (master-slave) con clock opposti: cambia solo sul fronte attivo e non è trasparente. Si assume D flip-flop positive-edge-triggered.Elementi di memoria - latch SR, latch D e flip-flop D →).

Esempio. Un half adder con ingressi $(1,1)$ dà sempre $S=0$, $C=1$ (combinatorio); un contatore con lo stesso ingresso può dare uscite diverse a seconda dello stato (sequenziale).

Come distinguerli da una sequenza di ingressi e uscite. Un sistema con ingressi $(A,B)=(0,1),(1,1),(1,1)$ e uscite $Y=0,1,0$ è certamente sequenziale: allo stesso ingresso $(1,1)$ ha risposto prima $1$ e poi $0$. Un circuito combinatorio non può farlo. L'opposto non vale: una sequenza compatibile con una funzione non dimostra che il sistema sia combinatorio.

Procedura di progetto

1. Specifiche: individuare ingressi e uscite, dare loro un nome.
2. Tabella di verità che lega ingressi e uscite.
3. Funzione booleana a costo minimo per ogni uscita (mappe di Karnaugh, algebra, ecc.): Mappe di Karnaugh - implicanti e copertura minimaLa mappa di Karnaugh è la tabella di verità disposta in una griglia con righe e colonne in codice Gray, così che celle adiacenti (anche tra bordi opposti) differiscano in una sola variabile. Si raggruppano gli 1 in rettangoli di $2^k$ celle: ogni gruppo elimina $k$ variabili e dà un prodotto. Implicante primo = gruppo massimo; essenziale = unico a coprire un mintermine; la copertura minima contiene tutti gli essenziali più il minimo di altri primi (può non essere unica). Efficace fino a 4 variabili.Mappe di Karnaugh - implicanti e copertura minima →.
4. Diagramma logico con i blocchi disponibili nella tecnologia scelta.
5. Verifica della correttezza (tabella o simulazione).

Approccio gerarchico

Con 8 ingressi la tabella ha $2^8=256$ righe: troppo per le mappe. Si usa l'approccio gerarchico (impropriamente "divide et impera"): il sistema è diviso in blocchi e sottoblocchi, ricorsivamente, finché ognuno è abbastanza semplice da progettare da solo; i blocchi si collegano poi tra loro, riusando quelli uguali.

Esempio: comparatore di uguaglianza a 4 bit

Specifica: ingressi $A=A_3A_2A_1A_0$ e $B=B_3B_2B_1B_0$, uscita $E=1$ se $A=B$, altrimenti $E=0$. Due vettori sono uguali se sono uguali a coppie tutti i bit: $A_i=B_i$ per $i=0,\dots,3$.

1. Primo livello: quattro comparatori a 1 bit che producono $N_i=A_i\oplus B_i$ ($N_i=0$ se $A_i=B_i$, $1$ se diversi) e un blocco che combina i quattro $N_i$.
2. Secondo livello: il comparatore a 1 bit è una XOR; il blocco finale deve dare $E=1$ solo se tutti gli $N_i$ valgono 0, quindi è una NOR a 4 ingressi: $E=\overline{N_0+N_1+N_2+N_3}$.

Verifica: $A=1010$, $B=1010\Rightarrow N=0000\Rightarrow E=1$; $A=1010$, $B=1011\Rightarrow N=0001\Rightarrow E=0$ ✓. Costo in ingressi: $4\times2$ (XOR) $+4$ (NOR) $=12$.

La rappresentazione ad albero mostra solo la struttura (sistema $\to$ blocchi $\to$ porte). Se un blocco compare più volte si può disegnare una sola volta ("circuiti regolari"): quanto più un circuito è regolare, tanto meno lavoro richiede il progetto. Il rapporto tra il numero di porte nel circuito finale e il numero di blocchi nel diagramma gerarchico è una misura della regolarità.

Blocchi combinatori elementari

Funzioni di una variabile. Con un solo ingresso $X$ le uscite possibili sono: value-fixing ($F=0$ oppure $F=1$ costante), value-transferring ($F=X$, un semplice filo), value-inverting ($F=\overline X$, un inverter).

Vettori. Un ingresso a $n$ bit si disegna con una linea con una barretta obliqua e il numero di bit; per usare solo alcuni bit si indica l'indice: $X(2)$.

Definizione (circuito di abilitazione). Enabling (abilitazione). Un circuito di abilitazione lascia passare il segnale $X$ all'uscita se il segnale di enable EN vale 1, altrimenti forza l'uscita a un valore fisso. Due forme: $F=X\cdot EN$ (se $EN=0$ allora $F=0$) e $F=X+\overline{EN}$ (se $EN=0$ allora $F=1$).

Esempio: comandi di un'auto. Luci, radio e alzacristalli funzionano solo ad auto accesa: il segnale di accensione IS fa da enable per i tre interruttori $LS,RS,WS$. Equazioni: $L=IS\cdot LS$, $R=IS\cdot RS$, $W=IS\cdot WS$. Se $IS=0$ tutte le uscite sono 0 qualunque sia lo stato degli interruttori (nella tabella di verità le righe con $IS=0$ hanno $X$ negli ingressi interruttore: sono righe "multi-mintermine", un prodotto che non è un mintermine).

I blocchi più importanti, decoder, encoder e multiplexer, hanno una nota a parte: Decoder, encoder e priority encoderUn decoder $n$-to-$m$ ($m\le2^n$) converte un ingresso binario a $n$ bit in un'uscita 1-hot (un solo 1, nella posizione indicata): le sue uscite sono i mintermini degli ingressi, realizzati con $m$ AND; per decoder grandi si usa l'approccio gerarchico (costo in ingressi: 3-to-8 = 27, 6-to-64 = 182) e un enable. Ogni funzione = decoder + OR dei suoi mintermini. L'encoder fa l'operazione inversa (1-hot $\to$ binario) ma sbaglia con più ingressi a 1 o tutti a 0: il priority encoder risolve con una priorità e un'uscita V (valid).Decoder, encoder e priority encoder →, Multiplexer e funzioni logiche realizzate con decoder e multiplexerIl multiplexer (MUX) $2^n$-to-1 ha $2^n$ ingressi dati, $n$ ingressi di selezione e un'uscita che copia l'ingresso selezionato: $Y=\sum_i m_i(S),I_i$. Si realizza con decoder + AND di enable + OR (costo 22 per il 4-to-1) o direttamente (costo 18). Un MUX $2^n$-to-1 realizza qualunque funzione di $n$ variabili (ingressi dati = colonna della tabella di verità); con un MUX $2^{n-1}$-to-1 si usano le $n-1$ variabili come selezione e gli ingressi dati valgono $0$, $1$, $X$ o $\overline X$ (l'ultima variabile). I MUX a vettori selezionano gruppi di bit.Multiplexer e funzioni logiche realizzate con decoder e multiplexer →.

Mappatura tecnologica: NAND e NOR

La mappatura tecnologica sostituisce il diagramma logico con uno che usa i componenti disponibili nella tecnologia scelta. Nella tecnologia CMOS (Porte CMOS e parametri tecnologici dei circuiti integratiNei circuiti integrati digitali (CMOS) i MOSFET si modellano come interruttori: nMOS chiuso se il gate vale 1, pMOS chiuso se il gate vale 0. Una porta CMOS ha una rete di pull-up (PUN, solo pMOS) verso Vdd e una di pull-down (PDN, solo nMOS) verso massa, duali: una è ON e l'altra OFF. NAND: nMOS in serie e pMOS in parallelo; NOR: nMOS in parallelo e pMOS in serie; una porta a $n$ ingressi ha $2n$ transistor. Parametri: fan-in, fan-out, margine di rumore, ritardo di propagazione ($t_{pHL}$, $t_{pLH}$, limita la frequenza di clock), dissipazione di potenza, costo (area di silicio; costi NRE e di produzione).Porte CMOS e parametri tecnologici dei circuiti integrati →) le porte NAND e NOR sono più compatte e veloci di AND e OR, quindi in genere si realizzano circuiti con sole NAND, NOR e inverter.

Proprietà (SOP realizzata con sole NAND). SOP $\to$ NAND-NAND. Una somma di prodotti si realizza con AND seguite da una OR. Applicando due volte la doppia negazione e De Morgan: $$F=P_1+P_2+\dots+P_k=\overline{\overline{P_1+P_2+\dots+P_k}}=\overline{\overline{P_1}\cdot\overline{P_2}\cdots\overline{P_k}}.$$ Ogni $\overline{P_i}$ è l'uscita di una NAND con gli ingressi del prodotto, e la parte esterna è una NAND con $k$ ingressi. Esempio: $F=AB+C\overline D+\overline AC$ diventa $F=\overline{\overline{AB}\cdot\overline{C\overline D}\cdot\overline{\overline AC}}$: tre NAND a 2 ingressi più una NAND a 3 ingressi (più gli inverter per $\overline D$ e $\overline A$). Un prodotto con un solo letterale richiede un inverter al posto della NAND. Le due realizzazioni (AND-OR e NAND-NAND) sono equivalenti per tutte le 16 combinazioni degli ingressi.

Esempio. $F=AB+C=\overline{\overline{AB}\cdot\overline C}$: una NAND a $2$ ingressi per $AB$, un inverter per $C$ e una NAND finale a $2$ ingressi.

Proprietà (POS realizzata con sole NOR). POS $\to$ NOR-NOR. Dualmente $F=S_1S_2\cdots S_k=\overline{\overline{S_1}+\overline{S_2}+\dots}$ si realizza con NOR di somme e una NOR finale. Esempio: $F=(A+\overline B)(C+D)(\overline A+\overline D)=\overline{\overline{A+\overline B}+\overline{C+D}+\overline{\overline A+\overline D}}$: tre NOR a 2 ingressi più una NOR a 3 ingressi.

Esempio. $F=(A+B)(C+D)=\overline{\overline{A+B}+\overline{C+D}}$: due NOR a $2$ ingressi e una NOR finale a $2$ ingressi.

Per questo motivo le realizzazioni NAND sono più adatte alle SOP (molti prodotti, una somma) e quelle NOR alle POS. Caso per caso si valutano costo (porte, ingressi) e ritardi e si sceglie l'implementazione meno cara.

Il passaggio ai livelli di ritardo e al numero massimo di ingressi per porta (fan-in) si discute in Porte CMOS e parametri tecnologici dei circuiti integratiNei circuiti integrati digitali (CMOS) i MOSFET si modellano come interruttori: nMOS chiuso se il gate vale 1, pMOS chiuso se il gate vale 0. Una porta CMOS ha una rete di pull-up (PUN, solo pMOS) verso Vdd e una di pull-down (PDN, solo nMOS) verso massa, duali: una è ON e l'altra OFF. NAND: nMOS in serie e pMOS in parallelo; NOR: nMOS in parallelo e pMOS in serie; una porta a $n$ ingressi ha $2n$ transistor. Parametri: fan-in, fan-out, margine di rumore, ritardo di propagazione ($t_{pHL}$, $t_{pLH}$, limita la frequenza di clock), dissipazione di potenza, costo (area di silicio; costi NRE e di produzione).Porte CMOS e parametri tecnologici dei circuiti integrati →.

Errori comuni

• Dire che un sistema è combinatorio perché una breve sequenza lo è: serve l'intera funzione.
• Dimenticare gli inverter per le variabili negate nella mappatura NAND-NAND.
• Usare la forma NAND-NAND per una POS (o NOR-NOR per una SOP): funziona solo se prima si converte la forma.
• Sottovalutare i ritardi: un circuito molto profondo è più lento.