Elettrotecnica e non solo (admin)
Un gatto tra gli elettroni (IsidoroKZ)
Esperienza e simulazioni (g.schgor)
Moleskine di un idraulico (RenzoDF)
Il Blog di ElectroYou (webmaster)
Idee microcontrollate (TardoFreak)
PICcoli grandi PICMicro (Paolino)
Il blog elettrico di carloc (carloc)
DirtEYblooog (dirtydeeds)
Di tutto... un po' (jordan20)
AK47 (lillo)
Esperienze elettroniche (marco438)
Telecomunicazioni musicali (clavicordo)
Automazione ed Elettronica (gustavo)
Direttive per la sicurezza (ErnestoCappelletti)
EYnfo dall'Alaska (mir)
Apriamo il quadro! (attilio)
H7-25 (asdf)
Passione Elettrica (massimob)
Elettroni a spasso (guidob)
Bloguerra (guerra)
Indice |
La riduzione, o minimizzazione, delle funzioni booleane (seconda parte)
Dopo aver analizzato la riduzione delle formule booleane con il metodo algebrico (vedi LogicBignami (VI)) vediamo adesso un sistema "grafico" che ci permette la riduzione senza ricorrere a nessun passaggio matematico.
Le mappe di Karnaugh: costruzione della griglia
Questo metodo risulta applicabile in maniera semplice per funzioni booleane con un massimo di 5 variabili, oltre tale numero l'utilizzo delle mappe di Karnaugh si complica, in questi casi si deve ripiegare sul metodo algebrico già visto, o sul metodo della tabulazione o di Quine-McCluskey che vedremo in seguito.
Le mappe di Karnaugh rappresentano un particolare sistema di visualizzare i mintermini (o maxtermini) di una tabella della verità sotto forma di griglia.
Per trasformare una tabella della verità in griglia si dovranno suddividere le variabili booleane in due gruppi: un gruppo individuerà le colonne e l'altro le righe.
Quindi avremo i seguenti casi:
Tabella della verità a 3 variabili booleane ---> Mappa di Karnaugh 2 righe x 4 colonne
Una variabile booleana "indicizzerà" le righe (stati possibili 
) e le altre due "indicizzeranno" le colonne (stati possibili 
).
Tabella della verità a 4 variabili booleane ---> Mappa di Karnaugh 4 righe x 4 colonne
Due variabili booleane "indicizzeranno" le righe e le altre due "indicizzeranno le colonne"
Tabella della verità a 5 variabili booleane ---> 2 Mappe di Karnaugh 4 righe x 4 colonne
Come vedremo si tratta di una particolare forma "bidimensionale" di griglia dove quattro variabili booleane individuano, come detto precedentemente, le righe e le colonne su entrambe le mappe, e la quinta variabile individua la singola mappa.
Nota: Nell'accoppiare due variabili booleane, queste dovranno avere "indice" consecutivo, ad esempio, date le variabili booleane 
, 
, 
e 
:
| Accoppiamento corretto
|
|---|
 e  |
