Decoder, encoder e priority encoder

Sono i blocchi combinatori che cambiano codifica: il decoder da binario a 1-hot, l'encoder da 1-hot a binario. Sono la base dei selettori, dei decoder di indirizzo delle memorie (Memorie ROM e RAM - SRAM, DRAM e organizzazione dei chipUna memoria è un insieme di celle (word da più bit) con circuiteria di controllo. Classificazioni: sola lettura (ROM) o lettura/scrittura; ad accesso casuale (RAM), seriale (SAM) o ibrido (Flash); volatile (SRAM, DRAM) o non volatile. Una RAM $2^k\times n$ ha $k$ bit di indirizzo (indipendenti da $n$), $n$ bit dati, read/write e chip select. SRAM: cella bistabile (latch), veloce, senza refresh; DRAM: condensatore, più densa, con refresh. Organizzazione: decoder di riga e colonna (coincident selection), uscite tri-state, array di chip (più chip per più parole, più bit per più linee dati).Memorie ROM e RAM - SRAM, DRAM e organizzazione dei chip →) e delle unità di controllo.

Codifica 1-hot

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

Esempio. Il valore $5$ in one-hot a $8$ bit è $00100000$: vale $1$ solo il bit di posizione $5$.

La 1-hot usa più bit, ma è comoda: ogni bit "dice" una cosa sola (anche per gli stati di una macchina, Sintesi delle reti sequenziali - riconoscitore di sequenza e codifica degli statiSintesi di una rete sequenziale sincrona: specifiche $\to$ diagramma degli stati $\to$ tabella (riduzione degli stati equivalenti) $\to$ codifica binaria degli stati $\to$ scelta del FF (D PET) $\to$ equazioni di ingresso dei FF e delle uscite $\to$ minimizzazione $\to$ circuito e verifica. Lo stato riassume la parte di storia utile; per i riconoscitori si ha uno stato per ogni prefisso riconosciuto, riusando gli stati (sovrapposizioni). Reset: stato iniziale noto. Codifica Gray (numero minimo di FF) vs 1-hot (un FF per stato, logica più semplice): per il riconoscitore 1101 Gray costa circa la metà.Sintesi delle reti sequenziali - riconoscitore di sequenza e codifica degli stati →).

Decoder

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.

Esempio. Decoder $3$-to-$8$: con ingresso $101$ ($5$) le uscite $D_7\dots D_0$ valgono $00100000$, e $D_5=A_2\overline{A_1}A_0$.

• 1-to-2: $D_0=\overline A$, $D_1=A$ (un inverter e un filo).
• 2-to-4: $D_0=\overline A_1\overline A_0$, $D_1=\overline A_1A_0$, $D_2=A_1\overline A_0$, $D_3=A_1A_0$: 2 inverter e 4 AND a 2 ingressi.

Approccio gerarchico e costo

Per decoder grandi, un'AND per mintermine con $n$ ingressi ciascuna è troppo costosa. Si collegano decoder piccoli: ad esempio un 3-to-8 si ottiene con un decoder 2-to-4, un decoder 1-to-2 e 8 AND a 2 ingressi (ogni AND combina un'uscita del 2-to-4 con una del 1-to-2). Un 6-to-64 si realizza con due decoder 3-to-8 e 64 AND a 2 ingressi.

Costo come numero di ingressi di porta (gli inverter contano 1):

(Il 6-to-64 piatto richiede 64 AND a 6 ingressi, non a 7.) La struttura gerarchica costa meno della metà.

Decoder con enable

Un enable EN abilita o meno le uscite: con $EN=0$ tutte le uscite valgono 0. Si realizza con $m$ AND di enable sulle uscite oppure, per decoder grandi ($n\ge4$) più economico, collegando EN agli ingressi del decoder (a livello delle AND finali).

Realizzare una funzione con un decoder

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.

Esempio: sommatore completo. Ingressi $X,Y,Z$ (addendi e riporto), $S=\sum m(1,2,4,7)$ e $C=\sum m(3,5,6,7)$: decoder 3-to-8 e due OR a 4 ingressi, $S=D_1+D_2+D_4+D_7$, $C=D_3+D_5+D_6+D_7$ (Sommatori binari - half adder, full adder e ripple carryHalf adder (2 ingressi): $S=X\oplus Y$, $C=XY$. Full adder (3 ingressi, con riporto in ingresso $Z$): $S=X\oplus Y\oplus Z$, $C=XY+XZ+YZ=G+PZ$ con $P=X\oplus Y$, $G=XY$; si realizza con due half adder e una OR. Il ripple carry adder a $n$ bit concatena $n$ full adder: il riporto "ondeggia" dal LSB al MSB, quindi il ritardo cresce linearmente con $n$. È un circuito iterativo (gerarchico e regolare). Il moltiplicatore a 2 bit usa 4 AND e 2 half adder.Sommatori binari - half adder, full adder e ripple carry →).

