Esercizio 4comparatore a maggiore di b su due numeri a due bit (tema d'esame luglio 2022)

Teoria usata: 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 →, Progettazione di una rete combinatoria - approccio gerarchico e porte NAND-NORUna rete combinatoria ha uscite che dipendono solo dagli ingressi presenti (nessuna memoria, nessuna retroazione); una sequenziale dipende anche dalla storia (stato, memoria, feedback). Progetto: specifiche, tabella di verità, funzione a costo minimo, diagramma logico, verifica. Con molti ingressi si usa l'approccio gerarchico (blocchi e sottoblocchi riusabili; regolarità). Blocchi base: funzioni di una variabile, vettori, enabling. Mappatura tecnologica: in CMOS NAND e NOR sono più compatte, quindi SOP $\to$ NAND-NAND e POS $\to$ NOR-NOR.Progettazione di una rete combinatoria - approccio gerarchico e porte NAND-NOR →, Introduzione al VHDL - entity, architecture, tipi e livelli di descrizioneVHDL è un linguaggio di descrizione dell'hardware (HDL), non di programmazione: le dichiarazioni sono concorrenti e descrivono blocchi di circuito; serve per documentare, simulare e sintetizzare. Un blocco ha una entity (nome e porte in/out) e almeno una architecture (cosa c'è dentro: structural con component e port map, dataflow con equazioni booleane, behavioral con comportamento). Tipi: std_logic (da 1164: '0','1','X','Z','U','-',...), std_logic_vector, bit, boolean, integer. Signal per i collegamenti interni, constant per i valori fissi.Introduzione al VHDL - entity, architecture, tipi e livelli di descrizione → (stesso comparatore in VHDL).

Passo 1: tabella di verità

Ci sono $4$ ingressi, quindi $16$ righe: per ogni coppia $(a,b)$ di numeri da $0$ a $3$ si scrive $y=1$ se $a>b$. L'indice della riga è $a_1a_0b_1b_0$ in binario.

I mintermini sono $y=\sum m(4,8,9,12,13,14)$ (ci sono $\binom42=6$ coppie con $a>b$, tra $4\cdot3=12$ coppie con $a\ne b$).

Passo 2: mappa di Karnaugh

Righe $a_1a_0$, colonne $b_1b_0$ (codice Gray):

Passo 3: raggruppamenti

Gli implicanti primi sono tre:

• il gruppo da 4 celle $\{8,9,12,13\}$ (righe $a_1a_0=11$ e $10$, colonne $b_1b_0=00$ e $01$): costanti $a_1=1$, $b_1=0$ $\Rightarrow$ $a_1\overline{b_1}$ ("il bit alto di $a$ vale 1 e quello di $b$ vale 0": $a\ge2>b$);
• il gruppo da 2 celle $\{4,12\}$ (colonna $b_1b_0=00$, righe $a_1a_0=01$ e $11$): costanti $a_0=1$, $b_1=0$, $b_0=0$ $\Rightarrow$ $a_0\overline{b_1}\,\overline{b_0}$;
• il gruppo da 2 celle $\{12,14\}$ (riga $a_1a_0=11$, colonne $b_1b_0=00$ e $10$, adiacenti attraverso il bordo): costanti $a_1=1$, $a_0=1$, $b_0=0$ $\Rightarrow$ $a_1a_0\overline{b_0}$.

Sono tutti essenziali: la cella $4$ è coperta solo dal secondo, la cella $14$ solo dal terzo, la cella $8$ solo dal primo.

$$a>b=a_1\overline{b_1}+a_0\,\overline{b_1}\,\overline{b_0}+a_1a_0\,\overline{b_0}$$

Passo 4: verifica e commento

Il controllo sui $16$ casi dà l'uguaglianza con $a>b$ per ogni coppia. Sulla struttura: $a_1\overline{b_1}$ copre i casi in cui il bit alto decide; gli altri due prodotti coprono i casi in cui i bit alti sono uguali ($a_1=b_1$) e decide il bit basso: infatti $a_0\overline{b_1}\,\overline{b_0}$ ($a=01$, $b=00$) e $a_1a_0\overline{b_0}$ ($a=11$, $b\in\{10,00\}$) si possono riscrivere con una XNOR: $a>b=a_1\overline{b_1}+(a_1\odot b_1)\,a_0\overline{b_0}$, forma "gerarchica" che si estende ai comparatori a più bit.

Costo (ingressi di porta, inverter di $b_1,b_0$ compresi): AND a 2 ingressi $(2)$ + AND a 3 $(3)$ + AND a 3 $(3)$ + OR a 3 $(3)$ + 2 inverter $(2)$ $=13$.

In VHDL la funzione si descrive in dataflow come

AgtB <= (A(1) and not B(1)) or (A(0) and not B(1) and not B(0)) or (A(1) and A(0) and not B(0));

(comparatore della nota di introduzione al VHDL, Introduzione al VHDL - entity, architecture, tipi e livelli di descrizioneVHDL è un linguaggio di descrizione dell'hardware (HDL), non di programmazione: le dichiarazioni sono concorrenti e descrivono blocchi di circuito; serve per documentare, simulare e sintetizzare. Un blocco ha una entity (nome e porte in/out) e almeno una architecture (cosa c'è dentro: structural con component e port map, dataflow con equazioni booleane, behavioral con comportamento). Tipi: std_logic (da 1164: '0','1','X','Z','U','-',...), std_logic_vector, bit, boolean, integer. Signal per i collegamenti interni, constant per i valori fissi.Introduzione al VHDL - entity, architecture, tipi e livelli di descrizione →).

La POS minima ha 5 somme: $(\overline{b_1}+\overline{b_0})(a_0+\overline{b_1})(a_1+\overline{b_0})(a_1+\overline{b_1})(a_1+a_0)$: più costosa della SOP (qui si preferisce la SOP).

Errori comuni

• Dimenticare il raggruppamento attraverso il bordo ($\{12,14\}$).
• Raggruppare le celle di $a=b$ (diagonale) o di $a<b$.
• Ordinare le colonne $b_1b_0$ in binario ($00,01,10,11$) invece che in Gray.