Cos'è ElectroYou | Login Iscriviti

ElectroYou - la comunità dei professionisti del mondo elettrico

7
voti

LogicBignami (VIII)

Indice

La riduzione, o minimizzazione, delle funzioni booleane (terza parte)

Dopo aver visto la riduzione di una funzione booleana mediante il metodo algebrico (LogicBignami (VI)) e mediante il metodo "grafico" delle mappe di Karnaugh (LogicBignami (VII)) analizziamo, adesso, un metodo, cosiddetto "tabellare", il Quine-McCluskey.

PREMESSA

Questo metodo non rientrava nel mio percorso di studi da Istituto Tecnico Industriale, per cui, prima di riassumerlo l'ho dovuto studiare io stesso.
Se trovate qualche lacuna o mancanza siete invitati a segnalarlo, tenendo presente che il target di questi miei articoli sono, comunque, studenti delle superiori e appassionati.

Grazie.


Questo metodo si presta ad essere tradotto in una routine da far svolgere ad un elaboratore dati, questo permette la riduzione di una funzione booleana con un numero qualsiasi (*) di variabili booleane, a differenza del metodo utilizzante le mappe di Karnaug che, come abbiamo detto nel precedente articolo LogicBignami (VII), oltre le 5 variabili booleane si complica eccessivamente.

(*) In realtà le tempistiche per la soluzione del problema di riduzione della funzione booleana con il metodo Quine-McCluskey cresce in maniera esponenziale all'aumentare del numero di variabili booleane da trattare, tant'è che, al di spora della decina di variabili booleane, convengono altri sistemi di riduzione di tipo euristico, la cui descrizione, però, esula l'impostazione data a questa serie di articoli divulgativi.

Il metodo di Quine - McCluskey si applica a funzioni booleane sottoforma di somma logica di prodotti logici e consta, essenzialmente, di due passaggi principali:

1) Eliminare più variabili booleane possibili dai singoli termini prodotto logico applicando ripetutamente la regola:

K \cdot Y + K \cdot \overline {Y} = K

dove

K \cdot Y \; e K \cdot \overline Y \; rappresentano due termini prodotto logico che differiscono unicamente per una variabile booleana, Y \;, che, in un termine sarà normale e nell'altro risulterà complementata.

Ad esempio, considerando i due termini

I_0 \; \overline {I_1} \; I_2 \; \overline {I_3}

I_0 \; \overline {I_1} \; I_2 \; I_3

notiamo che i due differiscono solo per la variabile booleana I_3 \; che, in un termine è normale e nell'altro è negata, per tanto, applicando la suddetta regola otterremo:

Da notare che il risultato a cui porta questa regola non cì è nuovo, in quanto l'avevamo già visto in LogicBignami VI con la riduzione algebrica delle funzioni booleane, con l'applicazione della proprietà distributiva, della regola della complementarietà e della regola dell'elemento neutro.

Il termine K \;, risultato della semplificazione reiterata, quando non risulta più riducibile con nessun altro termine prodotto logico, prende il nome di implicante primo.

2) Usare una grafico che ci permette di selezionare il minimo numero di implicanti primi che, sottoposti a somma logica, forniscono la stessa funzione logica booleana di partenza con un numero ridotto di termini e variabili booleane.


La ricerca degli implicanti primi

Come abbiamo detto il metodo Quinde - McCluskey si applica a funzioni booleane somma logica di prodotti logici, e, nello specifico, in formato canonico (nel caso la funzione booleana non sia in tale formato, la si può ricavare secondo quanto visto in LogicBignami VI).

Il formato canonico ci permette di analizzare tutte le possibili copie di mintermini alle quali sia possibile applicare la regola appena citata:

K \cdot Y + K \cdot \overline {Y} = K

Vediamo allora come trovare tutti gli implicanti primi, ossia tutti i termini prodotto logico ridotti al minimo numero di variabili booleane possibile.

Innanzi tutto si costruisce una tabella suddividendo i mintermini, della funzione booleana da ridurre, in gruppi in base al numero di variabili booleane in stato logico 1 \;.
In pratica avremo:

- il gruppo 0 conterrà il mintermine con tutte le variabili booleane in stato logico 0
- il gruppo 1 conterrà tutti i mintermini con una variabile booleana in stato logico 1
- il gruppo 2 conterrà tutti i mintermini con due variabili booleane in stato logico 1
- il gruppo 3 conterrà tutti i mintermini con tre variabili booleane in stato logico 1
- ... e così via fino al gruppo n, dove "n" è il numero delle variabili booleane presenti nei mintrmini della funzione booleana da ridurre, che conterrà il mintermine con tutte le variabili booleane in stato logico 1