Tralasciamo le tabelle della verità a 2 variabili booleane, per le quali le funzioni booleane d'uscita coincidono o con le funzioni di una delle porte logiche viste in LogicBignami (III) o in LogicBignami (V), oppure sono immediatamente riducibili con il metodo algebrico.
Prima di addentrarci nella costruzione delle griglie, rinfreschiamoci un attimo le definizioni di mintermine e maxtermine, viste in LogicBignami (IV):
| Mintermine (o Minterm)
|
|---|
| E' una funzione booleana associata ad ogni combinazione delle variabili d'ingresso: equivale al prodotto logico di queste variabili, complementate se corrispondenti ad uno stato logico 0 altrimenti non complementate, in modo da fornire, come risultato, sempre uno stato logico 1.
|
| Maxtermine (o Maxterm)
|
|---|
| E' una funzione booleana associata ad ogni combinazione delle variabili d'ingresso: equivale alla somma logica di queste variabili, complementate se corrispondenti ad uno stato logico 1 altrimenti non complementate, in modo da fornire, come risultato, sempre uno stato logico 0.
|
Quindi, quando parleremo di mintermine ci riferiremo agli stati logici 1 della funzione booleana, viceversa, quando parleremo di maxtermine ci riferiremo agli stati logici 0 della medesima funzione booleana.
Nella realizzazione delle griglie la disposizione dei mintermini (o maxtermini) è tale che, considerata una casella in una posizione arbitraria sulla griglia stessa, lo spostamento di una posizione (alto/basso o sinistra/destra) comporta il cambiamento di stato logico di un'unica variabile booleana all'interno del mintermine (o maxtermine) contenuto nella casella scelta (in pratica la distanza di Hamming, intesa come il numero di sostituzioni che intervengono nel mintermine (o maxtermine), nel passaggio tra due caselle adiacenti, è pari a 1).
Quindi considerando il seguente esempio, partendo dalla casella centrale che contiene il mintermine 
, quando ci spositamo verso l'alto, varia solo lo stato di , quando ci spostiamo verso il basso, varia solo lo stato di , quando ci spostiamo a sinistra, varia lo stato di e quando ci spostiamo verso destra, varia lo stato di .
Questa particolarità costruttiva si ottiene impostando il cambiamento di stato logico, nelle coppie di variabili booleane che "indicizzano" le colonne della griglia (e anche per quelle che "indicizzano" le righe, per le mappe di Karnaugh a 4 e 5 variabili booleane), secondo una particolare "forma" detta Codice Gray (Questo codice sarà approfondito in altri articoli quando verranno trattati i circuiti di codifica), dove, appunto, nel passaggio da una combinazione di stati logici alla successiva (o alla precedente), si ha il cambiamento di stato di un'unica variabile booleana alla volta:
Quindi le griglie corrispondenti alle tabelle della verita da 3 a 5 variabili booleane, evidenziando la posizione relativa dei singoli mintermini (o maxtermini), sono le seguenti:
Mappa di Karnaugh per 3 variabili booleane
mappa mintermini
mappa maxtermini
Le mappe di Karnaugh per 3 variabili booleane esistono in due versioni perchè la suddivisione in righe e colonne, delle variabili stesse, considerate con indice crescente è dupplice: e oppure e 
.
Mappa di Karnaugh per 4 variabili booleane
mappa mintermini
mappa maxtermini
Mappa di Karnaugh per 5 variabili booleane
mappa mintermini
mappa maxtermini
In realtà le mappa di Karnaugh per 5 variabili booleane non vanno considerate come una griglia "piana" ma come due griglie di 16 caselle sovrapposte come rappresentato nella seguente immagine:
Una particolarità delle mappe di Karnaugh è che le griglie devono essere considerate chiuse su se stesse, in particolare:
Nelle mappe di Karnaugh per 3 variabili booleane i bordi sinistro e destro coincidono, quindi spostandosi a destra della colonna (10) si rientra nella colonna (00) e, viceversa, spostandosi a sinistra della colonna (00) si rientra nella colonna (10).
In pratica possiamo pensare la mappa come "avvolta" a formare una figura cilindrica verticale.
Nelle mappe di Karnaugh per 4 variabili booleane, oltre ai bordi sinistro e destro, anche i bordi superiore ed inferiore coincidono, quindi spostandosi in alto sopra la riga (00) si rientra in basso nella riga (10) e, viceversa, spostandosi in basso sotto la riga (10) si rientra in alto nella riga (00).
In questo caso possiamo pensare la mappa sempre "avvolta" come un cilindro, questa volta orizzontale, che si richiude e formare una figura toroidale
Nelle mappe di Karnaugh per 5 variabili booleane, abbiamo una figura toroidale per ciascuna delle due griglie (quella per 
e quella per 
) e questi toroidi sono da considerare uno all'interno dell'altro, con le singole caselle corrispondenti sovrapposte, come abbiamo visto precedentemente.
Le mappe di Karnaugh: utilizzo
E' la particolare disposizione dei mintermini (o maxtermini) sulla mappa di Karnaugh, appena descritta, che ci permette di eseguire una riduzione immediata della funzione booleana, e per far ciò si deve seguire il seguente procedimento:
Raggruppare i mintermini, o i maxtermini
La scelta di cosa raggruppare dipende se, alla fine, si vuole ottenere una funzione booleana che sia una somma logica di prodotti logici, allora si raggrupperanno i mintermini, oppure un prodotto logico di somme logiche, allora si raggrupperanno i maxtermini.
Ogni raggruppamento rappresenterà un termine prodotto logico, se sono stati considerati i mintermine, oppure un termine somma logica, se sono stati considerati i maxtermine, di cui sarà composta la nostra funzione booleana ridotta.
I raggruppamenti possibili devono essere composti da un numero di caselle, adiacenti, pari a potenze di 2, quindi avremo queste casistiche:
a) Una sola casella, il raggruppamento da una sola casella implica che il mintermine (o maxtermine), contenuto nella stessa, non è, di fatto riducibile, ossia l' implicante (o l' implicato) che otterremo sarà comunque composto da tutte le variabili della funzione booleana
b) 2 caselle, poste in orizzontale o verticale
c) 4 caselle, poste in linea orizzontale o verticale, o a formare un quadrato
Queste tre tipologie di raggruppamenti valgono per tutte le mappe di Karnaugh, ma, per quella a 5 variabili booleane vedremo che possono essere eseguiti anche attraverso i "due piani" della mappa stessa.
Esistono poi un altro caso applicabile solo alle mappe di Karnaugh a 4 e 5 variabili booleane:
d) 8 caselle, equivalenti a 2 linee orizzontali o verticali affiancate (o sovrapposte sui "due piani" della mappa, per la versione a 5 variabili booleane) oppure da 2 quadrati da 4 caselle sovrapposti sui "due piani" della mappa, valido solo per la versione a 5 variabili booleane
e uno valido solo per le mappe di Karnugh a 5 variabili boolaene:
e) 16 caselle, equivalenti a 2 gruppi formati da 2 linee orizzontali o verticali affiancate, sovrapposti sui "due piani" della mappa, oppure, tutte le 16 caselle di uno dei "due piani".
Come analizzeremo in seguito, quando una tabella della verità ha un numero di mintermini (o maxtermini) pari alla metà delle possibili combinazioni delle variabili booleane considerate, in una configurazione tale da determinare, sulla realtiva mappa di Karnaug, un unico raggruppamento pari alla metà delle caselle disponibili, allora la funzione booleana d'uscita coincide con una delle variabili booleane d'ingresso.
Di seguito vediamo come si realizzano i suddetti raggruppamenti:
b) Raggruppamenti a 2 caselle:
c) Raggruppamenti a 4 caselle:
d) Raggruppamenti a 8 caselle
Da notare che tutti i raggruppamenti segnati in blu sulle griglie, sono possibili perchè, come si è detto in precedenza, le mappe di Karnaugh sono chiuse su se stesse.
Inoltre tutti i raggruppamenti illustrati nelle mappe di Karnaugh per 3 variabili booleane sono da intendersi applicabili anche su quelle di ordine superiore (a 4 o 5 variabili booleane).
Sulle mappe di Karnaugh a 5 variabili booleane, per la loro particolare struttura bidimensionale, è possibile formare raggruppamenti anche attraverso i "due piani" di griglia, purchè le celle utilizzate abbiano, su ogni singola grilgia, la medesima "indicizzazione" delle variabili booleane:
Nota: Nelle seguenti immagini, piane per semplificare le viste, le due griglie, riferite a e sono da considerarsi sovrapposte come indicato in precedenza.
Ecco alcuni esempi di raggruppamenti su mappe di Karnaugh a 5 variabili:
b) Raggruppamento a 2 caselle
c) Raggruppamenti a 4 caselle
d) Raggruppamenti a 8 caselle
e) Raggruppamento di 16 caselle
Anche sulle mappe di Karnaugh a 5 variabili, i raggruppamenti segnati in blu sono possibili perchè le mappe risultano chuse su se stesse.
I raggruppamenti vanno sempre fatti a partire dal massimo numero possibile di caselle, per quello che permette la disposizione dei mintermini (o maxtermini) sulla griglia, scendendo, via via, di numero in modo da includere tutti i termini presenti, perchè determinano la miglior riduzione della funzione booleana corrispondente:
Per la proprietà dell'idempotenza, vista in LogicBignami (II), per realizzare raggruppamenti con un numero maggiore di caselle, è possibile utilizzare mintermini (o maxtermini) comuni in raggruppamenti distinti:
Fondamentalmente entrambe le tipologie di raggruppamento sono corrette ma, quella di destra, raggruppando più caselle in meno gruppi, permette di ottenere una funzione booleana più ridotta.
Quando si ha l'opportunità di utilizzare gli stessi mintermini (omaxtermini) in più raggruppamenti, e sussiste la possibilità di avere più opportunità di scelta, a parità di numero di celle ragguppabili, se ne dovrà scegliere una sola delle due.
In questo caso si dovrà scegliere o il raggruppamento azzurro o quello rosso, non entrambi.
Analizzare le variabili booleane invarianti
Una volta stabilito come devono essere effettuati raggruppamenti di mintermini (o maxtermini) sulla griglia, si deve analizzare, all'interno dei gruppi selezionati, quale , o quali variabili booleane mantengono fisso il loro stato logico: queste rappresenteranno l' implicante (o l' implicato) che andranno a formare la funzione booleana ridotta.
Prendiamo, ad esempio, le ultime due mappe di Karnaugh illustrate e vediamo, applicando quanto detto, che funzioni booleane ricaviamo:
Avendo considerato i mintermini, la funzione booleana sarà una somma logica di prodotti logici, e analizzando i diversi raggruppamenti, otteniamo i seguenti implicanti:
1) Raggruppamento rosso: una sola casella, l' implicante corrispondente al mintermine della casella stessa, quindi 
2) Raggruppamento blu: 2 caselle, le variabili booleane con stato logico fisso sono , e : essendo in stato logico 0, e dovendo costituire un implicante, le dovremo considerare complementate, per cui avremo il corrispondente 
3) Raggruppamento verde: 4 caselle, qui le variabili booleane con stato logico fisso sono e e solo quest'ultima, essendo in stato logico 0, sarà complementata, quindi l' implicante corrispondente sarà 
da cui risulta la funzione booleana: 
Analizziamo adesso la medesima mappa di Karnaugh ma dove sono stati realizzati raggruppamenti di caselle maggiori:
1) Raggruppamento rosso: 2 caselle, le variabili booleane con stato logico fisso sono , e , ed essendo tutte in stato logico 1 determinano il corrispondente implicante 
2) Raggruppamento blu: 4 caselle, le variabili booleane che non variano di stato sono e : essendo in stato logico 0, e dovendo costituire un implicante, le dovremo considerare complementate, per cui avremo il corrispondente 
3) Raggruppamento verde: 4 caselle, è rimasto invariato rispetto alla precedente mappa di Karnaugh quindi l' implicante corrispondente sarà sempre
da cui, questa volta, ricaviamo la funzione booleana: 
Per verificare che le due funzioni booleane generino, effettivamente, gli stessi stati logici, ricaviamo la tabella della verità per entrambe (per meglio evidenziare ho riprodotto anche gli stati logici intermedi degli implicanti di ognuna delle due funzioni booleane):
Possiamo notare che entrambe le funzioni booleane sono costituite dalla somma logica di 3 implicanti ma la seconda, proprio in virtù di raggruppamenti con un maggior numero di caselle, ha implicanti con un numero inferiore di variabili booleane, il che si traduce in una semplificazione circuitale come dimostrato negli schemi circuitali delle due dove, tra l'altro, notiamo che il "circuito B", relativo alla funzione booleana maggiormente ridotta, utilizza anche una porta logica NOT in meno (quella relativa alla linea 
:
Vediamo, adesso, perchè, con un raggruppamento pari alla metà delle caselle disponibili su una qualsiasi mappa di Karnaugh, la funzione booleana relativa è immediatamente ricavabile senza l'uso della mappa stessa ma, direttamente dall'analisi della tabella della verità relativa.
Consideriamo una tabella della verità a 4 variabili, e quindi la relativa mappa di Karnaugh, ma il discorso vale anche per le altre:
Come si vede, senza scomodare la relativa mappa di Karnaugh, o qualsiasi altro metodo di riduzione, la funzione booleana 
altro non è che la variabile booleana d'ingresso .
Infatti, volendo analizzare comunque il raggruppamento da 8 caselle, l'unica variabile booleana che non varia di stato logico è, appunto, .
Riduzione diretta di una funzione booleana
Vediamo, infine, come compilare una mappa di Karnaugh partendo direttamente dalla funzione booleana, al fine di stabile se questa può essere ridotta oppure no.
Supponiamo di avere la seguente funzione booleana: 
.
Ricaviamo la relativa mappa di Karnaugh a 4 variabili, inserendo uno stato logico 1 nelle caselle corrispondenti agli implicanti riportati nella funzione logica (non essendo in formato canonico considero tutti i termini come implicanti).
Gli implicanti, che non sono composti da tutte e 4 le variabili booleane, determineranno uno stato logico 1, sulla mappa di Karnaugh, in tutte le caselle "indicizzate" dal prodotto logico dell' implicante considerato:
Ad esempio, per l' implicante si dovrà inserire uno stato logico 1 in tutte le seguenti caselle:
,
,
,
.
In pratica è lo stesso procedimento di risalire alla forma canonica della funzione booleana vista in LogicBignami (VI), solo che in questo caso viene fatto direttamente senza alcun passaggio matematico.
Quindi la nostra mappa di Karnaugh sarà la seguente:
dove:
- le caselle relative all' implicante 
sono in rosso;
- la casella relativa all' implicante 
è in verde;
- le caselle relative all' implicante 
sono in blu.
A questo punto eseguiamo i raggruppamenti secondo le regole poc'anzi citate, ottenendo 2 gruppi da 4 caselle (segnati in blu e verde) e un gruppo da 2 caselle (segnato in rosso):
Analizzando quali variabili booleane, all'interno di tali gruppi, non variano di stato logico, otteniamo i seguenti implicanti che comporranno la nostra funzione booleana ridotta:
- raggruppamento blu:
- raggruppamento rosso: 
- raggruppamento verde:
Quindi, alla fine, la nostra funzione ridotta risulterà essere: 
Con questo abbiamo concluso questa lunga chiacchierata sulle mappe di Karnaugh, nel prossimo articolo analizzeremo l'altro sistema di riduzione, il metodo della tabulazione o di Quine-McCluskey.
