FormularioCircuiti Digitali: definizioni, teoremi e formule delle note, in ordine di capitolo

I. Sistemi digitali e rappresentazione dell'informazione

Sistemi digitali, segnali binari e livelli di astrazione

Formula (margini di rumore)

$$NM_H=V_{OH,\min}-V_{IH,\min}=0{,}9-0{,}6=0{,}3\,\mathrm V,\qquad NM_L=V_{IL,\max}-V_{OL,\max}=0{,}4-0{,}1=0{,}3\,\mathrm V$$

Proprietà (combinazioni di $n$ bit). Un gruppo di $n$ bit ha $2^n$ combinazioni distinte, quindi può rappresentare $2^n$ elementi:

bit	1	2	3	4	8	10	16
combinazioni	2	4	8	16	256	1024	65536

Basi di numerazione e conversioni - binario, ottale ed esadecimale

Definizione (notazione posizionale in base $r$). In base $r$ si usano le $r$ cifre $0,1,\dots,r-1$. Il valore di una cifra dipende dalla posizione: è il coefficiente di una potenza di $r$. Un numero con cifre $a_na_{n-1}\dots a_1a_0.a_{-1}a_{-2}\dots a_{m}$ vale $$N=\sum_{i=m}^{n}a_i\,r^i .$$

Proprietà (cifre ottali ed esadecimali e bit). Poiché $8=2^3$ e $16=2^4$, una cifra ottale corrisponde esattamente a 3 bit e una esadecimale a 4 bit: sono scritture compatte del binario, lunghe un terzo o un quarto.

Proprietà (conversione binario-esadecimale). Si formano gruppi di 4 bit partendo dalla virgola (verso sinistra per la parte intera, verso destra per la frazionaria), completando con zeri i gruppi estremi, e si sostituisce ogni gruppo con la sua cifra. Esempio: $0010\,1100\,0110\,1011{,}1111\,0000\,0110_2=2C6B{,}F06_{16}$.

Proprietà (parte intera: divisioni successive per $r$). Si divide il numero per la base, si annota il resto, si divide il quoziente, e così via fino al quoziente $0$. Il primo resto è la cifra meno significativa: i resti si leggono dal basso verso l'alto. Perché funziona: ogni divisione per $r$ stacca la cifra $a_0$ (il resto) e sposta tutte le altre di una posizione, come cancellare l'ultima cifra in decimale.

Proprietà (parte frazionaria: moltiplicazioni successive per $r$). Si moltiplica la parte frazionaria per 2; la parte intera del prodotto (0 o 1) è la prossima cifra dopo la virgola, a partire dalla più significativa; si ripete sulla nuova parte frazionaria finché si ottiene $0$ o si hanno abbastanza cifre.

Codici binari - BCD, ASCII, Unicode, parità e Gray

Definizione (codice BCD). Il BCD (Binary-Coded Decimal) codifica ogni cifra decimale con il suo valore binario su 4 bit. Per scrivere un numero si codifica cifra per cifra:

Definizione (codifica UTF-8)

intervallo del code point	byte	schema dei bit
U+0000 – U+007F	1	0xxxxxxx
U+0080 – U+07FF	2	110xxxxx 10xxxxxx
U+0800 – U+FFFF	3	1110xxxx 10xxxxxx 10xxxxxx
U+10000 – U+10FFFF	4	11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

I bit x sono quelli del code point, scritti in binario e distribuiti da sinistra a destra.

Definizione (bit di parità). Per rilevare errori (non correggerli) si aggiunge un bit scelto in modo che il numero totale di 1 sia pari (parità pari, la più usata) oppure dispari.

Definizione (distanza di Hamming). La distanza di Hamming tra due configurazioni è il numero di bit in cui differiscono. Esempi: $8=1000$ e $11=1011$ differiscono nei due bit meno significativi, distanza $2$; $8=1000$ e $4=0100$ differiscono in due posizioni, distanza $2$; $0=000$ e $7=111$, distanza $3$. Non è la differenza algebrica dei numeri.

Definizione (codice Gray). Il codice Gray è un codice in cui due numeri consecutivi hanno distanza di Hamming $1$: passando dal numero al successivo cambia un solo bit.