Come si è detto questa tabella conterrà solo i mintermini di cui è composta la nostra funzione booleana da ridurre, quindi, non è detto che tutti i gruppi sopra indicati contengano dei termini.

Facciamo un esempio, consideriamo la seguente tabella della verità è ricabimone la funzione booleana in formato canonico:

Dalla sommatoria dei mintermini in stato logico 1 \;, evidenziati in rosso, deriva la seguente funzione booleana in formato canonico:

O = \overline {I_0} \; \overline {I_1} \; \overline {I_2} \; \overline {I_3} + I_0 \; \overline {I_1} \; \overline {I_2} \; \overline {I_3} + \overline {I_0} \; I_1 \; \overline {I_2} \; \overline {I_3} + I_0 \; \overline {I_1} \; I_2 \; \overline {I_3} + \overline {I_0} \; I_1 \; I_2 \; \overline {I_3} +
 + I_0 \; I_1 \; I_2 \; \overline {I_3} + \overline {I_0} \; \overline {I_1} \; \overline {I_2} \; I_3 + 
I_0 \; \overline {I_1} \; \overline {I_2} \; I_3 + \overline {I_0} \; I_1 \; \overline {I_2} \; I_3 + \overline {I_0} \; I_1 \; I_2 \; I_3

Raggruppiamo, allora, questi mintermini, in gruppi come li abbiamo poc'anzi definiti:

Con questa tabella possiamo notare che i termini prodotto logico da comparare devono appartenere per forza a due gruppi adiacenti (0 e 1, 1 e 2, 2 e 3) perchè solo in questo frangente si può riscontrare che, tra quello appartenente ad un gruppo e quello del gruppo immediatamente successivo, sussiste la variazione di stato logico di un'unica variabile booleana.

Iniziamo, quindi a comparare il mintermine m_0 \;, del gruppo 0, con i mintermini m_1 \;, m_2 \; e m_8 \; del gruppo 1.

Come possiamo notare tutte le coppie [m_0 \; m_1] \;, [m_0 \; m_2] \; e [m_0 \; m_8] \; differiscono tutte per lo stato logico di un'unica variabile booleana (rispettivamente I_0 \;, I_1 \; e I_3 \;).

Applicando, allora, a queste coppie di mintermini, la regola K \cdot Y + K \cdot \overline {Y} = K \;, possiamo ricavare la seguente tabella, dove le variabili booleane eliminate dai mintermini sono state marcate con un - \;:

In questa tabella, con i termini K_{[a,b]} \; si intendono gli implicanti derivanti dal confronto dei mintermini m_a \; e m_b \;.

A questo punto passiamo al gruppo 1 e confrontiamo ogni suo mintermine con quelli presenti nel gruppo 2 in modo da trovare tutte le possibili coppie che differiscono per lo stato logico di un'unica variabile booleana, operando come abbiamo appena visto nel confornto tra il gruppo 0 e il gruppo 1, e lo stesso facciamo confrontando ogni mintermine del gruppo 2 con quelli appartenenti al gruppo 3.

Alla fine otterremo una seconda tabella così composta:

E' utile evidenziare i mintermini che sono stati accoppiati almeno una volta (qui sono stati segnati con un asterisco) perchè quelli che non possono essere accoppiati, quindi quelli che non possono essere ridotti, saranno degli implicanti primi e finiranno, così come sono, nella formula della funzione booleana che sarà poi analizzata tramite il grafico degli implicanti primi.

Prendiamo, allora, questo secondo gruppo di tabelle di implicanti e ripetiamo i passaggi appena visti confrontando, questa volta, gli implicanti appartenenti a gruppi adiacenti, sempre al fine di trovare le coppie che differiscono per lo stato logico di un'unica variabile booleana.

Il confronto tra le diverse coppie di implicanti può risultare più semplice se si considera anche il simbolo - \; come elelmento dell'implicante stesso:

Ad esempio, se confrontiamo la coppia K_{[0, \; 1]} \; e K_{[8, \; 9]} risulta subito evidente che l'unica variabile che differisce di stato logico è I3

