Le mappe di Karnaugh rappresentano un metodo grafico-sistematico
per la semplificazione di qualsiasi funzione booleana. Questo metodo si basa
su poche regole e se applicate tutte contemporaneamente portano sempre alla
massima semplificazione delle espressioni booleane.
Una mappa di Karnaugh (mappa di K) è costituita da una serie di celle adiacenti
opportunamente disposte. Ogni cella rappresenta una particolare combinazione
delle variabili d'entrata, che compaiono nell'espressione booleana, sotto forma
di prodotto (se si considerano i MinTermini).
Se n sono le variabili d'entrata della rete, la mappa di K. prevede
2n celle, perché 2n sono le combinazioni
possibili di n variabili booleane. Un'espressione con due variabili A e B richiede
una mappa di K con 4 celle, come mostrato in figura:
Nella mappa di figura a), sono mostrate le quattro celle contenenti tutte le
possibili combinazioni tra due variabili binarie A e B; la figura b), invece,
mostra come viene disegnata la mappa di K, per il suo impiego nella semplificazione
delle funzioni booleane: le variabili sono poste esternamente alle celle. Si
noti come le celle siano collocate in modo tale che qualsiasi coppia di celle
vicine (adiacenti) si consideri, cambi di stato una sola variabile. Altre forme
di mappe di K per tre e quattro variabili:
Celle Adiacenti
Si definiscono celle adiacenti due celle che rappresentano due combinazioni per le quali cambia di stato una sola variabile. In genere sono adiacenti tutte le celle che hanno un lato in comune, quelle agli estremi delle righe e quelle agli estremi delle colonne.
Mappa di Karnaugh e espressioni booleane
Per conoscere il comportamento di una rete logica si determina la tavola della verità e da questa si risale alla funzione logica espressa come una delle due forme canoniche: SOP cioè somma di prodotti (MinTermini) o POS cioè come prodotti di somme (MaxTermini).
Per rappresentare una funzione booleana con la mappa di K, considerandola sottoforma di somma di prodotti, per ogni termine prodotto (MinTermine) si scrive un 1 nella cella corrispondente della mappa di K.
Ad esempio:
In altre parole la mappa di K non è altro che un modo diverso di rappresentare
la tavola della verità della funzione logica data.
La mappa di Karnaugh e la semplificazione di
una funzione logica.
Si devono creare gruppi o raggruppamenti di
1 che si trovano in celle adiacenti seguendo le seguenti regole:
Nel progetto di reti logiche, a volte, si presentano combinazioni delle variabili d'entrata non permesse. Ad esempio il codice BDC (Binary Deimal Code) codifica solo le 10 cifre decimalie e servono 4 bit per la loro codifica. Le possibili combinazione con 4 bit sono 16, nel caso del codice BCD ne servono 10, da 0000,... fino a 1001; le altre 6, a partire da 1010, ... fino a 1111 non sono ammesse. Dovendo costruire una macchina logica con 4 variabili d'entrata che operi soltanto su numeri in BCD è ovvio che le 6 combinazioni suddette non sono codici BCD validi, ma possibili. Queste combinazioni possono essere considerate di indifferenza, nel senso che non avverranno mai.
L'importanza delle condizioni di indifferenza si manifesta nella semplificazione delle mappe di Karnaugh, perchè ognuna di esse può indifferentemente assumere il valore 0 oppure 1 senza influenzare il funzionamento della macchina logica. In questo modo, aumentando il numero degli 1 presenti nella mappa, aumenta la semplificazione dell'espressione della funzione logica e di conseguenza si ottimizza anche il numero di porte per realizzare il circuito.
Nella mappa di Karnaugh le condizioni di indifferenza vengono indicate con una X.
Si
consideri l'esempio di figura: