Espressioni Binarie

Introduzione

Una mappa di Karnaugh permette di ridurre una espressione booleana, oppure ottenerne una a partire da una tabella della verità. Una generica espressione booleana può essere rappresentata dalla tabella della verità, che contiene i valori di output in funzione di quelli di input.

Una mappa di Karnaugh è una rappresentazione della tabella della verità sotto forma di un insieme di celle. A partire da una tabella della verità, si compilano le celle con i valori opportuni ed in seguito applicare alcune regole per ricavare l'espressione corrispondente. Una tabella della verità con n ingressi possiede 2n righe, che corrispondono al numero di combinazioni possibili di n valori binari. Analogamente, una mappa di Karnaugh possiede 2n celle, ognuna identificata da una precisa combinazione degli ingressi. Esiste quindi una corrispondenza tra celle della mappa e righe della tabella.

L'espressione corrispondente alla tabella della verità con cui viene costruita la tabella corrisponde alle combinazioni di ingressi che producono un "1" nella casella relativa. Infatti, se è presente un "1", allora l'uscita sarà "1" in relazione ai valori degli ingressi di quella casella. L'espressione completa è data dalle opportune combinazioni di ingressi corrispondenti alle caselle contenti il valore 1. Ogni combinazione è costituita dagli ingressi messi in AND tra loro. Se un ingresso è 0 allora si deve considerare l'ingresso negato. L'espressione finale è costruita da tutte le combinazioni messe in OR tra loro.

Se, ad esempio, si ricava che l'uscita è "1" per i valori degli ingressi x=0, y=1, allora l'espressione è: out = (not x) and y. Se invece l'uscita è "1" per i valori x=0, y=1, z=0 e x=1, z=1 allora l'uscita è: out = ((not x) and y and (not z)) or (x and z)

Una tale espressione tuttavia può essere ricavata anche direttamente dalla tabella della verità, osservando le combinazioni relative all'uscita "1". La mappa di Karnaugh permette di identificare facilmente delle espressioni semplificate. La procedura indicata in precedenza è sempre corretta, ma non sempre genera delle espressioni minime. Infatti, considerando la seguente tabella della verità:

X Y out
0 0 0
0 1 1
1 0 1
1 1 1

Applicando il metodo descritto si ottiene:
out = ((not x) and y) or (x and (not y)) or (x and y)
che è sicuramente corretta, tuttavia si può notare che è la tabella di verità corrispondente a out = x or y. Quella ottenuta non è dunque l'espressione minima.

Tramite una mappa di Karnaugh è possibile invece ottenere l'espressione minima. Le regole sono:

  1. Si scrive ogni gruppo di variabili d'ingresso (in AND tra loro) corrispondente ad una casella o ad un gruppo di caselle con valore pari a "1". Se il valore di una variabile d'ingresso è 0 allora si utilizza la negazione della stessa
  2. Si devono inserire nell'espressione tutti i gruppi relativi agli "1" presenti nella mappa. È possibile che una casella appartenga a più di un gruppo
  3. Si scrive l'espressione finale mettendo in OR tra loro tutti i gruppi

Inoltre si deve cercare di raggruppare il maggior numero possibile di caselle con valore "1". Il vantaggio delle mappe di Karnaugh consiste proprio nella facile individuazione di questi gruppi.

Mappe di Karnaugh

Mappe con 2 ingressi

La mappa di Karnaugh con due ingressi è quella più semplice possibile. Data una tabella della verità con 2 ingressi, essa sarà del tipo:

X Y out
0 0 m1
0 1 m2
1 0 m3
1 1 m4

Dove la variabile d'uscita è out e per comodità si suppone che assuma i valori m1, m2, m3, m4. Essendo la variabile d'uscita binaria, questi valori non saranno tutti diversi tra loro.

Se si desidera costruire una mappa, si dovranno utilizzare 4 celle. In modo naturale è possibile pensare di assegnare alle colonne il primo ingresso x e alle righe il secondo ingresso y. All'interno delle celle si inserisce il valore della variabile d'uscita in corrispondente.

X=0 X=1
Y=0 m1 m3
Y=1 m2 m4