Quindi, come detto, ripetendo i passaggi di confronto e riduzione, anche sui gruppi della tabella di implicanti appena ottenuta, ricaviamo questa ulteriore tabella formata da due soli gruppi, dove con K_{[a,b] \;[c,d]} \; evidenziamo le coppie di implicanti K_{[a,b]} \; e K_{[c,d]} \; ridotte:

Gli implicanti possono anche essere rappresentati solo includendo all'interno delle parentesi l'elenco dei mintermini che essi riducono: [a, b, c, d].
Questo è sicuramente vantaggioso quando il numero delle semplificazioni aumenta.

Vediamo che tre implicanti (indicati dalla freccia blu), K_{[1, \;5]} \; equivalente a I_0 \; \overline I_1 \; \overline I_3 \;, K_{[5, \;7]} \; equivalente a I_0 \; I_2 \; \overline I_3 \; e K_{[6, \;7]} \; equivalente a I_1 \; I_2 \; \overline I_3 \; non fanno coppia con nessun altro implicante appartenente ad un gruppo adiacente, per cui, non potendo più essere ridotti, sono degli implicanti primi e finiranno direttamente nella formula della funzione booleana con questo "livello" di riduzione.

Nell'ultima tabella, formata da due soli gruppi di implicanti, vediamo che non è possibile trovare delle coppie confrontabili che differiscano solamente per lo stato logico di un'unica variabile booleana, quindi ognuno di essi è un implicante primo.

In pratica quando non è più possibile trovare coppie di implicanti riducibili, il processo di confronto si arresta e tutti gli implicanti rimasti saranno considerati implicanti primi.

Notiamo, inoltre, la presenza, nel primo gruppo, di due coppie di implicanti uguali e, nel secondo gruppo di una coppia di implicanti uguali (indicati con le lettere a-a, b-b e c-c): nella funzione booleana ne verrà inserito uno solo di ognuna, in virtù della regola dell'idempotenza vista in LogicBignami II.

Quindi la nostra funzione booleana ridotta equivarrà alla somma logica di tutti gli implicanti primi risultanti dalle suddette tabelle:

O = I_0 \; \overline I_1 \; \overline I_3 + I_0 \; I_2 \; \overline I_3 + I_1 \; I_2 \; \overline I_3 + \overline I_0 \; I_1 + \overline I_0 \; \overline I_2 + \overline I_1 \; \overline I_2

Rispetto alla funzione booleana di partenza, questa potrebbe sembrare già ridotta, in realtà si può notare, che diversi termini contengono variabili booleane con il medesimo stato logico e quindi potrebbero essere, in parte, ulteriormente ridotti.

Infatti la sola ricerca degli implicanti primi porta ad una funzione booleana che contiene termini che hanno il minor numero di variabili booleane possibile, per singolo termine, ma non il minor numero di termini possibile.

Per ottenere la funzione booleana ridotta finale, sia come variabili booleane manipolate che come numero di termini che la compongono, si deve procedere con il secondo passo del metodo Quine-McCluskey, ossia utilizzare il grafico degli implicanti primi.

Utilizzo del grafico degli implicanti primi

Dopo aver visto come trovare tutti gli implicanti primi, mostriamo adesso il metodo per estrarre da questi il minimo numero di termini che ci permetteranno di esprimere la medesima funzione logica di partenza.

Per far ciò dobbiamo costruire un grafico dove metteremo in relazione gli implicanti primi, a cui assegneremo le righe del grafico, con i relativi mintermini della funzione booleana di partenza, a cui assegneremo le colonne.

Riprendiamo allora la nostra funzione booleana, in formato canonico, utilizzata all'inizio dell'esempio:
O = \overline {I_0} \; \overline {I_1} \; \overline {I_2} \; \overline {I_3} + I_0 \; \overline {I_1} \; \overline {I_2} \; \overline {I_3} + \overline {I_0} \; I_1 \; \overline {I_2} \; \overline {I_3} + I_0 \; \overline {I_1} \; I_2 \; \overline {I_3} + \overline {I_0} \; I_1 \; I_2 \; \overline {I_3} +
 + I_0 \; I_1 \; I_2 \; \overline {I_3} + \overline {I_0} \; \overline {I_1} \; \overline {I_2} \; I_3 + 
I_0 \; \overline {I_1} \; \overline {I_2} \; I_3 + \overline {I_0} \; I_1 \; \overline {I_2} \; I_3 + \overline {I_0} \; I_1 \; I_2 \; I_3

