Mappe di Karnaugh - implicanti e copertura minima

Semplificare un'espressione con l'algebra (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 →) richiede intuito e non esiste un algoritmo che garantisca la forma più semplice. La mappa di Karnaugh (Maurice Karnaugh, Bell Labs, 1954) è un metodo grafico che porta con certezza a una somma di prodotti minima (o, in modo duale, a un prodotto di somme minimo, 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à →). Funziona bene fino a 4 variabili; programmi di sintesi usano principi analoghi per funzioni più grandi.

Come è fatta una mappa

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

La mappa va pensata richiusa su se stessa: il bordo sinistro è adiacente al bordo destro e il superiore all'inferiore (a cilindro con 3 variabili, a toro con 4). Perciò, per esempio, le quattro caselle d'angolo di una mappa a 4 variabili sono tutte adiacenti.

Numerazione delle celle (indice del mintermine):

Si riempie la mappa mettendo 1 nelle celle dei mintermini della funzione (e $0$, o niente, nelle altre).

Perché un raggruppamento semplifica

Due celle adiacenti differiscono per una variabile: se la funzione vale $1$ in entrambe, quella variabile si elimina, per la regola $XY+X\overline Y=X$ (adiacenza). Esempio: i mintermini $m_2=\overline AB\overline C$ (010) e $m_3=\overline ABC$ (011) sono adiacenti e $\overline AB\overline C+\overline ABC=\overline AB$.

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.

Implicanti e 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.

Procedura.

1. Riempire la mappa con gli 1.
2. Trovare gli IP: i rettangoli più grandi (potenze di 2) di 1 adiacenti, tenendo conto dei bordi che si richiudono.
3. Individuare gli IPE: cercare gli 1 coperti da un solo IP.
4. Se restano 1 scoperti, scegliere pochi altri IP per coprirli (se ci sono scelte equivalenti la forma minima non è unica).
5. Scrivere la somma dei prodotti dei gruppi scelti e verificare su qualche riga.

Esempi svolti

Due variabili

$F=\sum m(1,2,3)$:

Due gruppi da 2: la colonna $B=1$ (celle 1 e 3, resta $B$) e la riga $A=1$ (celle 2 e 3, resta $A$). Sono i due IP, entrambi essenziali (la cella 1 è coperta solo dal primo, la 2 solo dal secondo): $F=A+B$.

Tre variabili con scelta (copertura non unica)

$F=\sum m(0,1,2,5,6)$:

Gli implicanti primi sono quattro:

• celle $1,5$ (colonna $BC=01$): resta $\overline BC$;
• celle $2,6$ (colonna $BC=10$): resta $B\overline C$;
• celle $0,2$ (riga $A=0$, colonne $00$ e $10$, adiacenti attraverso il bordo): resta $\overline A\,\overline C$;
• celle $0,1$ (riga $A=0$, colonne $00$ e $01$): resta $\overline A\,\overline B$.

Essenziali: $\overline BC$ (solo lei copre $5$) e $B\overline C$ (solo lei copre $6$). Restano da coprire la cella $0$, che può esserlo da $\overline A\,\overline C$ oppure da $\overline A\,\overline B$: due forme minime equivalenti, $$F=\overline BC+B\overline C+\overline A\,\overline C\qquad\text{oppure}\qquad F=\overline BC+B\overline C+\overline A\,\overline B,$$ entrambe con $3$ prodotti e $6$ letterali. Verifica sulla cella $0$ ($A=B=C=0$): $\overline BC=0$, $B\overline C=0$, $\overline A\,\overline C=1$ → $F=1$ ✓; sulla $3$ ($A=0,B=C=1$): tutti e tre i prodotti valgono 0 → $F=0$ ✓.

Quattro variabili con tre essenziali

$F=\sum m(1,3,4,5,6,7,9,11,12,13,15)$:

• Le colonne $CD=01$ e $11$ (8 celle: $1,3,5,7,9,11,13,15$): resta $D=1$ → $D$.
• Le celle $4,5,12,13$ ($B=1$, $C=0$): resta $B\overline C$.
• La riga $AB=01$ ($4,5,7,6$): resta $\overline AB$.

Sono i 3 IP, tutti essenziali ($3$ è coperta solo da $D$; $12$ solo da $B\overline C$; $6$ solo da $\overline AB$): $F=D+B\overline C+\overline AB$, contro 11 mintermini da 4 letterali ciascuno nella canonica.

Quattro variabili con essenziali e completamento

$F=\sum m(0,1,2,5,6,7,8,9,10,14)$:

I gruppi grandi sono due: la colonna $CD=10$ (celle $2,6,14,10$, resta $C\overline D$) e il quadrato che si chiude attraverso i bordi (celle $0,1,8,9$, resta $\overline B\,\overline C$); sono essenziali ($14$ è coperta solo dal primo, $9$ solo dal secondo). Rimangono scoperte le celle $5$ e $7$: le copre il gruppo $\{5,7\}$ ($\overline ABD$). Quindi $F=C\overline D+\overline B\,\overline C+\overline ABD$. Gli altri IP ($\overline B\,\overline D$, $\overline ABC$, $\overline A\,\overline CD$) sono validi implicanti ma non servono nella copertura minima.

Costo e scelta tra coperture

Se due coperture hanno lo stesso numero di prodotti e letterali, sono entrambe minime. Se interessa il numero di ingressi delle porte (gate input cost) si confrontano i due totali. Ogni gruppo scelto si realizza con una AND e tutti i gruppi confluiscono in una OR (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 →).

Errori comuni

• Ordinare le celle in binario ($00,01,10,11$) invece che in Gray.
• Non usare i bordi che si richiudono (gruppi che lo richiederebbero restano spezzati).
• Gruppi con numero di celle non potenza di 2 (3, 5, 6, …) o non rettangolari.
• Gruppi non massimi: si ottengono prodotti con letterali inutili.
• Gruppi in eccesso (uno stesso 1 si può usare più volte, ma gruppi tutti già coperti da altri sono ridondanti).
• Sbagliare il segno dei letterali: variabile diretta se vale 1 in tutto il gruppo, negata se 0.