Una volta completata la tabella, si identificano gli "1" presenti. In base alla loro posizione si possono facilmente applicare le proprietà delle formule booleane.

Si consideri, per esempio, la presenza di due "1" nella prima riga. Allora essi corrispondono ai valori x=0, y=0 e x=1, y=0. Si può notare quindi che la variabile d'uscita è pari a "1" quando y=0. Infatti se questa condizione è soddisfatta, l'uscita è "1" indipendentemente dal valore di x.

X=0 X=1
Y=0 1 1
Y=1 0 0

In particolare, se sono presenti due "1" nella prima fila, allora essi corrisponderebbero a:
(not x and not y) or (x and not y)
dove il primo termine corrisponde a m1 e il secondo a m3. Si può notare che in entrambi i prodotti è presente il valore not y. Quindi l'espressione può essere ridotta, in base alla proprietà distributiva a:
not y and (x or not x)
ma x or not x = 1, quindi not y and 1 = not y.

Osservando nuovamente la mappa di Karnaugh si nota che gli "1" occupano proprio la riga corrispondente a y=0, ovvero not y. Ragionando in modo analogo, si osserva che la seconda riga corrisponde a y, la prima colonna a not x e la seconda colonna a x. La tecnica di risoluzione quindi si basa sull'identificazione di eventuali "raggruppamenti" di "1", che semplificano l'espressione.

Si considera la seguente mappa di Karnaugh:

X=0 X=1
Y=0 1 1
Y=1 1 0

In questo caso esistono due gruppi di "1": quello relativo alla prima riga (y=0) e quello relativo alla prima colonna (x=0). I due gruppi si sovrappongono, ma questo è permesso. Allora l'espressione finale è data dalle espressioni dei due gruppi messe in OR tra loro:
out = (not x) or (not y) = x nand y
per il teorema di De Morgan. Se non si fossero raggruppate le variabili si sarebbe ottenuta l'espressione out = ((not x) and (not y)) or (x and (not y)) or ((not x) and y)

Mappe con 3 ingressi

Con tre ingressi l'associazione righe/colonne non è più intuitiva. Date le variabili x, y, z si può associare la variabile z alle righe e le variabili x e y alle colonne. Poiché devono essere presenti 8 caselle, la mappa è composta da 2 righe e 4 colonne. Ad ogni colonna viene associata una combinazione delle variabili x e y che, per conservare le proprietà, devono rispettare un dato ordine. In particolare, passando da una colonna alla successiva deve variare solo una variabile: quindi la consueta combinazione 00, 01, 10, 11 non può essere utilizzata poiché tra il valore 01 e il valore 10 si modificano entrambe le variabili. E' invece corretta la sequenza seguente: 00, 01, 11, 10, che può essere usata per "etichettare" le colonne.

XY=00 XY=01 XY=11 XY=10
Z=0 a b c d
Z=1 e f g h

Si può notare che la prima riga corrisponde a z=0, la seconda a z=1. La prima e l'ultima colonna corrispondono a y=0, mentre le due colonne centrali a y=1. Invece, le prime due colonne corrispondono a x=0 e le ultime due colonne a x=1. Alternativamente si può utilizzare il seguente schema:

not X not X X X
not Z a b c d
Z e f g h
not Y Y Y not Y

In questo modo ogni casella della mappa corrisponde al valore delle variabili relative presenti nelle colonne e nelle righe. Ad esempio, la casella b corrisponde alle variabili x=0, y=1 e z=0.
Si consideri la seguente mappa:

XY=00 XY=01 XY=11 XY=10
Z=0 0 1 1 1
Z=1 0 1 1 1

Si possono considerare le due colonne centrali, che corrispondono a y=1 e il gruppo dei due "1" che corrisponde a x and (not y), oppure le ultime due colonne (x) e il gruppo dei due "1" che corrisponde a (not x) and y. Quindi l'espressione booleana corrispondente può essere:
out = y or (x and (not y))
oppure
out = x or ((not x) and y)
Si può verificare che le due espressioni generano, al variare di x e y, la stessa tabella della verità (in realtà dovrebbero essere a 3 variabili, ma in questo caso il valore della variabile z è irrilevante). In modo analogo si può organizzare graficamente la tabella in verticale:

