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

Questa nota completa 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 → con tre casi: la forma a prodotto di somme, le condizioni di indifferenza e le funzioni XOR.

Prodotto di somme minimo (POS)

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.

Esempio. Un gruppo di $0$ che per $\overline F$ dà $\overline AB$ diventa nella POS la somma $A+\overline B$.

Perché la regola dei segni è opposta: il gruppo $\overline AB$ per $\overline F$ dà un prodotto, che negato diventa la somma $A+\overline B$ (De Morgan): le variabili che nel gruppo valgono $0$ ($A$) compaiono dirette, quelle che valgono $1$ ($B$) negate.

Esempio

$F=\prod M(2,5,6,7,8,9,10,11,14)$, cioè $F=0$ nelle celle $2,5,6,7,8,9,10,11,14$ e $F=1$ nelle altre 7:

Gruppi di 0 (IP, tutti essenziali):

• celle $2,6,14,10$ (colonna $CD=10$): variabili costanti $C=1,D=0$; per $\overline F$: $C\overline D$; somma per $F$: $\overline C+D$;
• celle $5,7$ ($A=0,B=1,D=1$): per $\overline F$: $\overline ABD$; somma: $A+\overline B+\overline D$;
• celle $8,9,10,11$ (riga $AB=10$): per $\overline F$: $A\overline B$; somma: $\overline A+B$.

$$F=(\overline C+D)(A+\overline B+\overline D)(\overline A+B)$$

Confronto con la SOP. Raggruppando gli 1 si ottengono tre forme minime equivalenti, tutte con $4$ prodotti da $3$ letterali (12 letterali), per esempio $F=B\overline C\,\overline D+\overline A\,\overline C\,\overline D+\overline A\,\overline BD+ABD$. La POS ha 3 somme e 7 letterali: qui la POS è nettamente più compatta, perché gli 0 sono meno numerosi e meglio raggruppabili degli 1. In generale conviene lavorare sulla fase (1 o 0) che ha meno celle e gruppi più grandi.

Controllo su una cella: per $A=0,B=1,C=0,D=0$ (cella $4$, $F=1$): $\overline C+D=1$, $A+\overline B+\overline D=0+0+1=1$, $\overline A+B=1$; prodotto $=1$ ✓. Per la cella $6$ ($A=0,B=1,C=1,D=0$): $\overline C+D=0+0=0$ → $F=0$ ✓.

Condizioni di don't care

Finora si è supposto che la funzione valga $0$ dove non vale $1$. A volte, però, la funzione non è completamente specificata: per alcune combinazioni degli ingressi il valore dell'uscita è indifferente, perché quella combinazione non può presentarsi (per esempio i codici $1010$–$1111$ in un ingresso BCD, 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 →) o perché il risultato non interessa. Nella tabella e nella mappa si scrive una X.

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.

Esempio. Con una cifra BCD le celle $10$–$15$ sono X: il gruppo delle celle $3,2,11,10$ dà $\overline BC$ usando le X di $10$ e $11$.

Esempio: cifra BCD "primo oppure 1"

Un circuito riceve una cifra BCD $ABCD$ ($0$–$9$) e deve dare $F=1$ se la cifra è $1,2,3,5,7$. Le righe $10$–$15$ non si presentano: sono don't care.

• Gruppo delle celle $1,3,5,7$ ($A=0,D=1$): $\overline AD$, senza usare X.
• Gruppo delle celle $3,2,11,10$ ($B=0,C=1$): $\overline BC$, che usa le X delle celle $10$ e $11$ (e copre le celle 2 e 3).

$$F=\overline BC+\overline AD$$ 2 prodotti, 4 letterali. Se non si sfruttassero le X (trattandole come 0) servirebbe $F=\overline AD+\overline A\,\overline BC$ (5 letterali): le X risparmiano un letterale e una porta con meno ingressi. In POS: gli 0 sono nelle celle $0,4,6,8,9$ e le X sono a disposizione. Gruppi: $\{0,4,8,12\}$ (resta $\overline C\,\overline D$, somma $C+D$), $\{4,6,12,14\}$ (resta $B\overline D$, somma $\overline B+D$), le due righe $AB=11$ e $AB=10$ (resta $A$, somma $\overline A$). Risultato: $F=\overline A\,(C+D)(\overline B+D)$, equivalente alla SOP sulle combinazioni valide (sulle X le due forme possono dare valori diversi, e va bene).

Se due scelte per le X danno lo stesso costo, si hanno due forme minime algebricamente diverse ma equivalenti sulle combinazioni che si presentano.

Funzioni XOR e di parità

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.

Esempio. $X\oplus Y\oplus Z$ vale $1$ per $111$ (tre 1, dispari) e $0$ per $110$ (due 1, pari).

Questa funzione è il bit di somma di un sommatore completo (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 →).

Errori comuni

• Nella POS, scrivere le variabili con i segni della SOP (diretta se 1): per i gruppi di 0 vale la regola opposta.
• Fare gruppi di X non collegati a nessun 1.
• Trattare una X come "da coprire per forza".
• Dimenticare che le forme minime ottenute usando le X possono differire sulle combinazioni non valide: va bene.
• Cercare di raggruppare una mappa a scacchiera.