5. Mappe di Karnaugh

Non sempre rappresentando una funzione logica in maniera diretta consente di realizzare il circuito elettronico più ottimizzato possibile, ovvero con il minor numeri di componenti elettronici.

Molte volte occorre applicare le proprietà e i teoremi dell’algebra booleana per minimizzare (semplificare) il circuito elettronico da realizzare.

Esiste un metodo grafico più semplice per ottenere questa minimizzazione: le Mappe di Karnaugh.

Struttura di una mappa di Karnaugh #

Una mappa di Karnaugh è costituita da tante caselle quante sono le combinazioni degli ingressi (in altri termini, quante sono le righe della tabella di verità) disposte una di fianco all’altra secondo un determinato schema.

All’interno di ogni casella sarà presente un 1 se l’uscita Y è uguale a 1 (VERA), altrimenti sarà vuota.

Vediamo come vengono costruite a seconda del numero di variabili (ingressi) presenti in un circuito.

Mappa di Karnaugh a 2 variabili (ingressi) #

Nella mappa di Karnaugh a due variabili ci sono 4 caselle. In ogni casella si dovrà inserire un 1 solo se la per la combinazione relativa alla casella il risultato della funzione logica (Y) sarà uguale a 1.

Mappa di Karnaugh a 3 variabili (ingressi) #

Nella mappa di Karnaugh a tre variabili ci sono 8 caselle. Bisogna fare attenzione che nella mappa sono invertite le caselle 2-3 e 6-7.

In ogni casella si dovrà inserire un 1 solo se la per la combinazione relativa alla casella il risultato della funzione logica (Y) sarà uguale a 1.

Mappa di Karnaugh a 4 variabili (ingressi) #

Nella mappa di Karnaugh a quattro variabili ci sono 16 caselle. Bisogna fare attenzione che nella mappa sono invertite le caselle 2-3, 6-7, 11-10, 14-15. Oltre alle caselle sono anche invertite le ultime due colonne.

In ogni casella si dovrà inserire un 1 solo se la per la combinazione relativa alla casella il risultato della funzione logica (Y) sarà uguale a 1.

Mappa di Karnaugh a 5 variabili (ingressi) #

Nelle mappe di Karnaugh a più di 4 variabili si utilizzano sempre le mappe di Karnaugh a 4 variabili, ma se ne usano due per ogni variabile in più:

Per combinazioni che comprendono la quinta variabile (E) uguale a 0 si userà la tabella di Karnaugh in alto. Per combinazioni con E uguale a 1 si userà quella in basso.

Se avessimo sei variabili si dovrebbe aggiungere una colonna a destra.

Esempio pratico di minimizzazione #

Per capire il metodo di minimizzazione con le Mappe di Karnaugh vediamo un esempio pratico. Partiamo dalla seguente funzione logica a quattro variabili:

La tabella di verità della funzione logica è la seguente:

Come evidenziato, l’uscita Y vale 1 (VERA) per le combinazioni delle righe 0,3,5,7,8,11,13,15 che corrispondono alle caselle della mappa di Karnaugh in cui andiamo ad inserire un 1:

Una volta disegnata la mappa bisogna procedere con la minimizzazione per semplificare la funzione logica. Per farlo si devono raggruppare le caselle adiacenti (vicine) rispettando le seguenti regole:

• I raggruppamenti sono costituiti da n caselle che corrispondono a potenze di 2 (1,2,4,8,16…)
• I raggruppamenti sono fatti tra caselle adiacenti, anche quelle che si trovano nei bordi esterni della mappa
• I raggruppamenti devono essere più grandi possibili per semplificare al meglio
• Una casella che fa già parte di un raggruppamento può essere associata ad un altra casella per formare un nuovo gruppo

Seguendo queste regole, dalla mappa di Karnaugh che abbiamo realizzato possiamo fare i seguenti raggrruppamenti:

Una volta raggruppate le caselle bisogna scrivere la funzione minimizzata. Per farlo si devono analizzare le caselle raggruppate per ogni gruppo e metterle in relazione con le variabili delle caselle.

1° gruppo nel primo gruppo abbiamo raggruppato le caselle 3,7,11,15. Ciascuna caselle corrisponde a una combinazione di variabili:

Per semplificare il primo gruppo bisogna prendere le due variabili che non cambiano mai all’interno del gruppo, che sono CD. Di conseguenza, questo gruppo verrà semplificato come CD.

2° gruppo nel secondo gruppo abbiamo raggruppato le caselle 5,7,13,15. Abbiamo quindi la seguente combinazioni di variabili:

Le uniche due variabili che non cambiano sono BD e d quindi il secondo gruppo verrà semplificato con BD.

3° gruppo nel terzo gruppo abbiamo le caselle 0 e 8. Abbiamo quindi la seguente combinazione:

Le uniche variabili che non cambiano sono BCD. Essendo negate, il terzo gruppo verrà semplificato con:

Risultato minimizzazione:

In questo esempio abbiamo visto come è possibile minimizzare una funzione graficamente in maniera molto semplice utilizzando le mappe di Karnaugh.