Le Mappe di Karnaugh

Concetti Chiave

Il metodo delle mappe di Karnaugh fornisce una rappresentazione visiva delle funzioni booleane, facilitando la loro minimizzazione.
Le mappe di Karnaugh sono particolarmente utili per funzioni con un numero ridotto di variabili (fino a 4 o 5).
La minimizzazione tramite K-map si basa sull'identificazione di gruppi di 1 adiacenti, che possono essere combinati per formare termini più semplici.
I termini più semplici prendono il nome di sotto-cubi e possono essere composti in modo da coprire più mintermini ma sempre in numero pari ad una potenza di due: 1, 2, 4, 8.

Il Metodo delle Mappe di Karnaugh

La complessità delle porte logiche digitali che implementano una funzione booleana è direttamente correlata alla complessità dell'espressione algebrica che descrive la funzione. Sebbene la rappresentazione della tabella di verità di una funzione sia unica, quando è espressa algebricamente può apparire in molte forme diverse, ma equivalenti. Le espressioni booleane possono essere semplificate con mezzi algebrici come visto nella lezione sui teoremi dell'algebra booleana.

Tuttavia, questa procedura di minimizzazione è scomoda, perché manca di regole specifiche per predire ogni passo successivo nel processo manipolativo. Il metodo delle mappe presentato in questa lezione fornisce una procedura semplice e diretta per minimizzare le funzioni booleane. Questo metodo può essere considerato come una forma pittorica di una tabella di verità. Il metodo delle mappe è anche conosciuto come il metodo della mappa di Karnaugh o K-map.

Una K-map è un diagramma composto da quadrati, con ogni quadrato che rappresenta un mintermine della funzione che deve essere minimizzata. Poiché qualsiasi funzione booleana può essere espressa come somma di mintermini, ne consegue che una funzione booleana è riconosciuta graficamente nella mappa dall'area racchiusa da quei quadrati i cui mintermini sono inclusi nella funzione. Infatti, la mappa presenta un diagramma visivo di tutti i modi possibili in cui una funzione può essere espressa in forma standard. Riconoscendo vari modelli, l'utente può derivare espressioni algebriche alternative per la stessa funzione, da cui può essere selezionata la più semplice.

Le espressioni semplificate prodotte dalla mappa sono sempre in una delle due forme standard: somma di prodotti o prodotto di somme. Si assumerà che l'espressione algebrica più semplice sia quella che ha un numero minimo di termini con il minor numero possibile di letterali in ogni termine. Questa espressione produce un diagramma circuitale con un numero minimo di porte e il numero minimo di input a ogni porta. Vedremo successivamente che l'espressione più semplice non è unica: è talvolta possibile trovare due o più espressioni che soddisfano i criteri di minimizzazione. In tal caso, qualsiasi soluzione è soddisfacente.

Mappe di Karnaugh a due Variabili

Una mappa di Karnaugh a due variabili è mostrata nella figura che segue:

Ci sono quattro mintermini per due variabili; quindi, la mappa consiste di quattro quadrati, uno per ogni mintermine. La mappa è ridisegnata di seguito per mostrare la relazione tra i quadrati e le due variabili $x$ e $y$ :

**Figura 2:** Mappa di Karnaugh a due variabili ridisegnata per mostrare la relazione tra le variabili e i mintermini delle singole celle

Lo 0 e l'1 marcati in ogni riga e colonna designano i valori delle variabili. La variabile $x$ appare complementata nella riga 0 e non complementata nella riga 1. Similmente, $y$ appare complementata nella colonna 0 e non complementata nella colonna 1.

Se marchiamo i quadrati i cui mintermini appartengono a una data funzione, la mappa a due variabili diventa un altro modo utile per rappresentare qualsiasi delle 16 funzioni booleane di due variabili.

Come esempio, la funzione AND, $f(x,y) = xy$ , è mostrata nella figura seguente:

**Figura 3:** Mappa di Karnaugh della funzione AND a due variabili