X=0 X=1
YZ=00 a b
YZ=01 c d
YZ=11 e f
YZ=10 g h

Oppure:

not X X
not Y a b not Z
not Y c d Z
Y e f Z
Y g h not Z

Mappa con 4 ingressi

Con quattro ingressi si dispone la mappa come una griglia di 4 colonne e 4 righe. Supponendo di avere gli ingressi x, y, z, k, si usano due variabili per le colonne e due variabili per le righe, con lo stessa combinazione utilizzata nel caso dei tre ingressi, ovvero con i valori delle variabili che cambiano da una casella all'altra solo una alla volta.

XY\ZK 00 01 11 10
00 a b c d
01 e f g h
11 i l m n
10 o p q r

In questo caso le righe sono associate alle variabili xy e le colonne alle variabili zk. Alternativamente si può considerare il seguente schema.

not Z not Z Z Z
not X a b c d not Y
not X e f g h Y
X i l m n Y
X o p q r not Y
not K K K not K

Per individuare i valori delle variabili di una casella è sufficiente osservare le variabili presenti nelle righe e nelle colonne. Ad esempio, la casella h ha i seguenti valori: x=0 (nella colonna a sinistra infatti è presente not x), y=1, z=1, k=0. Infatti essa corrisponde a: xy=01 e zk=10.

Determinazione del costo minimo

Data una mappa di Karnaugh, è importante cercare l'espressione con costo minimo. Intuitivamente, quando si sintetizza un circuito a partire da un'espressione, è desiderabile mantenere il numero di porte più piccolo possibile. In particolare si vuole cercare l'espressione minima corrispondente ad una data mappa di Karnaugh.

Una variabile o una combinazione di variabili per cui la funzione vale 1 è detto implicante della funzione.

Un implicante è detto implicante primo se non può essere combinato con altri implicanti per formarne uno con meno variabili. Da esso non è possibile cancellare una sua variabile per ottenere un altro implicante.

Esempio:
Si considera la seguente Mappa di Karnaugh

not Z Z Z not Z
X 0 0 0 0 not Y
X 0 0 1 1 Y
not X 0 0 1 1 Y
not X 1 1 0 0 not Y
K K not K not K

Gli implicanti sono: z(not k)y, (not z)(not k)y e (not x)(not y)k.
Gli implicanti z(not k)y e (not z)(not k)y non sono primi perché possono essere combinati in (not k)y. Quest'ultimo è un implicante primo. (not x)(not y)k non può essere combinato con altri implicanti, quindi è primo.

Un insieme di implicanti che contengono tutte le combinazioni delle variabili per le quali la funzione assume valore 1 è detta copertura. L'insieme di tutti gli implicanti primi costituisce una copertura.

È tuttavia possibile che un sottoinsieme degli implicanti primi costituisca una copertura. In altre parole, non è garantito che l'insieme degli implicanti primi sia una copertura minima.

Se un implicante primo contiene uno o più termini che non sono inclusi in nessun altro implicante primo, allora è detto implicante primo essenziale.

Esempio:
Si considera la seguente Mappa di Karnaugh

X not X
not Y 0 1 not Z
not Y 1 1 Z
Y 1 0 Z
Y 0 0 not Z

Gli implicanti primi sono: xz, (not y)z, (not x)(not y).
Gli implicanti primi essenziali sono solo xz e (not x)(not y), perché l'implicante (not y)z contiene termini che sono già compresi negli altri due implicanti primi.
In questo caso si può notare che i due implicanti primi essenziali costituiscono una copertura minima della funzione.

La ricerca della copertura minima di una funzione procede quindi in questo modo:

  1. calcolo di tutti gli implicanti primi
  2. calcolo di quali implicanti primi sono essenziali
  3. se l'insieme degli implicanti primi essenziali è una copertura per la funzione, allora è la copertura minima, altrimenti, si considerano altri implicanti primi non essenziali fino a raggiungere la copertura
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License