Come minimizzare un circuito con le mappe di karnaugh

Ormai siamo nell'era del digitale e molte delle moderne tecnologie sono basate su componenti che lavorano in modo digitale.
Il digitale si differenzia dall'analogico perché qualsiasi grandezza può assumere solamente due valori, HIGH e LOW, 1 e 0. Ciò ha permesso una rapida espansione di tali componenti all'interno di macchine più sofisticate come i pc e tutti i calcolatori e/o strumenti numerici. Alla base della logica digitale ci sono le cosiddette funzioni logiche. Dalle funzioni si ricava l'implementazione del circuito che le realizza, e ciò lo si fa tramite le cosiddette porte logiche. Esistono però degli strumenti che permettono di minimizzare un circuito, in modo da ottenere lo stesso risultato ma con performance migliori. Uno di questi sono le mappe di karnaugh. Vediamo allora come si usano e come fare per minimizzare un circuito.

• Carta e penna

Una funzione logica descrive un risultato a partire da uno, due o più ingressi. Gli ingressi e il tipo di operazione logica (AND, OR, NOR, NAND ecc ecc) determinano il numero e il tipo di porte logiche da utilizzare per implementare la funzione. Tali porte logiche (solitamente realizzate con tecnologia CMOS) inseriscono dei ritardi nella propagazione dei segnali, quindi ci sarà un ritardo tra l'applicazione dell'ingresso e la lettura dell'uscita, e tali ritardi sono tanto maggiori quanto maggiore è il numero di porte logiche connesse in cascata (cioè nelle quali l'uscita di una è l'ingresso dell'altra). Inoltre tali porte hanno un costo, che se pure di un infinitesimo, in quantità enormi (si consideri che un chip di un processore contiene all'incirca 4 milioni di porte) risulta non trascurabile.
Un ultimo problema è determinato dall'assorbimento di potenza elettrica, che in totale (per l'intero chip) non è affatto irrisorio.
Risulta chiaro che quindi minimizzare un circuito risulta vantaggioso sotto tutti i punti di vista.

Si può quindi minimizzare un circuito andando a minimizzare la funzione logica. L'obbiettivo delle mappe di karnaugh è quello di formare una nuova funzione logica sfruttando i MINTERMINI, ovvero dei termini che sono estrapolati dalle mappe stesse secondo la logica che stiamo per mostrarvi.

Si parte dalla funzione logica che sarà formata da un certo numero di letterali e saranno quindi presenti dei prodotti logici (che corrispondo ad una funzione AND) e delle somme logiche (che sono invece funzioni OR), inoltre alcuni letterali possono essere soprasegnati, tale convenzione indica la negazione del valore assunto dal letterale (ciò lo si realizza attraverso la funzione NOT) secondo l'algebra di Boole.

Si scrive quindi la tabella di verità della funzione logica da voler minimizzare senza riportare il valore di uscita per nessuna delle combinazioni degli ingressi. Si procede quindi riempiendo la colonna di output ponendo 1 per le combinazioni di ingresso che si ritrovano nella funzione logica di partenza e 0 per quelle combinazioni assenti nella funzione logica.

Dalla tabella di verità si può direttamente estrapolare la mappa di karnaugh. La mappa di karnaugh sarà una matrice avente 2^n locazioni, dove n è il numero di ingressi. Ogni locazione corrisponde ad una possibile combinazione degli ingressi. La particolarità di tale matrice è che passando da una locazione all'altra, sia in verticale che in orizzontale (ma non in diagonale), cambia una sola variabile per volta.
Si procede quindi inserendo 0 o 1 nelle giuste locazioni della mappa. Si esegue quindi questo semplice algoritmo per identificare la funzione minima che dia lo stesso risultato della funzione logica di partenza.

Bisogna quindi identificare il numero minimo di gruppi di 1 che permettono di ricoprire tutti gli 1 presenti nella matrice.
Per ogni gruppo bisogna prendere quanti più 1 possibile tenendo presente due considerazioni: gli 1 devono essere adiacenti (e sono considerati adiacenti anche quelli alle estremità, come se la matrice fosse chiusa su un qualcosa di sferico), e il numero di 1 deve essere una potenza del 2.
 Se ci sono degli 1 che non sono adiacenti a nessun altro 1 questi devono essere portati in conto singolarmente, formeranno quindi un gruppo.
 Ogni gruppo formato darà vita ad un MINTERMINE secondo la seguente logica: si estrarrà un termine letterale che sarà il prodotto logico tra le variabili di ingresso che restano inalterate nel passaggio da una locazione all'altra del gruppo stesso. Tali letterati saranno negati o meno a seconda che il loro valore nel gruppo sia 0 o 1.
I MINTERMINI saranno in numero pari al numero di gruppi e la loro somma logica darà la forma minima della funzione logica di partenza.

• Continuate a fare esercizi per apprendere bene l'algoritmo

• Sintesi di una funzione logica con le mappe di Karnaugh
• Mappa di Karnaugh
• Mappe di Karnaugh : esercizi risolti
• Semplificazione di circuiti notevoli tramite le mappe di Karnaugh

• Come utilizzare le mappe di Karnaugh
• Come codificare una qualsiasi funzione con un multiplexer