Poiché $xy$ è uguale al mintermine $m_3$ , un 1 è posto all'interno del quadrato che appartiene a $m_3$ .

Analogamente, la funzione OR, $f(x, y) = x + y$ è rappresentata nella mappa della figura che segue da tre quadrati marcati con 1:

**Figura 4:** Mappa di Karnaugh della funzione OR a due variabili

Questi quadrati corrispondono ai singoli mintermini della seguente espressione algebrica:

m_1 + m_2 + m_3 = x'y + xy' + xy = x + y

I tre quadrati avrebbero potuto essere determinati anche dall'unione dei quadrati della variabile $x$ nella seconda riga e quelli della variabile $y$ nella seconda colonna, che racchiude l'area appartenente a $x$ o $y$ :

**Figura 5:** Mappa di Karnaugh della funzione OR a due variabili: Sottocubi evidenziati rispettivi a x e y

In ogni esempio, i mintermini per cui la funzione è vera sono marcati con un 1.

Mappe di Karnaugh a Tre Variabili

Una mappa di Karnaugh a tre variabili è mostrata nella figura che segue:

Ci sono otto mintermini per tre variabili binarie; quindi, la mappa consiste di otto quadrati. Si noti che i mintermini sono disposti, non in una sequenza binaria, ma in una sequenza simile al codice di Gray.

La caratteristica di questa sequenza è che solo un bit cambia valore da una colonna adiacente alla successiva.

Per evidenziare questa caratteristica, ridisegniamo la mappa nella figura che segue:

**Figura 7:** Mappa di Karnaugh a Tre Variabili: Evidenziazione dei mintermini

In figura, la mappa è marcata con mintermini numerati in ogni riga e ogni colonna per mostrare la relazione tra i quadrati e le tre variabili. Per esempio, il quadrato assegnato a $m_5$ corrisponde alla riga 1 e alla colonna 01. Quando questi due numeri sono concatenati, danno il numero binario 101, il cui equivalente decimale è 5. Ogni cella della mappa corrisponde a un mintermine unico, quindi un altro modo di guardare al quadrato $m_5 = xy'z$ è considerarlo nella riga marcata $x$ e nella colonna appartenente a $y'z$ (colonna 01). Si noti che ci sono quattro quadrati in cui ogni variabile è uguale a 1 e quattro in cui ognuna è uguale a 0. La variabile appare non complementata nei primi quattro quadrati e complementata negli ultimi.

Per comprendere l'utilità della mappa nel semplificare le funzioni booleane, dobbiamo riconoscere la proprietà di base posseduta dai quadrati adiacenti: Qualsiasi due quadrati adiacenti nella mappa differiscono per una sola variabile, che è complementata in un quadrato e non complementata nell'altro (I quadrati che sono vicini su una diagonale non sono considerati adiacenti).

Per esempio, $m_5$ e $m_7$ giacciono in due quadrati adiacenti. La variabile $y$ è complementata in $m_5$ e non complementata in $m_7$ , mentre le altre due variabili sono le stesse in entrambi i quadrati. Dai postulati dell'algebra booleana, ne consegue che la somma di due mintermini in quadrati adiacenti può essere semplificata a un singolo termine prodotto consistente di solo due letterali. Per chiarire questo concetto, consideriamo la somma di due quadrati adiacenti come $m_5$ e $m_7$ :

m_5 + m_7 = xy'z + xyz = xz(y' + y) = xz

Qui, i due quadrati differiscono per la variabile $y$ , che può essere rimossa quando viene formata la somma dei due mintermini. Quindi, qualsiasi due mintermini in quadrati adiacenti (verticalmente o orizzontalmente, ma non diagonalmente, adiacenti) che sono messi in OR insieme causeranno una rimozione della variabile dissimile.

I prossimi quattro esempi spiegano la procedura per minimizzare una funzione booleana con una mappa di Karnaugh.

Esempio 1