Conviene quando la funzione ha pochi mintermini. Se ne ha più della metà, la OR diventa grande: si usa invece una NOR a cui si collegano i mintermini della funzione complementata ($F=\overline{\sum m_{i\notin F}}$, cioè $F=1$ solo quando nessun mintermine di $\overline F$ è attivo).

Esempio: decoder da BCD a sette segmenti

Il display a sette segmenti ha i segmenti $a,b,c,d,e,f,g$ (da quello in alto, in senso orario, poi quello centrale). Il circuito riceve una cifra BCD $ABCD$ e accende i segmenti giusti. Tabella (1 = acceso, caratteri usuali; $6$ con il segmento $a$, $9$ con $d$):

Con le combinazioni $1010$–$1111$ come don't care, le sette mappe di Karnaugh danno (variabili $A$ = MSB, $D$ = LSB):

Tre realizzazioni possibili: (1) porte con sette mappe indipendenti, condividendo i prodotti comuni tra le uscite per risparmiare AND; (2) decoder 4-to-16 più sette OR, collegando a ogni OR i mintermini del segmento; (3) sette multiplexer 8-to-1 (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 →). Controllo: la cifra $2$ ($A=0,B=0,C=1,D=0$) deve spegnere solo $c$ e $f$: $c=B+\overline C+D=0+0+0=0$ ✓; $f=A+B\overline C+B\overline D+\overline C\,\overline D=0+0+0+0=0$ ✓; $a=C=1$ ✓.

Encoder

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

Esempio. Con $D_5=1$ e gli altri ingressi a $0$: $A_0=1$, $A_1=0$, $A_2=1$, cioè $A=101=5$.

Ogni uscita è la OR degli ingressi il cui indice ha quel bit a 1. La tabella di verità ha solo $8$ righe specificate; le altre $256-8$ combinazioni sono don't care.

Due problemi.

1. Se due ingressi valgono 1 insieme (per esempio $D_3=D_6=1$) l'uscita è la OR dei codici: $011+110=111$, uguale a quella del solo $D_7$: errata.
2. Se tutti gli ingressi valgono 0 l'uscita è $000$, uguale a quella di $D_0=1$.

Priority encoder

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

Esempio a 4 ingressi, priorità $D_3>D_2>D_1>D_0$:

Mappe di Karnaugh (con le X come don't care) danno $$A_1=D_3+D_2,\qquad A_0=D_3+\overline{D_2}D_1,\qquad V=D_3+D_2+D_1+D_0 .$$ Verifica su $D_3D_2D_1D_0=0110$: $A_1=1$, $A_0=0+\overline1\cdot1=0$, quindi $A=10$ cioè $2$, l'indice dell'ingresso a 1 più alto ($D_2$) ✓. Il controllo su tutte le 16 combinazioni (confronto con l'indice del primo 1 incontrato partendo da $D_3$) dà sempre lo stesso risultato.

Il priority encoder è alla base della gestione delle priorità tra interrupt (Interfacce di input-output - strobing, handshaking, interrupt e DMALe periferiche (tastiera, disco, display) hanno velocità, codici e funzionamento diversi dalla CPU: servono interfacce che sincronizzano e adattano i dati. Un unico bus collega più periferiche, ognuna con un decoder di indirizzo (memory-mapped: indirizzi comuni con la memoria; isolated: linee di controllo separate). Controllo asincrono con strobing (senza conferma) o handshaking (con conferma, più robusto). Trasmissione seriale (meno linee) o parallela; simplex, half e full duplex; USB a pacchetti con codifica NRZI. Modi di trasferimento: I/O programmato (busy-wait, spreca la CPU), interrupt (priorità: daisy chain, parallela con maschera), DMA (il controllore prende il bus con BR/BG e trasferisce senza CPU).Interfacce di input-output - strobing, handshaking, interrupt e DMA →).

Errori comuni

• Credere che il decoder produca la forma binaria: produce una 1-hot.
• Dimenticare che un encoder semplice è corretto solo con ingresso 1-hot.
• Non gestire il caso "tutti gli ingressi a 0" nel priority encoder (serve $V$).
• Contare male il costo: nel 6-to-64 piatto le AND hanno 6 ingressi (non 7).