che corrisponde alla sommatoria dei seguenti mintermini che, come detto, rappresenteranno gli indici delle colonne del nostro grafico:

O = m0 + m1 + m2 + m5 + m6 + m7 + m8 + m9 + m10 + m14

Mentre, come abbiamo visto, gli implicanti primi, di questa funzione logica sono:

K_{[1,5]} = I_0 \; \overline I_1 \; \overline I_3
K_{[5,7]} = I_0 \; I_2 \; \overline I_3
K_{[6,7]} = I_1 \; I_2 \; \overline I_3
K_{[0,1][8,9]} = \overline I_1 \; \overline I_2
K_{[0,2][8,10]} = \overline I_0 \; \overline I_2
K_{[2,6][10,14]} = \overline I_0 \; I_1

che rappresenteranno, invece, gli indici delle righe del grafico, che, a questo punto, avrà il seguente aspetto:

Ricordiamo che l'implicante, qualsiasi, K_{[a,b][c,d]...} \; è derivato dalla semplificazione della somma logica di mintermini indicati dai "pedici", così, ad esempio:

K[0,1][8,9] = K[0,1] + K[8,9] = (m0 + m1) + (m8 + m9) =
= (\overline {I_0} \; \overline {I_1} \; \overline {I_2} \; \overline {I_3} + I_0 \; \overline {I_1} \; \overline {I_2} \; \overline {I_3}) + (\overline {I_0} \; \overline {I_1} \; \overline {I_2} \; I_3 + I_0 \; \overline {I_1} \; \overline {I_2} \; I_3) = \overline {I_1} \; \overline {I_2}

Nota: Ho tralasciato i passaggi intermedi della semplificazione in quanto già visti più volte, e quindi dovrebbero già essere assimilati.

Per questo, nel suddetto grafico, aggiungiamo una "x" per segnare, in ogni riga "puntata" da ogni implicante primo, quali mintermini ha ridotto:

ad esempio, nella riga relativa a K_{[0,1][8,9]} \; metteremo una "x" nelle colonne dei mintermini m_0 \; m_1 \; m_8 \; m_9

Il nostro grafico risulterà, allora, così compilato e completo:

A questo punto possiamo iniziare la fase di semplificazione: per prima cosa controlliamo se esistono colonne con un'unica "x", se esistono, l'implicante primo, della riga corrispondente a dove è presente quell'unica "x", diventa essenziale, perchè è l'unico che riduce quel mintermine la cui colonna contiene quell'unica "x".

Gli eventuali implicanti primi essenziali così trovati finiscono direttamente nella formula finale della nostra funzione booleana ridotta.

Nel nostro grafico vediamo che ci sono due colonne che hanno un'unica "x" (evidenziate con una cerchiatura), quella relativa al mintermine m_9 \; e quella relativa al mintermine m14.

In particolare:

- Alla "x" della colonna m_9 \; corrisponde la riga dell'implicante primo K_{[0,1][8,9]} = \overline I_1 \; \overline I_2
- Alla "x" della colonna m_14 \; corrisponde la riga dell'implicante primo K_{[2,6][10,14]} = \overline I_0 \; I_1

questi diventano, quindi, implicanti primi essenziali e entrano direttamente nella formula della funzione booleana ridotta: O = \overline I_1 \; \overline I_2 + \overline I_0 \; I_1 + ...

Selezionati gli eventuali implicanti primi essenziali, dal grafico vanno eliminati tutti gli elementi presenti sulle loro righe, come indicato di seguito:

Inoltre, in corrispondenza di ognuna di queste "x" eliminate nelle righe indirizzate dagli implicanti primi essenziali, elimineremo anche tutti gli elementi presenti nella corrispondente colonna, come evidenziato nella figura con le righe verticali verdi:

Da questo grafico, possiamo osservare che sono rimaste, non eliminate, due coppie di "x" appartenenti ai due mintermini m_5 \; e m_7 \;:

- Le due "x" del mintermine m_5 \; ci indicano che quest'ultimo è ridotto dagli implicanti primi K_{[1,5]} \; e K_{[5,7]} \;
- Le due "x" del mintermine m7, invece, ci indicano che quest'ultimo è ridotto dagli implicanti primi K_{[5,7]} \; e K_{[6,7]} \;