Semplificare la funzione booleana che segue:

F(x, y, z) = \Sigma(2, 3, 4, 5)

Per prima cosa costruiamo la mappa di Karnaugh inserendo un 1 in ogni quadrato del mintermine corrispondente. Questo è mostrato nella figura che segue, in cui i quadrati per i mintermini 010, 011, 100, e 101 sono marcati con 1:

**Figura 8:** Esempio 1: Mappa di Karnaugh

Il passo successivo è trovare possibili quadrati adiacenti. Questi sono indicati nella mappa da due rettangoli colorati, ognuno che racchiude due 1:

Il rettangolo in alto a destra rappresenta l'area racchiusa da $x'y$ . Quest'area è determinata osservando che l'area di due quadrati è nella riga 0, corrispondente a $x'$ , e nelle ultime due colonne, corrispondenti a $y$ . Similmente, il rettangolo in basso a sinistra rappresenta il termine prodotto $xy'$ . (La seconda riga rappresenta $x$ e le due colonne di sinistra rappresentano $y'$ ).

La somma di quattro mintermini nei quadrati ombreggiati può essere sostituita da una somma di solo due termini prodotto. La somma logica di questi due termini prodotto dà l'espressione semplificata

F = x'y + xy'

Sotto-cubi Adiacenti

In certi casi, due quadrati nella mappa sono considerati adiacenti anche se non si toccano. Nella figura che segue, $m_0$ è adiacente a $m_2$ e $m_4$ è adiacente a $m_6$ perché i loro mintermini differiscono per una variabile:

Questa differenza può essere prontamente verificata algebricamente:

m_0 + m_2 = x'y'z' + x'yz' = x'z'(y' + y) = x'z'

