Mappa di Karnaugh

La mappa di Karnaugh è un metodo di rappresentazione esatta di sintesi di reti combinatorie a uno o più livelli. Una tale mappa costituisce una rappresentazione visiva di una funzione booleana in grado di mettere in evidenza le coppie di mintermini o di maxtermini a distanza di Hamming unitaria (ovvero di termini che differiscono per una sola variabile binaria (o booleana)). Poiché derivano da una meno intuitiva visione delle funzioni booleane in spazi $\{0,1\}^{n}$ con $n$ numero delle variabili della funzione, le mappe di Karnaugh risultano applicabili efficacemente solo a funzioni con al più 5 - 6 variabili.

Storia

La mappa di Karnaugh è stata inventata nel 1953 da Maurice Karnaugh, ingegnere delle telecomunicazioni impiegato presso i Bell Laboratories.

Utilizzo

Una mappa di Karnaugh è un metodo grafico che ha come obiettivo quello di ridurre la complessità delle funzioni booleane espresse in forme canoniche. Essa si costruisce a partire dalla tabella della verità di una funzione booleana, nel processo di sintesi di una rete combinatoria.

Le mappe di Karnaugh permettono di costruire semplicemente la forma minima di una funzione come somma di prodotti logici (forma disgiuntiva) o come prodotto di somme logiche (forma congiuntiva) e quindi semplificazioni della funzione booleana spesso più immediate di quelle ottenibili con modifiche algebriche.

Esempio

Le mappe di Karnaugh sono utilizzate per facilitare la semplificazione delle funzioni booleane. Per esempio, si consideri la funzione Booleana descritta dalla seguente tabella di verità:

Tabella di verità di una funzione

#	$A$	$B$	$C$	$D$	$f(A,B,C,D)$
0	0	0	0	0	0
1	0	0	0	1	0
2	0	0	1	0	0
3	0	0	1	1	0
4	0	1	0	0	0
5	0	1	0	1	0
6	0	1	1	0	1
7	0	1	1	1	0
8	1	0	0	0	1
9	1	0	0	1	1
10	1	0	1	0	1
11	1	0	1	1	1
12	1	1	0	0	1
13	1	1	0	1	1
14	1	1	1	0	1
15	1	1	1	1	0

Di seguito sono riportate due notazioni differenti le quali descrivono comunque la stessa funzione in algebra booleana non semplificata, utilizzando le variabili booleane $A$, $B$, $C$, $D$ e le rispettive inverse.

• $f(A,B,C,D)=\sum _{}m_{i},i\in \{6,8,9,10,11,12,13,14\}$ dove $m_{i}$ sono i min-termini della mappa (cioè le righe che hanno output 1 nella tabella di verità).
• $f(A,B,C,D)=\prod _{}M_{i},i\in \{0,1,2,3,4,5,7,15\}$ dove $M_{i}$ sono i max-termini della mappa (cioè le righe che hanno output 0 nella tabella di verità).

Essendoci 16 combinazioni delle 4 variabili booleane, anche la mappa di Karnaugh dovrà avere 16 posizioni. Il modo più conveniente per disporle è in una tabella 4×4.

La mappa di Karnaugh corrispondente alla funzione f

I numeri binari nella griglia mostrano il valore d'uscita della funzione per tutte le combinazioni possibili di ingresso. Scriveremo 0 all'estrema sinistra in alto poiché f = 0 quando A = 0, B = 0, C = 0, D = 0, cioè f(0,0,0,0) = 0. Allo stesso modo scriveremo 1 in basso a destra poiché A = 1, B = 0, C = 1, D = 0 restituiscono f = 1, ovvero f(1,0,1,0,) = 1.

Si noti che le coppie di variabili di input (A,B e C,D) sono ordinate con il codice Gray, in modo che fra coppie di celle adiacenti cambi una sola variabile (distanza di Hamming = 1).

Dopo aver costruito la mappa di Karnaugh si raggruppano gli 1 in rettangoli più grandi possibile, che però abbiano sempre un'area (in quadretti della tabella) pari ad una potenza di 2 (1, 2, 4, 8, 16, 32, …). I raggruppamenti ottimali, in questo esempio, sono quelli indicati nella mappa con il contorno verde, rosso e blu.

