Mappe di Karnaugh (raggruppamenti)

Raggruppamenti nelle mappe K
Fino a questo a punto abbiamo imparato a costruire la mappa di Karnaugh e a riempirla; ora va elaborata, ossia occorre dare inizio alla fase di minimizzazione. Più precisamente si effettuano quelli che si chiamano raggruppamenti delle caselle adiacenti contenenti 1. Chiaramente i raggruppamenti non vanno fatti a piacimento, ma ci sono delle regole da seguire che sono:

1) i raggruppamenti possono essere costituiti da 1, 2 , 4, 8, 16, ecc. caselle, tutte adiacenti l’una all’altra, comprese quelle che si trovano a i bordi esterni della mappa;
2) i raggruppamenti devono essere più ampi possibile e possono anche sovrapporsi parzialmente;
3) una casella già inclusa in un raggruppamento può essere associata ad un’altra casella solo se ciò contribuisce a formare un nuovo gruppo di 2, 4, 8, ecc. caselle.

Come conviene procedere nei raggruppamenti?
Per ottenere i migliori risultati e cioè arrivare all’espressione minima della funzione logica è utile procedere secondo i seguenti punti:

a) si individuano dapprima le caselle che non possono essere combinate con altre; racchiuse in un cerchio esse costituiscono i raggruppamenti da una casella;
b) fra le altre caselle si individuano quelle che possono essere combinate con una soltanto delle altre in un sol modo; si racchiudono i raggruppamenti a due così ottenuti. Per il momento non si considerano le caselle che possono essere raggruppate con un’altra in più di un modo;
c) fra le caselle ancora libere, si individuano quelle che possono essere combinate con altre tre in un sol modo; si racchiudono con una linea i raggruppamenti a quattro così ottenuti. Non si considerano per il momento le caselle che possono essere raggruppate a quattro in più di unn modo;
d) si procede in modo analogo per i raggruppamenti più ampi;
e) se alla fine restano caselle libere, queste possono essere combinate fra loro o con caselle già coperte con il solo criterio di formare il minor numero possibile di gruppi.

Come ben potete comprendere, ragazzi, la fase più delicata del metodo delle mappe di Karnaugh è proprio quella dei raggruppamenti delle caselle contenenti 1 perché sbagliare un raggruppamento significa arrivare a minimizzazioni incomplete.
A questo punto effettuiamo i raggruppamenti sulla nostra funzione logica di tre varibili considerata in uno degli esempi precedenti:




Procediamo ora con l’effettuare i raggruppamenti per la funzione logica di quattro variabili vista prima:




State notando quanto sono potenti le mappe di Karnaugh? A questo punto ricordiamo gli aspetti importanti per fare i raggruppamenti:




Ora resta da esaminare qual è l'espressione logica della funzione minimizzata: seguite la prossima lezione!

Mappe di Karnaugh (riempimento)

Riempimento della mappa K
Abbiamo imparato che una funzione può essere espressa come somma di mintermini o come prodotto di maxtermini. Per effettuare il riempimento della mappa K ci concentreremo sulla forma canonica di tipo P e cioè sulla possibilità di esprimere una funzione come somma di mintermini.
Disegnata la mappa, si individuano sulla tavola di verità le righe che forniscono per la funzione Y il valore 1 e per ogni riga individuata si inserisce un 1 nella corrispondente casella della mappa K. Se la funzione, anziché mediante la tavola di verità, è espressa in forma algebrica come somma di mintermini, si inserisce un 1 nelle caselle corrispondenti ai mintermini presenti nell’espressione. Rimangono invece vuote le caselle corrispondenti a mintermini non presenti nella funzione o a righe della tavola di verità che forniscono per la Y il valore 0.
Facciamo subito qualche esempio: consideriamo una funzione di tre variabili.



Funzione logica a tre variabili espressa in forma algebrica che ha la seguente tavola di verità:



Dalla tavola di verità o dalla forma algebrica della funzione inseriamo gli 1 nella mappa K.
Consideriamo ora l’esempio di una funzione a quattro variabili:


Funzione logica a quattro variabili espressa in forma algebrica che ha la seguente tabella di verità:



Si vede che Y vale 1 in corrispondenza delle righe 0,3,5,7,8,11,13 e 15; pertanto si inserisce un 1 nelle celle corrispondenti della mappa K. La stessa configurazione si ottiene partendo direttamente dai mintermini presenti nella forma algebrica della funzione Y.



A questo punto prendiamoci un pò di pausa. Ricominceremo con i raggruppamenti nelle mappe K.

Mappe di Karnaugh (struttura)