m_4 + m_6 = xy'z' + xyz' = xz'(y' + y) = xz'

Di conseguenza, dobbiamo modificare la definizione di quadrati adiacenti per includere questo e altri casi simili. Lo facciamo considerando la mappa come disegnata su una superficie in cui i bordi destro e sinistro si toccano per formare quadrati adiacenti.

Esempio 2

Semplifichiamo la funzione booleana

F(x, y, z) = \Sigma(3, 4, 6, 7)

La mappa per questa funzione è mostrata nella figura seguente:

**Figura 11:** Esempio 2: Mappa di Karnaugh

Ci sono quattro quadrati marcati con 1, uno per ogni mintermine della funzione.

Adesso segniamo i quadrati adiacenti come in figura:

Due quadrati adiacenti ombreggiati nella terza colonna sono combinati per dare un termine a due letterali $yz$ . I restanti due quadrati con 1 sono anche adiacenti per la nuova definizione. Questi due quadrati ombreggiati, quando combinati, danno il termine a due letterali $xz'$ . La funzione semplificata diventa quindi:

F(x, y, z) = yz + xz'

Combinazioni di quattro mintermini

Consideriamo ora qualsiasi combinazione di quattro quadrati adiacenti nella mappa a tre variabili. Qualsiasi tale combinazione rappresenta la somma logica di quattro mintermini e risulta in un'espressione con solo un letterale. Come esempio, la somma logica dei quattro mintermini adiacenti 0, 2, 4, e 6 si riduce al singolo termine letterale $z'$ :

**Figura 13:** Combinazione di quattro mintermini

m_0 + m_2 + m_4 + m_6 = x'y'z' + x'yz' + xy'z' + xyz'

= x'z'(y' + y) + xz'(y' + y)

= x'z' + xz' = (x' + x)z' = z'

Il numero di quadrati adiacenti che possono essere combinati deve sempre rappresentare un numero che è una potenza di due, come 1, 2, 4, e 8.

Man mano che più quadrati adiacenti sono combinati, otteniamo un termine prodotto con meno letterali.

Un quadrato rappresenta un mintermine, dando un termine con tre letterali.

Due quadrati adiacenti rappresentano un termine con due letterali.

Quattro quadrati adiacenti rappresentano un termine con un letterale.

Otto quadrati adiacenti racchiudono l'intera mappa a tre variabili e producono una funzione che è sempre uguale a 1.

Esempio 3

Semplifichiamo la funzione booleana:

F(x, y, z) = \Sigma(0, 2, 4, 5, 6)

La mappa per $F$ è mostrata nella figura:

**Figura 14:** Esempio 3: Mappa di Karnaugh

Troviamo i quadrati adiacenti come mostrato nella figura che segue:

Prima, combiniamo i quattro quadrati adiacenti nella prima e ultima colonna per dare il singolo termine letterale $z'$ . Il restante quadrato singolo, che rappresenta il mintermine 5, è combinato con un quadrato adiacente che è già stato usato una volta. Questo non è solo permissibile ma anche piuttosto desiderabile, perché i due quadrati adiacenti danno il termine a due letterali $xy'$ e il quadrato singolo rappresenta il mintermine a tre letterali $xy'z$ .

La funzione semplificata è quindi:

F(x, y, z) = z' + xy'

Esempio 4

Se una funzione non è espressa in forma somma-di-mintermini, è possibile usare la mappa per ottenere i mintermini della funzione e poi semplificare la funzione a un'espressione con un numero minimo di termini. È necessario, tuttavia, assicurarsi che l'espressione algebrica sia in forma somma-di-prodotti. Ogni termine prodotto può essere tracciato nella mappa in uno, due, o più quadrati. I mintermini della funzione sono poi letti direttamente dalla mappa.

Chiariamo meglio con il prossimo esempio.

Per la funzione booleana

F = A'C + A'B + AB'C + BC

(a) Si esprima questa funzione come somma di mintermini.
(b) Si trovi l'espressione somma-di-prodotti minimale.

Si noti che $F$ è una somma di prodotti, ma non una somma di mintermini. Tre termini prodotto nell'espressione hanno due letterali e sono rappresentati in una mappa a tre variabili da due quadrati ciascuno.

La funzione può essere rappresentata su di una mappa di karnaugh in questo modo:

**Figura 16:** Esempio 4: Mappa di Karnaugh

I due quadrati corrispondenti al primo termine, $A'C$ , sono situati nella figura di sopra nella coincidenza di $A'$ (prima riga) e $C$ (due colonne centrali) per dare i quadrati 001 e 011. Si noti che, nel marcare 1 nei quadrati, è possibile trovare un 1 già posto lì da un termine precedente. Questo accade con il secondo termine, $A'B$ , che ha 1 nei quadrati 011 e 010. Il quadrato 011 è comune con il primo termine, $A'C$ , però, quindi solo un 1 è marcato in esso. Continuando in questo modo, determiniamo che il termine $AB'C$ appartiene al quadrato 101, corrispondente al mintermine 5, e il termine $BC$ ha due 1 nei quadrati 011 e 111. La funzione ha un totale di cinque mintermini, come indicato dai cinque 1 nella mappa della figura di sopra.

I mintermini sono letti direttamente dalla mappa come 1, 2, 3, 5, e 7. La funzione può essere riespressa in forma somma-di-mintermini come

F(A, B, C) = \Sigma(1, 2, 3, 5, 7)

L'espressione somma-di-prodotti, come originariamente data, ha troppi termini. Può essere semplificata, come indicato dai quadrati ombreggiati nella mappa che segue:

L'espressione risultante sarà:

F = C + A'B

Esempio 5

Semplifichiamo la funzione booleana:

F(x, y, z) = \Sigma(0, 1, 6, 7)

Disegniamo la mappa di Karnaugh relativa:

**Figura 18:** Esempio 5: Mappa di Karnaugh

Troviamo la copertura con i sotto-cubi più grandi:

In tal caso, il sotto-cubo rosso corrisponde al termine $x'y'$ mentre quello verde al termine $xy$ . Per cui la forma minimizzata della funzione risulta: