Mappa di Karnaugh
Da Wikipedia, l'enciclopedia libera.
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). Siccome 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.
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 non molto elevato di variabili e si determina a partire dalla tabella della verità di questa funzione.
Il metodo delle mappe di Karnaugh è grafico e permette di costruire semplicemente la forma minima di una funzione come somma di prodotti logici (forma congiuntiva) o come prodotto di somme logiche (forma disgiuntiva). Essa ha il vantaggio di essere un procedimento grafico piuttosto intuitivo e quindi di permettere semplificazioni della funzione booleana spesso più immediate di quelle ottenibili 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 tabella 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 variabili 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 duale, ossia la funzione che fa uso dei Maxtermini, basta semplicemente raggruppare gli 0 invece che gli 1; ciò corrisponde nello scegliere nella tavola di verità le righe per cui la funzione di uscita vale 0 invece che 1.
In una mappa di Karnaugh con n variabili, un prodotto boleano di k variabili corrisponde a un rettangolo formato da 2n-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 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 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 una mappa supplementare in più per ogni variabile 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.
[modifica] Osservazioni
- La funzione ottenuta prendendo opportunamente i raggruppamenti massimi di 1 della Mappa di Karnaugh è minima ossia è quella funzione che dà la funzione di uscita con il minor numero di termini e quindi che richiede il numero minore di porte logiche.
- Un'alternativa alle mappe di Karnaugh, utile nei casi già elencati, è il metodo di semplificazione Quine McCluskey.
[modifica] Collegamenti esterni
Portale Matematica: accedi alle voci di Wikipedia che parlano di matematica