Di questi implicanti primi, vediamo che uno, K_{[5,7]} \;, ha entrambe queste "x" sulla sua riga: in pratica, dei tre citati, è l'unico a ridurre contemporaneamente sia il mintermine m_5 \; che il mintermine m_7 \; (cancellati dalla linea magenta), e, come abbiamo visto in precedenza, a questo punto possiamo eliminare anche gli altri elementi presenti nelle colonne m_5 \; e m_7 \; (linee verdi).

L'implicante primo K_{[5,7]} = I_0 \; I_2 \; \overline I_3 \; diventa l'ultimo termine nella nostra formula ridotta della funzione booleana:

O = \overline I_1 \; \overline I_2 + \overline I_0 \; I_1 + I_0 \; I_2 \; \overline I_3

Per verificare che, effettivamente, questa funzione booleana ridotta, copra tutti gli stati logici di quella in formato canonico, possiamo ricavarne la tabella della verità confrontandone gli stati logici d'uscita con quelli presenti nella tabella della verità di partenza:

Come si può vedere gli stati logici sono esattamente gli stessi.

Prima di concludere la trattazione del metodo Quine-McCluskey, analizziamo un caso particolare che non porta ad una riduzione unica.


Il grafico degli implicanti primi, ciclico

Supponiamo di avere la seguente tabella della verità:

La funzione booleana d'uscita, come somma logica di prodotti logici, è, come sappiamo, la somma dei seguenti mintermini: O = m0 + m1 + m2 + m5 + m6 + m7.

Come fatto in precedenza, cerchiamo gli implicanti primi, suddividendo questi mintermini in gruppi e cercando, tra questi, le possibili riduzioni:

Tutti i mintermini riescono ad essere ridotti negli implicanti riportati nella tabella di destra ma, nessuno di questi può essere ulteriormente ridotto, infatti nessun implicante di un gruppo "trova" nel gruppo adiacente un altro che differisca per lo stato logico di un'unica variabile booleana: per tanto tutti questi diventeranno implicanti primi.

Costruiamoci, allora, il grafico degli implicanti primi:

La prima cosa che salta all'occhio analizzando questo grafico è che, in nessuna colonna, è presente un'unica "x", ciò vuol dire che nessun implicante primo è un implicante primo essenziale.

Per ridurre il numero degli implicanti primi da inserire nella funzione booleana ridotta, a questo punto dovremmo cercare quelli che riducono, contemporaneamente più mintermini, in pratica dobbiamo vedere in quali righe sono presenti più "x".

Come si può vedere ogni riga contiene due "x": quindi non c'è un unico risultato di riduzione.

Potremmo, ad esempio, scegliere gli implicanti primi K_{[0, 1]} \;, K_{[2, 6]} \; e K_{[5, 7]} \; in base alla seguente riduzione grafica:

e quindi ottenere la funzione booleana ridotta, come somma logica di tali implicanti primi:

O = \overline {I_1} \; \overline {I_2} + \overline {I_0} \; I_1 + I_0\;I_2

ma potremmo, ugualmente scegliere gli implicanti primi K_{[0, 2]} \;, K_{[1, 5]} \; e K_{[6, 7]} \; operando quest'altra riduzione grafica:

e otterremo, comunque, una funzione booleana validamente ridotta, come somma logica di tre termini:

O = \overline {I_0} \; \overline {I_2} + I_0 \; \overline {I_1} + I_1 \; I_2

Visto quest'ultimo esempio, abbiamo terminato la disamina della riduzione delle funzioni booleane anche con il metodo Quine-McCluskey.

Prima di analizzare alcuni circuiti combinatori d'uso comune e, per questo, realizzati anche come singolo componente elettronico integrato, vedremo, nel prossimo articolo, i sistemi di numerazione binaria e le principali operazioni ad esso collegate.


LogicBignami - Indice articoli correlati

3

Commenti e note

Inserisci un commento

di ,

Immagino.. immagino .. quando ho scritto le mie piccole esposizioni in EY, era anche per me un metodo per riprendere i "sacri testi" e rinfrescare la teoria sopita , pertanto ti comprendo ..

Rispondi

di ,

... e non ti immagini quanto mi sta piacendo questo ripasso!!!

Rispondi

di ,

E bravo Max2433BO ..

Max2433BO ha scritto:
prima di riassumerlo l'ho dovuto studiare io stesso.
.. ti sei ridato allo studio dell'Elettronica digitale .. ..

Rispondi

Inserisci un commento

Per inserire commenti è necessario iscriversi ad ElectroYou. Se sei già iscritto, effettua il login.