Mappa di Karnaugh
Da Wikipedia, l'enciclopedia libera.
La mappa di Karnaugh è una metodologia esatta di sintesi di reti combinatorie a uno o più livelli. Queste sono una rappresentazione di una funzione booleana in modo da mettere in evidenza le coppie di mintermini o di maxtermini a distanza di Hamming unitaria (ovvero che differiscono di un solo bit). Siccome derivano da una meno intuitiva visione multidimensionale delle funzioni booleane in campo cartesiano, le mappe di Karnaugh risultano effettivamente applicabili a funzioni fino a 5 - 6 variabili.
Indice |
[modifica] Storia
La mappa di Karnaugh è stata inventata nel 1953 da Maurice Karnaugh, un ingegnere in Telecomunicazioni presso i Bell Laboratories.
[modifica] Utilizzo
Una mappa di Karnaugh riguarda una funzione booleana di un numero poco elevato di variabili e si costruisce a partire dalla tabella della verità di tale funzione.
Il metodo delle mappe di Karnaugh ha il vantaggio di essere un procedimento grafico piuttosto intuitivo e quindi di permettere semplificazioni della funzione booleana spesso più immediate di quelle ottenibili solo con modifiche algebriche.
[modifica] Esempio
Consideriamo la funzione:
- f(A,B,C,D) = E(6,8,9,10,11,12,13,14)
Il valore all'interno di E indica quale riga avrà output 1.
Questa funzione ha la seguente tavola della verità:
| # | 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 |
Essendoci 16 combinazioni delle 4 varibili booleane, anche la mappa di Karnaugh dovrà avere 16 posizioni. Il modo più conveniente per disporle è in una tabella 4x4.
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. Allo stesso modo scriveremo 1 in basso a destra poiché A = 1, B = 0, C = 1, D = 0 restituiscono f = 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 si modifichi una sola variabile.
Dopo aver costruito la mappa di Karnaugh si raggruppano gli 1 in rettangoli più grandi possibili, che però abbiano sempre un' area (in quadretti della tabella) pari ad una potenza di 2 (2, 4, 8, …) e non ad un suo multiplo, come spesso erroneamente accade a chi si cimenta per le prime volte in questi esercizi. 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, 1, 0) ) a 0 ( f(1, 0, 1, 0)), e quindi deve essere esclusa.
- C non cambia e quindi viene inclusa.
- D cambia ed è esclusa.
Così il primo prodotto che farà parte dell'espressione boleana finale è AC'.
Per il rettangolo in verde si vede che A e 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 si trova BCD' dal rettangolo blu.
L'espressione finale si ottiene sommando i prodotti precedentemente trovati: AC' + AB' + BCD' .
Se si vuole trovare la funzione inversa basta semplicemente raggruppare gli 0 invece che gli 1.
In una mappa di Karnaugh con n variabili, un prodotto boleano di k variabili corrisponde a un rettangolo di area 2n-k.
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 come "*" o "-", e possono essere considerate sia come 1 che come 0, in modo da formare raggruppamenti maggiori. Non è però consentito effettuare raggrupamenti 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.
[modifica] Limiti delle mappe di Karnaugh
- Per le funzioni con più di 4 varibili 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 una mappa supplementare in più per ogni combinazione di variabili oltre la quarta. Il numero di tali combinazioni è 2n − 4, dove n è il numero di variabili della funzione: ad esempio 5 variabili necessitano di 2 mappe, mentre 6 variabili necessitano di 4 mappe.
- Non sempre la funzione ottenuta da una mappa di Karnaugh, è la più ottimizzata possibile. Un corretto raggruppamento sulla mappa di Karnaugh consente però di trovare il circuito ottimo a due livelli di logica.
- Un'alternativa alle mappe di Karnaugh, utile nei casi già elencati, è il metodo di semplificazione Quine McCluskey.
