Mappe di Karnaugh

Le Mappe di Karnaugh sono uno strumento grafico inventato da Maurice Karnaugh nel 1953, con lo scopo di ottimizzare le reti logiche combinatorie.

Essenzialmente: sono un’alternativa alle tabelle di verità che risultano efficaci quando si lavora con un massimo di 4 variabili.

La struttura grazie al Codice di Gray:

Nelle Mappe di Karnaugh l’ordine delle combinazione di variabili, sono ordinate seguendo il Codice di Gray, detto anche codice a specchio.

In una tabella di verità, per ogni numero di variabili immagina la colonna di ogni variabile specchiata sotto di lei.

Proviamo a costruire insieme una mappa di verità specchiata: Per il momento abbiamo una sola variabile, quindi una sola colonna: $0, 1$ che andando a specchiare con il Codice di Gray diventerà per intero: $0, 1, 1, 0$. Se adesso aggiungiamo una seconda variabile, nella sua colonna vi sarebbero: $0, 0, 1, 1$, che verrebbe poi specchiata facendo risultare la colonna in totale come: $0, 0, 1, 1, 1, 1, 0, 0$. Assieme a questa verrebbe specchiata anche la colonna della prima variabile già specchiata, portandola così: $0, 1, 1, 0, 0, 1, 1, 0$.

Alla fine è possibile notare come leggendo riga per riga fino al rigo numero $2^n$, è stato ottenuto un ordine diverso delle combinazioni con adiacenza logica, ossia nel quale tra due combinazioni adiacenti cambia un solo bit alla volta.

Come si utilizzano le mappe di Karnaugh?

Abbiamo detto che le mappe di Karnaugh vengono utilizzate per ottimizzare, ma come nello specifico? Ebbene una volta indicati sulla mappa gli $0$ e gli $1$, è necessario raggruppare gli $1$ che compaiono in gruppi di $1$ adiacenti che chiamiamo k-cubi. Tuttavia è necessario sapere che la Mappa di Karnaugh ha una forma Toroide.

La Geometria della Mappa di Karnaugh:

La Mappa di Karnaugh ha una forma Toroide, è quindi come se fosse arrotolata su se stessa prendendo la forma di una ciambella, così che l’ultima colonna sia adiacente alla prima e che l’ultimo rigo sia adiacente al primo.

Esempio grafico della forma Toroide:

Esempi di adiacenza dei lati grazie alla forma Toroide:

Questa proprietà della Mappa di Karnaugh ci permette di raggruppare in k-cubi tenendo conto e sfruttando anche le adiacenze tra righe e colonne apparentemente opposte.

Potenze di 2:

I gruppi di $1$ per essere k-cubi, devono contenere un numero di $1$ che sia una potenza di $2$. Ad esempio gruppi da $1, 2, 4, 8 ...$ celle.

Massima dimensione:

Ogni k-cubo deve essere il più grande possibile, in quanto se il gruppo è più grande ci saranno meno letterali da dover riportare al termine dell’ottimizzazione.

Copertura totale:

Tutti gli $1$ presenti nella Mappa di Karnaugh devono essere inclusi in almeno un k-cubo.

Sovrapposizione:

È anche permesso inserire uno stesso $1$ all’interno di più k-cubi se questo serve a creare gruppi più grandi ottenendo una maggiore semplificazione.

Come leggere il risultato finale:

Una volta creati i k-cubi, ogni gruppo genera un implicante, ossia un termine prodotto (AND), composto solo dalle variabili che mantengono lo stesso valore in tutte le celle del gruppo.

Infine, viene eseguita la somma degli implicanti trovati per ottenere l’espressione booleana ottimizzata, che viene di norma rappresentata in Prima Forma Canonica, quindi le variabili su $0$ vengono rappresentate con la variabile negata, mentre le variabili su $1$ vengono rappresentate con la variabile normale.

Per quale motivo le variabili che non mantengono lo stesso valore vengono cancellate?

Il motivo è che in qualunque caso, quelle variabili verrebbero comunque eliminate algebricamente, quindi facendo così automatizziamo in maniera più diretta il processo.

Prendiamo d’esempio questi due implicanti: $x_1 x_2^{\prime} x_3 + x_1 x_2 x_3$

1. Proprietà Distributiva: Possono essere raccolti i termini comuni ($x_1$ e $x_3$), ottenendo l’espressione: $x_1 x_3 (x_2^{\prime} + x_2)$
2. Proprietà dell’Unicità del Complemento e l’Elemento Nullo: A questo punto, osservando la somma (OR) $x_2^{\prime} + x_2$ notiamo subito che a prescindere dal valore di $x_2$, sappiamo che almeno uno dei due varrà $1$ in quanto è l’elemento nullo dell’OR. Quindi l’espressione diventa: $x_1 x_3 1$ <— Sono tutti in AND (magari non si capisce).
3. Elemento Neutro: Poiché $1$ è l’elemento neutro dell’AND (quindi non fa variare il risultato), può essere omesso semplificando l’espressione: $x_1 x_3$ .

Continua con… Le Reti Logiche Sequenziali.