Per ciascun raggruppamento troviamo le variabili che non cambiano il loro valore.

Per il primo raggruppamento (il rosso) si vede che:

• La variabile A mantiene lo stesso stato (1) in tutto il gruppo, quindi deve essere inclusa nel prodotto risultante.
• La variabile B non mantiene il suo valore, passando da 1 ( f(1, 1,0, 0) ) a 0 ( f(1, 0, 0, 0)), e quindi deve essere esclusa.
• C non cambia, mantiene lo stesso stato (0), quindi viene inclusa.
• D cambia ed è esclusa.

Così il primo prodotto che farà parte dell'espressione booleana finale è AC' (si considera la variabile diretta se, per i valori all'interno del rettangolo, essa assume il valore 1, e la sua negata se invece assume il valore 0).

Per il rettangolo in verde (formato da quattro 1 disposti in verticale) si vede che A, B mantengono lo stesso stato, mentre C e D cambiano. Essendo B uguale a 0, la variabile deve essere negata prima di venire inclusa nel prodotto. Così si ottiene AB'.

Con lo stesso procedimento, dal rettangolo blu si trova BCD': l'unica variabile che non va inclusa nel prodotto è la A in quanto all'interno del rettangolo essa cambia di valore.

L'espressione finale della funzione f si ottiene sommando i prodotti precedentemente trovati: AC' + AB' + BCD' .

Se si vuole trovare la funzione duale, ossia la funzione che fa uso dei maxtermini, basta semplicemente raggruppare i valori 0 invece degli 1: ciò corrisponde allo scegliere nella tavola di verità le righe per cui la funzione di uscita vale 0 invece che 1. In tal caso vanno complementate (cioè negate) le variabili che rimangono costanti nel raggruppamento e che hanno valore pari a 1. Nell'esempio mostrato la funzione duale è data da (A+C) (A+B) (B'+C'+D') .

In una mappa di Karnaugh con n variabili, un prodotto Booleano di k variabili corrisponde a un rettangolo formato da 2^n-k caselle.

Le mappe di Karnaugh sono adatte anche alla semplificazione di funzioni che contengono condizioni di indifferenza (don't care, cioè valori di input per cui è irrilevante quale sia l'output): queste si rappresentano nella griglia solitamente con i simboli *, - oppure con la lettera greca $\Delta$ (delta), e possono essere considerate sia come 1 che come 0, in modo da formare raggruppamenti maggiori. Non è però consentito effettuare raggruppamenti di soli don't care.

Nota: La griglia è da considerarsi, non come un piano, ma come un toro, quindi i rettangoli possono attraversare i bordi, sia verticalmente che orizzontalmente, passando da un lato a quello opposto. Per esempio anche ABD' potrebbe essere un prodotto valido.

Limiti delle mappe di Karnaugh

• Per le funzioni con più di 4 variabili diventa difficile l'uso delle mappe di Karnaugh; infatti queste per cercare di essere intuitive dovrebbero diventare tridimensionali oppure ricorrere alla Variable Entered Map, o ancora usare altre mappe supplementari in più il cui numero cresce in maniera esponenziale per ogni variabile oltre la quarta. Il numero di tali combinazioni è $2^{n-4}$, dove $n$ è il numero di variabili della funzione: ad esempio 5 variabili necessitano di 2 mappe, 6 variabili necessitano di 4 mappe, mentre 7 variabili necessitano di 8 mappe ($2^{3}$).

Osservazioni

• La funzione ottenuta prendendo opportunamente i raggruppamenti massimi di 1 della Mappa di Karnaugh è quella minima, ossia è quella che esprime l'uscita con il minor numero di termini e quindi che richiede il numero minore di porte logiche per essere realizzata.
• Un'alternativa alle mappe di Karnaugh, utile nei casi già elencati, è il metodo di semplificazione Quine McCluskey.

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sulle mappe di Karnaugh

Collegamenti esterni

• mappa (informatica), su sapere.it, De Agostini.
• Karnaugh, mappa di, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• (EN) Eric W. Weisstein, Karnaugh Map, su MathWorld, Wolfram Research.
• (EN) Karnaugh map, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.
• A.Bondavalli, Semplificazione delle funzioni logiche mediante le mappe di Karnaugh