Formula (conversione binario-Gray). Il bit più significativo si copia; ogni altro bit è lo XOR del bit binario corrispondente con quello alla sua sinistra: $g_i=b_i\oplus b_{i+1}$. Esempio: $b=1011$: $g_3=1$; $g_2=0\oplus1=1$; $g_1=1\oplus0=1$; $g_0=1\oplus1=0$, quindi $g=1110$. La conversione inversa è $b_i=b_{i+1}\oplus g_i$.

Numeri con segno, complemento a 2, sottrazione e overflow

Definizione (complemento a 1 e a 2). Dato $N$ su $n$ bit:

• complemento a 1: $(2^n-1)-N$, cioè il complemento di ogni bit (si scambiano 0 e 1);
• complemento a 2: $2^n-N$, cioè complemento a 1 più 1.

Definizione (numeri con segno in complemento a 2). I positivi sono come in senza segno ($0$ seguito dal modulo); un negativo $-N$ si rappresenta con il complemento a 2 di $N$, cioè $2^n-N$. L'MSB è $0$ per tutti i positivi e $1$ per tutti i negativi. Con 4 bit:

bit	senza segno	segno e modulo	complemento a 2
0000	0	$+0$	0
0111	7	7	7
1000	8	$-0$	$-8$
1001	9	$-1$	$-7$
1010	10	$-2$	$-6$
1011	11	$-3$	$-5$
1100	12	$-4$	$-4$
1101	13	$-5$	$-3$
1110	14	$-6$	$-2$
1111	15	$-7$	$-1$

Proprietà (intervallo e peso dell'MSB in complemento a 2). In complemento a 2 c'è un solo zero e l'intervallo è asimmetrico: da $-2^{n-1}$ a $2^{n-1}-1$ (con 8 bit da $-128$ a $127$; $-(-128)$ non è rappresentabile). Il valore si legge dando all'MSB il peso $-2^{n-1}$: $11110011=-128+64+32+16+2+1=-13$.

Formula (sottrazione in complemento a 2). $A-B=A+(-B)$, cioè si somma ad $A$ il complemento a 2 di $B$: $A-B=A+\overline B+1$ (complemento a 1 di $B$ più 1). Esempio: $+7-(-12)$: $-12=11110100$, il suo complemento a 2 è $00001100$ ($+12$), e $00000111+00001100=00010011=+19$ ✓.

Proprietà (overflow in complemento a 2). Somma e sottrazione di operandi di segno diverso non hanno mai overflow (il modulo non cresce). Si ha overflow solo se i due addendi (per la sottrazione: $A$ e $-B$) hanno lo stesso segno e il risultato ha segno opposto. In termini di riporti: c'è overflow se il riporto che entra nel bit di segno è diverso dal riporto che esce dal bit di segno: $$V=C_{in,\,MSB}\oplus C_{out,\,MSB}.$$

II. Algebra di Boole, porte logiche e minimizzazione

Algebra di Boole - assiomi, teoremi e complemento di una funzione

Proprietà (identità fondamentali dell'algebra di Boole). Le identità vengono a coppie duali: la seconda si ottiene dalla prima scambiando AND con OR e $0$ con $1$.

nome	forma OR	forma AND (duale)
elemento neutro	$X+0=X$	$X\cdot1=X$
minimo e massimo	$X+1=1$	$X\cdot0=0$
idempotenza	$X+X=X$	$X\cdot X=X$
complemento	$X+\overline X=1$	$X\cdot\overline X=0$
doppia negazione	$\overline{\overline X}=X$
commutativa	$X+Y=Y+X$	$XY=YX$
associativa	$X+(Y+Z)=(X+Y)+Z$	$X(YZ)=(XY)Z$
distributiva	$X(Y+Z)=XY+XZ$	$X+YZ=(X+Y)(X+Z)$

Teorema (De Morgan)

$$\overline{X+Y}=\overline X\cdot\overline Y,\qquad\overline{X\cdot Y}=\overline X+\overline Y .$$

Teorema (semplificazione: assorbimento, adiacenza e consenso)

nome	forma	dimostrazione
assorbimento	$X+XY=X$	$X+XY=X(1+Y)=X\cdot1=X$
assorbimento (dual)	$X(X+Y)=X$	duale
	$X+\overline XY=X+Y$	$X+\overline XY=(X+\overline X)(X+Y)=1\cdot(X+Y)$
adiacenza (unificazione)	$XY+X\overline Y=X$	$X(Y+\overline Y)=X\cdot1=X$
consenso	$XY+\overline XZ+YZ=XY+\overline XZ$	vedi sotto

Proprietà (complemento di una funzione). Il complemento $\overline F$ ha la tabella di verità con $0$ e $1$ scambiati nella colonna dell'uscita. Per ottenerne l'espressione si hanno due vie.

(a) De Morgan. Esempio: $F_1=\overline AB+A\overline B$ (XOR). $\overline{F_1}=\overline{\overline AB}\cdot\overline{A\overline B}=(A+\overline B)(\overline A+B)=A\overline A+AB+\overline B\,\overline A+\overline BB=AB+\overline A\,\overline B$ (XNOR) ✓.

(b) Duale e negazione dei letterali. Si scrive l'espressione duale (scambio di AND/OR e di $0/1$) e poi si nega ogni letterale. Stesso esempio: il duale di $\overline AB+A\overline B$ è $(\overline A+B)(A+\overline B)$; negando i letterali si ottiene $(A+\overline B)(\overline A+B)$, uguale al risultato di (a) ✓.

Porte logiche, ritardi e porte universali

Definizione (porte AND, OR e NOT). AND (congiunzione, prodotto logico; $Z=X\cdot Y=XY=X\land Y$): $Z=1$ se e solo se tutti gli ingressi valgono 1.

OR (disgiunzione, somma logica; $Z=X+Y=X\lor Y$): $Z=1$ se almeno uno degli ingressi vale 1.

NOT (negazione, inverter; $Z=\overline X=X'$): $Z=1$ se $X=0$.

Definizione (porte NAND, NOR, XOR e XNOR)

• NAND = NOT(AND): $Z=\overline{XY}$; vale 0 solo se tutti gli ingressi sono 1.
• NOR = NOT(OR): $Z=\overline{X+Y}$; vale 1 solo se tutti gli ingressi sono 0.
• XOR (OR esclusivo, $Z=X\oplus Y$): vale 1 se gli ingressi sono diversi.
• XNOR: complemento dello XOR; vale 1 se gli ingressi sono uguali.

Definizione (ritardo di una porta). Una porta reale ha un tempo di ritardo $t_G$ (gate delay, tempo di propagazione): il tempo che trascorre da quando cambia almeno un ingresso a quando il cambiamento arriva all'uscita. Dipende dalla tecnologia, dalla tensione di alimentazione, dalla temperatura e dal carico pilotato (fan-out). In genere il ritardo per la commutazione $0\to1$ in uscita ($t_{pLH}$) è diverso da quello per $1\to0$ ($t_{pHL}$), e dipende da quale ingresso commuta; per semplicità si assume spesso $t_{pLH}=t_{pHL}=t_G$.

Proprietà (porte universali: NAND e NOR). Un insieme di porte è universale (o completo) se con esse si realizza ogni funzione booleana. $\{AND, OR, NOT\}$ lo è per definizione; NAND da sola lo è, e NOR da sola lo è.

Con NAND (un inverter è una NAND con gli ingressi cortocircuitati):

• NOT: $\overline X=\overline{X\cdot X}$ (1 NAND);
• AND: $X\cdot Y=\overline{\overline{XY}}$, cioè una NAND seguita da un inverter (2 NAND);
• OR: $X+Y=\overline{\overline X\cdot\overline Y}$ (De Morgan: due inverter e una NAND, 3 NAND).

Con NOR, dualmente: NOT $=$ NOR con ingressi uniti; OR $=\overline{\overline{X+Y}}$ (2 NOR); AND $X\cdot Y=\overline{\overline X+\overline Y}$ (3 NOR).

Forme canoniche - mintermini, maxtermini, SOP e POS

Definizione (mintermine). Un mintermine (minterm) è un prodotto (AND) in cui compare una e una sola volta ciascuna variabile della funzione, in forma diretta o negata. Ogni mintermine corrisponde a una riga della tabella di verità: vale $1$ per la combinazione di valori di quella riga e $0$ per tutte le altre. Si costruisce prendendo ciascuna variabile diretta se il suo bit nella riga è 1, negata se è 0. Se la riga è il numero $i$ (letto in binario con la prima variabile come bit più significativo) il mintermine si chiama $m_i$.

Definizione (maxtermine). Il maxtermine (maxterm) è il concetto duale: una somma (OR) che contiene una e una sola volta tutte le variabili, dirette o negate. Ogni maxtermine vale $0$ su una sola riga e $1$ su tutte le altre. Si costruisce con ciascuna variabile negata se il suo bit nella riga è 1, diretta se è 0 (è l'opposto della regola dei mintermini). Anche i maxtermini sono $2^n$ e corrispondono alle righe della tabella.

Proprietà (mintermine e maxtermine con lo stesso indice). Il mintermine e il maxtermine con lo stesso indice sono uno il complemento dell'altro: $\overline{m_i}=M_i$. Per $i=3$: $\overline{\overline X YZ}=X+\overline Y+\overline Z$ ✓ (De Morgan, Algebra di Boole - assiomi, teoremi e complemento di una funzioneL'algebra di Boole opera su variabili a due valori con AND, OR, NOT. Identità fondamentali (neutro, idempotenza, complemento, commutativa, associativa, distributiva in entrambe le forme), dualità (si scambiano AND/OR e 0/1), De Morgan $\overline{X+Y}=\overline X,\overline Y$, assorbimento $X+XY=X$, $X+\overline XY=X+Y$, adiacenza $XY+X\overline Y=X$, consenso $XY+\overline XZ+YZ=XY+\overline XZ$. Si dimostrano per induzione perfetta (tabella) o algebricamente. Il complemento di una funzione si ottiene con De Morgan o con duale + negazione dei letterali. Costo: numero di letterali o di ingressi delle porte.Algebra di Boole - assiomi, teoremi e complemento di una funzione →).

Definizione (forme canoniche SOP e POS). Dalla tabella di verità di $F$:

• SOP canonica (Sum Of Products): somma dei mintermini delle righe in cui $F=1$. In breve $F=\sum m(\dots)$.
• POS canonica (Product Of Sums): prodotto dei maxtermini delle righe in cui $F=0$. In breve $F=\prod M(\dots)$.

Mappe di Karnaugh - implicanti e copertura minima

Definizione (mappa di Karnaugh). La mappa ha una cella per ogni riga della tabella di verità, cioè per ogni mintermine (Forme canoniche - mintermini, maxtermini, SOP e POSUn mintermine è un prodotto che contiene una e una sola volta tutte le variabili (dirette o negate) e vale 1 su una sola riga della tabella di verità; un maxtermine è la somma duale e vale 0 su una sola riga; con $n$ variabili ci sono $2^n$ mintermini e $2^n$ maxtermini, e $\overline{m_i}=M_i$. Forma canonica SOP = somma dei mintermini delle righe con $F=1$; POS = prodotto dei maxtermini delle righe con $F=0$. Le forme canoniche si ricavano sempre dalla tabella ma sono ridondanti: servono come punto di partenza per la minimizzazione. SOP e POS si realizzano con circuiti a due livelli.Forme canoniche - mintermini, maxtermini, SOP e POS →). Le variabili sono distribuite su righe e colonne, e le combinazioni sono ordinate in codice Gray ($00,01,11,10$, non $00,01,10,11$) in modo che due celle vicine differiscano di una sola variabile, cioè siano a distanza di Hamming $1$ (Codici binari - BCD, ASCII, Unicode, parità e GrayUn codice binario a $n$ bit distingue $2^n$ elementi. BCD: una cifra decimale ogni 4 bit (1010–1111 non usati; 10 richiede 8 bit, non è il binario del numero). ASCII: 7 bit per 128 caratteri, la cifra ASCII è 011 seguito dal BCD. Unicode/UTF-8: da 1 a 4 byte, compatibile con ASCII. Bit di parità: rileva errori su un numero dispari di bit. Distanza di Hamming = numero di bit diversi. Codice Gray: numeri consecutivi differiscono di un solo bit (sensori di posizione); si costruisce per riflessione o con $g_i=b_i\oplus b_{i+1}$.Codici binari - BCD, ASCII, Unicode, parità e Gray →).

Proprietà (gruppo di $2^k$ celle). Estendendo: un gruppo rettangolare di $2^k$ celle (1, 2, 4, 8, 16) formato da 1 elimina $k$ variabili; il prodotto che lo rappresenta contiene le sole variabili che non cambiano all'interno del gruppo, dirette se valgono 1, negate se valgono 0.

Definizione (implicante, implicante primo ed essenziale, copertura)

• Implicante: prodotto per cui la funzione vale 1 ogni volta che il prodotto vale 1 (un gruppo di 1).
• Implicante primo (IP): implicante che non è contenuto in nessun implicante più grande (gruppo massimo, non ingrandibile).
• Implicante primo essenziale (IPE): IP che è l'unico a coprire almeno un mintermine della funzione; va incluso in ogni copertura.
• Copertura: insieme di implicanti che copre tutti gli 1. Obiettivo: copertura minima, cioè tutti gli IPE più il minor numero di altri IP che copre i mintermini rimasti.

Mappe di Karnaugh - POS, condizioni di don't care e parità

Proprietà (POS minima dai gruppi di zeri). La SOP raggruppa gli 1. La POS si ottiene raggruppando gli 0, ossia lavorando sul complemento $\overline F$:

1. si marcano gli 0 della mappa e si raggruppano come si farebbe con gli 1 (rettangoli di $2^k$, IP e IPE), ottenendo una SOP minima di $\overline F$;
2. si complementa con De Morgan: $F=\overline{\overline F}$. In pratica, per ogni gruppo si scrive una somma con le variabili che non cambiano, diretta se nel gruppo valgono 0, negata se valgono 1;
3. $F$ è il prodotto di queste somme.

Proprietà (condizioni di don't care). Una X si può usare come 1 o come 0, a seconda di ciò che serve per fare gruppi più grandi. Regole:

• una X dentro un gruppo viene trattata come 1, e non è coperta esplicitamente: la funzione ottenuta vale 1 su quella combinazione;
• una X lasciata fuori è trattata come 0;
• non si fa un gruppo che contenga solo X, e non è obbligatorio coprire le X;
• una X non rende un gruppo "essenziale": gli IPE si definiscono rispetto ai soli mintermini a 1.

Proprietà (XOR a tre variabili e mappa a scacchiera). La funzione XOR a 3 variabili (disparità, vale 1 se il numero di 1 in ingresso è dispari) è $X\oplus Y\oplus Z=\sum m(1,2,4,7)$. La sua mappa ha gli 1 a scacchiera:

$X\backslash YZ$	00	01	11	10
0	0	1	0	1
1	1	0	1	0

Nessun 1 è adiacente a un altro: i mintermini sono a distanza di Hamming 2 l'uno dall'altro. Non esistono gruppi da più di una cella, quindi la SOP minima coincide con la canonica ($4$ prodotti da $3$ letterali) e non si semplifica. Conviene usare le porte XOR: $S=(X\oplus Y)\oplus Z$ con due porte. Lo stesso vale per 4 variabili (16 celle, scacchiera da 8 mintermini dispari) e per la funzione di parità (complemento: $1$ se gli 1 sono in numero pari), che si ottiene sostituendo le XOR con XNOR.

III. Progettazione di reti combinatorie

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

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 →).

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$).

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.

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.

Decoder, encoder e priority encoder

Definizione (codifica one-hot). Nella codifica one-hot una configurazione a $m$ bit contiene uno e un solo 1, in una posizione che identifica il valore. Con $n=3$ bit binari i valori $0,\dots,7$ diventano:

binario	000	001	010	011	100	101	110	111
one-hot (8 bit)	00000001	00000010	00000100	00001000	00010000	00100000	01000000	10000000

Definizione (decoder $n$-to-$m$). Un decoder $n$-to-$m$ ha $n$ ingressi e $m\le2^n$ uscite $D_0,\dots,D_{m-1}$: pone a 1 l'uscita il cui indice è codificato dagli ingressi e a 0 le altre. Se a ogni combinazione degli ingressi corrisponde un'uscita valida, $m=2^n$. Esempio: ingresso $A_1A_0=11$ (cioè $3$) $\Rightarrow$ $D_3D_2D_1D_0=1000$.

Le uscite di un decoder sono i $2^n$ mintermini degli ingressi: $D_i=m_i$ (Forme canoniche - mintermini, maxtermini, SOP e POSUn mintermine è un prodotto che contiene una e una sola volta tutte le variabili (dirette o negate) e vale 1 su una sola riga della tabella di verità; un maxtermine è la somma duale e vale 0 su una sola riga; con $n$ variabili ci sono $2^n$ mintermini e $2^n$ maxtermini, e $\overline{m_i}=M_i$. Forma canonica SOP = somma dei mintermini delle righe con $F=1$; POS = prodotto dei maxtermini delle righe con $F=0$. Le forme canoniche si ricavano sempre dalla tabella ma sono ridondanti: servono come punto di partenza per la minimizzazione. SOP e POS si realizzano con circuiti a due livelli.Forme canoniche - mintermini, maxtermini, SOP e POS →). Quindi si realizza con $m$ porte AND a $n$ ingressi, ciascuna con la combinazione di ingressi diretti e negati del proprio mintermine.

Proprietà (funzione realizzata con un decoder e una OR). Una funzione in SOP è la somma dei suoi mintermini; il decoder genera tutti i mintermini. Quindi ogni funzione si realizza con un decoder e una porta OR a cui si collegano le uscite dei mintermini della SOP.

Definizione (encoder). L'encoder esegue l'operazione inversa del decoder: riceve un segnale 1-hot a $2^n$ bit e produce la codifica binaria a $n$ bit. Per l'encoder da ottale a binario con ingressi $D_0,\dots,D_7$ (un solo 1 alla volta): $$A_0=D_1+D_3+D_5+D_7,\quad A_1=D_2+D_3+D_6+D_7,\quad A_2=D_4+D_5+D_6+D_7 .$$

Definizione (priority encoder). Il priority encoder gestisce ingressi non 1-hot con due modifiche:

1. una funzione di priorità: conta solo l'ingresso a 1 con la priorità più alta, gli altri sono ignorati;
2. un'uscita V (valid): $V=1$ se almeno un ingresso vale 1, $V=0$ se sono tutti 0 (e allora l'uscita $A$ è don't care).

Multiplexer e funzioni logiche realizzate con decoder e multiplexer

Definizione (multiplexer $2^n$-to-1). Un MUX ha $2^n$ ingressi dati $I_0,\dots,I_{2^n-1}$, $n$ ingressi di selezione $S_{n-1}\dots S_0$ e un'uscita $Y$. Il segnale di selezione può essere binario o 1-hot; qui è binario: se $S$ vale $i$ in binario, allora $Y=I_i$.

MUX 2-to-1 ($n=1$): $Y=\overline S\,I_0+S\,I_1$. Se $S=0$ allora $Y=I_0$, se $S=1$ allora $Y=I_1$.

MUX 4-to-1 ($n=2$): $$Y=\overline S_1\overline S_0I_0+\overline S_1S_0I_1+S_1\overline S_0I_2+S_1S_0I_3 .$$

L'equazione generale è $Y=\sum_i m_i(S)\cdot I_i$: i mintermini degli ingressi di selezione fanno da "porte" per i dati.

Proprietà (funzione di $n$ variabili con un MUX $2^n$-to-1). Una funzione di $n$ variabili si realizza con un MUX $2^n$-to-1: le $n$ variabili sono collegate agli ingressi di selezione (rispettando l'ordine dei bit: la variabile più significativa va a $S_{n-1}$), e agli ingressi dati si applica il valore della tabella di verità, riga per riga: $I_i=F(i)$, una costante 0 o 1 (value fixing). Perché funziona: per la riga $i$ il MUX seleziona $I_i$, che è proprio il valore che la funzione deve avere.

Proprietà (funzione con un MUX $2^{n-1}$-to-1 e l'ultima variabile come dato). Si può usare un MUX più piccolo, con un ingresso di selezione in meno: si collegano alla selezione solo $n-1$ variabili e agli ingressi dati si applicano le costanti $0$, $1$ oppure la variabile rimasta $X$ o il suo complemento $\overline X$. Per ogni valore della selezione, le due righe della tabella (con $X=0$ e $X=1$) danno una coppia di valori:

$F(X=0)$	$F(X=1)$	ingresso dati
0	0	$0$
1	1	$1$
0	1	$X$
1	0	$\overline X$

IV. VHDL per la logica combinatoria

Introduzione al VHDL - entity, architecture, tipi e livelli di descrizione

Definizione (entity). È la "targa" del blocco: ne dà il nome e definisce l'interfaccia con l'esterno (quali porte, di che direzione e tipo). Non dice che cosa c'è dentro, come il simbolo di un circuito in uno schema. Un blocco deve avere una sola entity.

Definizione (architecture). È una descrizione particolare del contenuto di una entity: come si comporta e come opera internamente. Una entity può avere più architecture nello stesso progetto (per esempio una structural e una dataflow); un progetto non può avere più entity per lo stesso blocco.

Definizione (vettori std_logic_vector). std_logic_vector(n-1 downto 0) ha il bit più significativo a sinistra, di indice $n-1$; std_logic_vector(0 to n-1) ha l'indice $0$ a sinistra (è il MSB). Un bit si estrae con x(2), una porzione con x(3 downto 1); il concatenamento si scrive &: "10" & "01" vale "1001". I letterali esadecimali si scrivono x"1F". Il tipo integer si usa per parametri (lunghezza dei vettori, indici dei cicli) e si scrive in decimale senza virgolette.

Formula (confronto $A>B$ a 2 bit)

$$A>B=A_1\overline{B_1}+A_0\overline{B_1}\,\overline{B_0}+A_1A_0\overline{B_0}.$$

VHDL - istruzioni concorrenti, process e testbench

Definizione (assegnazione concorrente). y <= (a and b) or c; è un'equazione booleana. Ogni volta che cambia un segnale a destra, y viene rivalutato. Con più assegnazioni allo stesso segnale in istruzioni concorrenti si hanno più driver: in simulazione, se i valori sono diversi, il segnale diventa 'X' (conflitto); è un errore di progetto.

Proprietà (when ... else). Le condizioni sono valutate in ordine: se la prima è vera si sceglie il primo valore e le successive non contano. Serve per le priorità e permette decisioni su segnali diversi in condizioni diverse.

Proprietà (with ... select). Si valuta una sola espressione di scelta (S); tutte le scelte hanno la stessa priorità, tutti i valori possibili devono essere coperti da una e una sola scelta e when others è obbligatorio per i valori non elencati. È più semplice del when-else per i circuiti a selezione (multiplexer, decoder, tabelle di verità). Più valori si elencano con |: '1' when "0100" | "1000".

Definizione (lista di sensibilità). Lista di sensibilità (sensitivity list): i segnali al cui cambiamento il process si attiva. Per descrivere un circuito combinatorio deve contenere tutti gli ingressi (in VHDL-2008 si può scrivere process (all)). Può contenere solo segnali leggibili (ingressi o signal interni, non uscite). Un process senza lista parte subito all'inizio della simulazione e va avanti ripetendosi, a meno di un wait: è lo schema dei testbench.

Proprietà (aggiornamento dei segnali in un process). Il valore assegnato a un segnale dentro un process viene aggiornato solo quando il process si sospende (finite le istruzioni o a un wait). Se lo stesso segnale è assegnato più volte nello stesso passaggio, vale l'ultima assegnazione. Quindi

process (b)
begin
  a <= b;
  a <= not b;
end process;

descrive $a=\overline b$: un semplice inverter, cioè logica combinatoria, e non un flip-flop né un segnale che alterna.

Proprietà (memoria non voluta). Se in un if (o in un case) non si specificano tutte le condizioni, il segnale mantiene il valore precedente per quelle non coperte: il sintetizzatore deve introdurre un elemento di memoria (latch). È lo stesso meccanismo con cui si descrive di proposito un latch o un flip-flop; ma in un circuito che deve essere combinatorio è un errore.

Definizione (testbench). Il testbench è codice VHDL che simula un circuito: applica segnali in ingresso al circuito da verificare (DUT, device under test) e osserva le uscite. Non si sintetizza: serve solo per la simulazione.

V. Sommatori e sottrattori binari

Sommatori binari - half adder, full adder e ripple carry

Formula (half adder)

$$S=X\oplus Y,\qquad C=X\cdot Y .$$

Formula (full adder: somma e riporto). La somma $S$ vale 1 quando il numero di 1 in ingresso è dispari: è la funzione di disparità (Mappe di Karnaugh - POS, condizioni di don't care e paritàPer la POS minima si raggruppano gli 0 della mappa, si ottiene la SOP minima di $\overline F$ e si scrive $F$ come prodotto di somme (variabile diretta se vale 0 nel gruppo, negata se vale 1). Le condizioni di don't care (X) sono combinazioni di ingresso che non si presentano o la cui uscita è indifferente: si usano come 1 o come 0 a seconda di quel che allarga i gruppi (mai raggruppamenti fatti solo di X). Le funzioni XOR a più variabili (disparità) e XNOR (parità) hanno mappa a scacchiera: non si semplificano con i gruppi.Mappe di Karnaugh - POS, condizioni di don't care e parità →), $S=X\oplus Y\oplus Z=\sum m(1,2,4,7)$. Il riporto $C$ vale 1 quando almeno due ingressi valgono 1 (funzione maggioranza): $C=\sum m(3,5,6,7)=XY+XZ+YZ$ (SOP minima: 3 implicanti primi, tutti essenziali).

Formula (full adder con propagate e generate). Si pone $P=X\oplus Y$ (propagate) e $G=XY$ (generate). Allora $$S=P\oplus Z,\qquad C=G+P\cdot Z .$$

Definizione (sommatore ripple carry). Per sommare due numeri di $n$ bit $A=A_{n-1}\dots A_0$ e $B=B_{n-1}\dots B_0$ si collegano $n$ full adder: il riporto in uscita di ciascuno è il riporto in ingresso del successivo, dal LSB ($C_0$, di solito $0$) al MSB ($C_n$). Il riporto si propaga (ripple = ondeggiare) lungo la catena.

Formula (ritardo del sommatore ripple carry). Ogni full adder può calcolare la propria somma solo quando riceve il riporto dal precedente: i riporti si determinano uno dopo l'altro. Se ogni porta ha ritardo $t_G$, il riporto attraversa ogni stadio in circa $2t_G$ (una AND e una OR). Il ritardo totale cresce linearmente con $n$: circa $2n\,t_G$ per l'ultima somma. Il ripple adder è il più semplice e il più lento; per numeri a molti bit si usano circuiti con riporto anticipato (carry look-ahead), non trattati nel corso.

VI. Reti sequenziali: latch, flip-flop e macchine a stati

Elementi di memoria - latch SR, latch D e flip-flop D

Definizione (circuito sequenziale). In un circuito sequenziale le uscite dipendono dagli ingressi presenti e dalla storia passata, riassunta dallo stato. Si realizza collegando ingressi e uscite di una rete combinatoria con uno o più elementi di memoria (per noi i flip-flop), con un percorso di retroazione (feedback): le uscite degli elementi di memoria tornano agli ingressi della rete combinatoria. I circuiti combinatori sono aciclici, quelli sequenziali ciclici.

Definizione (latch SR). Con $S=1,R=0$ l'uscita va a $Q=1$ ($\overline Q=0$): set. Con $S=0,R=1$ va a $Q=0$ ($\overline Q=1$): reset. Con $S=R=0$ il latch conserva lo stato precedente. Nel funzionamento normale $Q$ e $\overline Q$ sono uno il complemento dell'altro.

La combinazione $S=R=1$ è proibita: porta entrambe le uscite a $0$, violando il requisito che $\overline Q$ sia il complemento di $Q$; e il vero problema è che, passando da $(1,1)$ a $(0,0)$, non si può prevedere il valore delle uscite (dipende dall'ordine in cui commutano $S$ e $R$ e dai ritardi delle porte). Nella simulazione ideale con commutazioni simultanee e ritardi uguali l'uscita finirebbe a un valore intermedio tra 0 e 1, non realistico.