Del modulo sull'algebra di Boole e le porte logiche riporterò una lezione sulle mappe di karnaugh evidenziando la minimizzazione di una funzione logica attraverso di esse.
Non preoccupatevi sarà indolore. Continuate a studiare ragazzi!!!

MAPPE DI KARNAUGH
Bene ragazzi. Parleremo di un metodo potente da applicare sulle funzioni logiche. Ricordate che finora abbiamo imparato come sia possibile implementare una funzione booleana mediante porte logiche a partire sia dall’espressione algebrica della funzione sia dalla sua tavola di verità, dopo aver ricavato una delle due forma canoniche. Su una funzione così ottenuta, il più delle volte, occorre operare in maniera da semplificarla o come si dice, da minimizzarla. Il metodo di cui parleremo in questa lezione è usato proprio per questo scopo. Si tratta delle mappe di Karnaugh o mappe K; è un metodo grafico molto utilizzato.
La mappa di Karnaugh è stata inventata nel 1953 da Maurice Karnaugh, un ingegnere in Telecomunicazioni.
Per quale motivo occorre minimizzare una funzione?
Pensate ad esempio che, una volta ricavata la funzione bisogna realizzarla mediante un circuito; è chiaro allora che minimizzare la funzione significa ridurre il numero di porte logiche da inserire nel circuito il che comporta di ridurre i costi.
Subito vi dico, per non farvi spaventare o preoccupare, che le mappe di Karnaugh sono semplici.
Le mappe di Karnaugh permettono di rappresentare e minimizzare funzioni logiche fino a sei variabili. Esse rappresentano la tabella di verità di una funzione in forma bidimensionale.

Struttura della mappa K
Le mappe di Karnaugh sono composte da un certo numero di caselle o celle.
Quante sono le celle?
Sono pari al numero dei valori delle variabili di ingresso (ovvero quante sono le righe della tavola di verità) opportunamente disposte una accanto all’altra. Un esempio ci aiuterà a capire meglio:


Nella fig.1 notiamo la corrispondenza che c’è fra le caselle della mappa di Karnaugh e le righe della tavola di verità, infatti la cella P0 corrisponde alla riga 0 della tavola di verità, con A=0, B=0; la casella P1 alla riga 1, con A=0, B=1; la casella P2 alla riga 2, con A=1, B=0; infine la casella P3 alla riga 3, con A=1, B=1.
Si può notare anche che con due variabili di ingresso (A, B) abbiamo quattro celle, quindi il numero delle caselle della mappa K è ottenuto come 2n dove n corrisponde al numero delle variabili di ingresso.
Riportiamo anche le mappe per tre (A,B,C) e quattro variabili di ingresso (A,B,C,D):


Ragazzi notate che, specialmente osservando la mappa di Karnaugh a quattro variabili, due caselle adiacenti differiscono per il valore di una sola variabile.
La casella P0 corrisponde ai valori A=0, B=0, C=0, D=0 (riga n.0 della tavola di verità) e quindi al mintermine la casella P1 individuata dalla colonna A=0, B=0 e dalla riga C=0, D=1, corrisponde al mintermine D (riga n.1 della tavola), e così via per tutte le caselle. Fra caselle adiacenti si verifica il cambiamento del valore di una sola variabile: dalla casella P12 alla P8, ad esempio, cambia solo B che passa da 1 a 0, mentre rimangono inalterate A,C e D, rispettivamente uguali a 1,0 e 0; dalla casella P5 alla P7 cambia C da 0 a 1, ecc.
Ciò è stato volutamente ottenuto disponendo opportunamente le righe e le colonne, ossia passando, nell’ordine, dalla riga o colonna 00, alla 01, alla 11, alla 10. La caratteristica dell’adiacenza deriva dal fatto che la mappa di Karnaugh pur essendo disegnata su un piano in realtà ha una struttura toroidale.
Ragazzi sono sicuro che a tutti voi piacciono le ciambelle, vero? Come le preferite? Farcite in che modo? Credo che vada bene qualsiasi gusto, purché sia una ciambella! Ora pensate alla mappa di Karnaugh: immaginatela con i lati sinistro e destro e superiore ed inferiore coincidenti come a formare una ciambella.
Le caselle dell’ultima colonna sono da considerarsi adiacenti a quelle della prima colonna disposte sulla stessa riga; così la P8 con la P0, la P9 con la P1, la P11 con la P3, la P10 con la P2. Infatti nel passaggio dalle une alle altre cambia solo il valore di A. Lo stesso vale per le caselle della prima e dell’ultima riga: le coppie di caselle P0 e P2, P4 e P6, P12 e P14, P8 e P10 sono pertanto adiacenti.


Adesso vi faccio riposare un pò.
Continueremo trattando il riempimento delle mappe di Karnaugh.