Cos'è ElectroYou | Login Iscriviti

ElectroYou - la comunità dei professionisti del mondo elettrico

6
voti

LogicBignami (VIII) - Addendum

Indice

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

Era mia intenzione trattare il seguente argomento quando se ne fosse presentata l'opportunità durante l'illustrazione del funzionamento di alcuni circuiti di logica combinatoria (soprattutto nei decodificatori), ma poi ho ritenuto più opportuno, per non disperdere troppo la teoria, di inserire questo capitolo come "addendum" nella serie sulla riduzione delle funzioni booleane.

Le condizioni indifferenza (o don't care)

Negli ultimi tre articoli (LogicBignami (VI), LogicBignami (VII) e LogicBignami (VIII)) abbiamo visto tre metodi che ci permettono di attuare la riduzione di una funzione booleana in formato canonico.

Fino ad ora abbiamo considerato tabelle della verità in cui gli stati logici relativi alla funzione booleana d'uscita erano o a 0 \; logico (stato logico "falso") o a 1 \; logico (stato logico "vero").

Nella realtà vedremo che esistono dei casi che, per una o più combinazioni delle variabili booleane d'ingresso, lo stato logico della funzione booleana d'uscita non abbia importanza: essa potrebbe essere considerata indifferentemente a stato logico 0 \; o a stato logico 1 \;, da cui il nome di condizione d'indifferenza o don't care condition.

Supponiamo di avere un commutatore a dieci posizioni con 4 \; sezioni e 4 \; uscite, con interruttori che chiudono sull'ingresso I \; seguendo lo schema qui sotto riportato:

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Questo tipo di commutatore, in pratica, permette la conversione delle cifre decimali da 0 \; a 9 \;, interpretate dalla posizione del contatto di commutazione, con le corrispondenti prime 10 \; combinazioni ottenibili con 4 \; variabili booleane (analizzeremo nei prossimi articoli i sistemi numerici e la conversione da uno all'altro sistema).

Se associassimo la lettera O \; per indicare il contatto aperto e la lettera C \; per indicare il contatto chiuso, rispetto all'ingresso I \;, otterremo la seguente tabella (a sinistra) che, come si può notare, risulta identica alla prima parte della tabella della verità per 4 \; variabili booleane (a destra) se considerassimo C \; come stato logico 1 \; e O \; come stato logico 0 \;:

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Però sappiamo che, per 4 \; variabili booleane, si ottengono 2^4 = 16 \; combinazioni diverse, quindi le prime 10 \; corrispondono alle posizioni del commutatore ma le restanti 6 \; rimarrebbero inutilizzate (evidenziate in rosso nella tabella della verità qui sopra).

Quindi, in questo caso, in corrispondenza di queste combinazioni, non potendo mai capitare (gli stati di commutazione non le comprendono), lo stato logico assunto dalla funzione booleana d'uscita può essere, indifferentemente, 1 \; oppure 0 \;.

Per identificare lo stato logico di indifferenza, di norma, in corrispondenza di queste combinazioni delle variabili booleane d'ingresso, la funzione booleana d'uscita viene contrassegnata con la lettera X \;.

Questi stati logici indifferenza verranno considerati come stato logico 1 \; o come stato logico 0 \; a seconda di come decideremo di esprimere la nostra funzione booleana d'uscita in formato canonico:

- Se intendiamo esprimerla come somma logica di prodotti logici, cioè come somma logica di mintermini, gli stati logici indifferenza saranno considerati come 1 \; logico e le relative combinazioni di variabili booleane d'ingresso, come mintermini.

- Se intendiamo, invece, esprimerla come prodotto logico di somme logiche, cioè come prodotto logico di maxtermini, gli stati logici indifferenza saranno considerati come 0 \; logico e le relative combinazioni di variabili booleane d'ingresso, come maxtermini .

Da notare, però, che non è detto che tutti gli stati logici indifferenza presenti in una tabella della verità concorrano ad una maggior riduzione della funzione booleana d'uscita, quindi non è detto che tutti i mintermini (o maxitermini) ad essi corrispondenti debbano essere considerati durante il processo di riduzione.

Di seguito vedremo come utilizzare gli stati logici indifferenza nei tre sistemi di riduzione di una funzione booleana già analizzati: metodo algebrico, metodo delle mappe di Karnaugh e metodo Quine - McCluskey.

Gli stati logici indifferenza: il metodo "algebrico"

Consideriamo il caso in cui la nostra funzione booleana d'uscita O \; sia in stato logico 1 \; quando la posizione assunta dal selettore del commutatore appena visto si trova sui numeri 0, \; 1, \; 2, \; 3, \; 6 \;.

In tal caso otteniamo la seguente tabella della verità:

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Consideriamo di realizzare la nostra funzione booleana d'uscita O \; come somma logica di prodotti logici, quindi come somma logica di mintermini e, per vedere quale vantaggio porta, alla riduzione della stessa, l'eventuale utilizzo delle condizioni di indifferenza come stato logico 1 \;, iniziamo a vedere come sarebbe se queste stesse condizioni indifferenti fossero ininfluenti per una funzione booleana somma logica di mintermini, quindi in stato logico 0 \;:

O = \sum _{n = 0}^3{m_n} + m_6 = \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 \; I_1 \; \overline {I_2} \; \overline {I_3} + \overline {I_0} \; I_1 \; I_2 \; \overline {I_3}

Procedendo come abbiamo già visto in LogicBignami (VI), passiamo alla riduzione per via algebrica, cercando il numero minimo di coppie di mintermini, che mi permettano di ridurre, se possibile, tutti i mintermini presenti, alle quali sia possibile applicare, in sequenza, la proprietà distributiva, la regola della complementarietà e la regola dell'elemento neutro (più la regola dell'idempotenza al mitermine m_2 \;): queste sono [m_0, \; m_1] \; \; [m_2, \; m_3] \; , \; [m_2, \; m_6] \;.

Stabilite le coppie di mintermini su cui agire si ottengono i seguenti implicanti:

\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_1} \; \overline {I_2} \; \overline {I_3} \cdot (\overline {I_0} + I_0) = \overline {I_1} \; \overline {I_2} \; \overline {I_3}

\overline {I_0} \; I_1 \; \overline {I_2} \; \overline {I_3} + I_0 \; I_1 \; \overline {I_2} \; \overline {I_3} = I_1 \; \overline {I_2} \; \overline {I_3} \cdot (\overline {I_0} + I_0) = I_1 \; \overline {I_2} \; \overline {I_3}

\overline {I_0} \; I_1 \; \overline {I_2} \; \overline {I_3} + \overline {I_0} \; I_1 \; I_2 \; \overline {I_3} = \overline {I_0} \; I_1 \; \overline {I_3} \cdot (\overline {I_2} + I_2) = \overline {I_0} \; I_1 \; \overline {I_3}

si nota, altresì, che, i primi due imlòicanti trovati, sono ulteriormente riducibili:

\overline {I_1} \; \overline {I_2} \; \overline {I_3} + I_1 \; \overline {I_2} \; \overline {I_3} = \overline {I_2} \; \overline {I_3} \cdot (\overline {I_1} + I_1) = \overline {I_2} \; \overline {I_3}

Quindi, la nostra funzione booleana ridotta, senza considerare i termini di indifferenza, equivale a:

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

Siamo quindi passati dalla funzione booleana, in formato canonico, costituita dalla somma logica di 5 \; mintermini, ad una funzione booleana, in formato ridotto, costituita dalla somma logica di 2 \; implicanti, uno costituito dal prodotto logico di 2 \; variabili booleane d'ingresso e l'altro dal prodotto logico di 3 \;.

Vediamo allora se, l'inserimento, nella funzione booleana in formato canonico, delle condizioni di indifferenza come stato logico 1 \;, ci permette di ottenere una funzione booleana maggiormente ridotta.

Iniziamo considerando tutte le condizioni di indifferenza allo stato logico 1 \; e ricaviamo la nuova funzione booleana in formato canonico (di seguito il mintermine sottolineato indicherà che lo stesso deriva da una condizione di indifferenza):

O = \sum _{n=0}^3{m_n} + m_6 + \sum_{n=10}^{15}{m_n} = \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 \; I_1 \; \overline {I_2} \; \overline {I_3} +

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

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

Ora dobbiamo cercare, se esistono, quali mintermini, tra quelli risultanti dalle condizioni di indifferenza, ci permettono di ridurre ulteriormente i due implicanti \overline {I_2} \; \overline {I_3} \; e \overline {I_0} \; I_1 \; \overline {I_3} \; trovati in precedenza.

Innanzi tutto notiamo che nessuno dei mintermini derivati dalle condizioni di indifferenza permette di ricavare un implicante che possa ridurre \overline {I_2} \; \overline {I_3} \; tipo \overline {I_2} \; I_3 \; o I_2 \; \overline {I_3} \;: infatti solo 2 \; (la coppia [m_{10}, \; m_{11}] \;) contengono il gruppo di variabili \overline {I_2} \; I_3 \;, da cui si otterrebbe l'unico implicante:

\underline {\overline {I_0} \; I_1 \; \overline {I_2} \; I_3} + \underline {I_0 \; I_1 \; \overline {I_2} \; I_3} = I_1 \; \overline {I_2} \; I_3 \cdot (\overline {I_0} + I_0) = I_1 \; \overline {I_2} \; I_3 \;

di nessuna utilità.

Vediamo, allora, se esiste la possibilità di ridurre l'implicante \overline {I_0} \; I_1 \; \overline {I_3} \;.

Nessuno dei 6 \; mintermini derivati dalle condizioni di indifferenza contiene la variabile booleana \overline {I_3} \; quindi è logico suppore che, se sarà possibile, la riduzione porterà proprio all'eliminazione di questa variabile booleana.

Elenchiamo, allora, tutti i mintermini che contengono il gruppo di variabili booleane \overline {I_0} \; I_1 \;, evidenziando sempre con una sottolineatura quelli derivanti dalle condizioni di indifferenza:

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

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

m_{10} = \underline {\overline {I_0} \; I_1 \; \overline {I_2} \; I_3}

m_{14} = \underline {\overline {I_0} \; I_1 \; I_2 \; I_3}

Come sappiamo la riduzione della coppia [m_2, \; m_6] \; da limplicante \overline {I_0} \; I_1 \; \overline {I_3} \;, mentre dalla coppia [m_{10}, \; m_{14}] \; risulta limplicante:

\underline {\overline {I_0} \; I_1 \; \overline {I_2} \; I_3} + \underline {\overline {I_0} \; I_1 \; I_2 \; I_3} = \overline {I_0} \; I_1 \; I_3 \cdot (\overline {I_2} + I_2) = \overline {I_0} \; I_1 \; I_3

a loro volta, questi due implicanti sono, tra loro, riducibili

\overline {I_0} \; I_1 \; \overline {I_3} + \overline {I_0} \; I_1 \; I_3 = \overline {I_0} \; I_1 \cdot (\overline {I_3} + I_3) = \overline {I_0} \; I_1

Anche per questo implicante non esiste possibilità di ulteriori riduzioni, con i mintermini a disposizione, quindi, di tutti quelli derivati dalle condizioni di indifferenza, gli unici utili per ridurre ulteriormente la nostra funzione booleana sono esclusivamente m_{10} \; e m_{14} \;:

O = \sum _{n=0}^3{m_n} + m_6 + m_{10} + m_{14} = \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 \; I_1 \; \overline {I_2} \; \overline {I_3} +

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

Come riprova ricaviamoci la relativa tabella della verità:

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Come si vede gli stati logici assunti dalla funzione booleana O \; sono identici a quelli presenti nella tabella della verità di inizio paragrafo, le condizioni di indifferenza hanno, ovviamente assunto gli stati logici coerenti con le scelte fatte in fase di riduzione ma, come tali, non sono di alcuna importanza per la funzionalità richiesta.

Gli stati logici indifferenza: il metodo delle "mappe di Karnaugh"

Abbiamo appena visto che l'analisi per la scelta di quanti e quali condizioni indifferenza utilizzare mediante la riduzione con il metodo algebrico può risultare relativamente lunga e complessa, cosa soprattutto vera all'aumentare del numero di variabili booleane manipolate.

Con il metodo delle mappe di Karnaugh, invece, l'operazione di selezione e scelta delle condizioni di indifferenza risulta la più semplice e immediata, con il limite, però, come già detto in articoli precedenti, che, di fatto, è praticabile solo per sistemi che utilizzano, al massimo, 5 \; variabili booleane.

Vediamo, allora, come sarebbe stata più veloce la semplificazione della funzione booleana relativa all'uscita O \; della tabella della verità usata nel paragrafo precedente:

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Da questa si ricava, come abbiamo visto nell'articolo LogicBignami (VII), la seguente mappa di Karnaugh:

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Consideriamo, anche qui, di voler ottenere una funzione booleana come somma logica di prodotti logici, quindi utilizzaremo i mintermini in stato logico 1 \; escludendo, per il momento, le condizioni di indifferenza per meglio esplicitare il loro contributo alla riduzione della funzione booleana d'uscita.

Vediamo, allora, che sono possibili due soli raggruppamenti: uno da 4 \; mintermini (indicato in blu) e uno da 2 \; (indicato in azzurro).

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Da questi due raggruppamenti, considerando in ognuno le variabili booleane che non cambiano di stato logico, si ricava la fuznione booleana:

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

Dobbiamo ora vedere se, tra le condizioni di indifferenza, ci sono dei termini che, considerati in stato logico 1 \;, permetterebbero di eseguire dei raggruppamenti con un meggior numero di mintermini rispetto ai precedenti inglobando i termini già in stato logico 1 \;.

Dalla disposizione delle X \; sulla mappa di Karnaugh si nota che solo due di queste, evidenziate con riquadri in rosso, permetterebbero di avere un raggruppamento da 4 \; mintermini (evidenziato in verde), andando ad inglobare il raggruppamento da 2 \; precedente:

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Quindi, la funzione booleana definitivamente ridotta, con il contributo delle condizioni di indifferenza, risulterà essere:

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

E' da tener presente che, quando, in una mappa di Karnaugh, sono presenti delle condizioni di indifferenza queste vanno considerate solo se sono utili, cioè solo se permettono di incorporare mintermini già in stato logico 1 \; (quelli, cioè, che sono già in uno stato logico prestabilito dalla funzione booleana richiesta) in raggruppamenti più grossi di quelli realizzabili senza condizioni di indifferenza.

Nella nostra mappa di Karnaugh, ad esempio, si nota che sarebbero possibili altri due raggruppamenti da 4 \; mintermini, segnati con il tratteggio: questi sono inutili perchè incorporano esclusivamente delle condizioni di indifferenza non portando, quindi, a nessuna ulteriore semplificazione alla nostra funzione booleana.

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Come abbiamo già visto nell'articolo dedicato alla semplificazione tramite le mappe di Karnaugh, anche in presenza di condizioni di indifferenza potrebbe capitare una situazione che ammette più soluzioni equivalenti.

Consideriamo, ad esempio, la seguente mappa di Karnaugh:

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Come si può notare i due mintermini evidenziati in grassetto potrebbero essere raggruppati in due modi con altrettante due condizioni di indifferenza:

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Queste, ai fini della semplificazione, sono identiche, per tanto se ne sceglierà una delle due a prorpia discrezione.

Vista l'applicazione delle condizioni di indifferenza anche al metodo delle mappe di Karnaugh, passiamo adesso ad analizzare il loro impiego con il metodo di riduzione Quine-McCluskey

Gli stati logici indifferenza: il metodo "Quine-McCluskey"

Per vedere come utilizzare le condizioni di indifferenza nella riduzione delle funzioni booleane con il metodo Quine-McCluskey, partiamo sempre da un esempio con il nostro commutatore di inizio articolo.

Questa volta supponiamo che la funzione booleana dell'uscita O \;, di nostro interesse, sia a livello logico 1 \; quando il selettore del commutatore sia posizionato in corrispondenza di un numero primo, quindi in corrispondenza dei numeri 2, \; 3, \; 5, \; 7 \;, per cui ricaviamo la seguente tabella della verità:

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

A questo punto dobbiamo procedere come abbiamo visto nell'articolo LogicBignami (VIII) per eseguire riduzione secondo il metodo Quine-McCluskey.

Innanzi tutto ricaviamo la tabella dove raggruppiamo i mintermini relaitivi allo stato logico 1 \; della funzione booleana d'uscita, suddivisi secondo il numero delle corrispondenti variabili booleane d'ingresso settate a livello logico 1 \; (gruppo 1, una sola variabile booleana a livello logico 1 \; - gruppo 2, due variabili booleane a livello logico 1 \;, ... ) : in questi gruppi inseriremo anche tutti i mintermini relativi alle condizioni di indifferenza X \; che, di conseguenza, considereremo allo stato logico 1\;.:

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Iniziamo, quindi, a cercare gli implicanti primi K_{[n, \; m] \; [p, \; q]...} \;, ricavando la tabella, innanzi tutto, degli implicanti che derivano dalla riduzione dei mintermini (ricordo che la colonna con il carattere "*" ci serve per vedere se non è stato possibile ridurre qualche termine):

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Proseguiamo, cercando ulteriori riduzioni tra gli implicanti appena trovati, ricavando questa utletriore tabella:

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Notiamo che nella tabella di sinistra l'implicante K_{[13, \; 15]} \;, indicato con la freccia blu, non è stato possibile sommarlo logicamente con nessuno del gruppo precedente al fine di ridurlo, quindi sarebbe un implicante primo: in realtà, essendo il risultato, a sua volta, della somma logica di due mintermini derivati da condizioni di indifferenza, questo non rientrerà nel grafico degli implicanti primi.

Nella tabella di destra, invece, si nota che:

1) La presenza di due coppie di implicanti uguali, la coppia indicata dalla lettera "a" e quella indicata dalla lettera "b": di ognuna di queste si utilizzerà un unico implicante.

2) Nessun implicante del gruppo superiore può essere accoppiato (sommato logicamente al fine di ridurlo) con un implicante del gruppo inferiore, quindi, ogni implicante, è un implicante primo, però, anche in questa tabella sono presenti due implicanti, K_{[10, \; 11] \; [14, \; 15]} \; e K_{[12, \; 13] \; [14, \; 15]} \;, che sono il risultato della riduzione di mintermini derivati da condizioni di indifferenza che, pertanto, non saranno inseriti, neanche loro, nel grafico degli implicanti primi.

Fatte queste considerazioni possiamo costruire il grafico degli implicanti primi dove non compariranno, come indicizzazione delle colonne, i mintermini derivati dalle condizioni di indifferenza:

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Come possiamo vedere sono presenti due colonne, rispettivamente indicizzate da m_2 \; e m_5 \;, che contengono un unico carattere "x" (evidenziato in un cerchio): come sappiamo, gli implicanti primi in corispondenza di questi diventano implicanti primi essenziali e finiscono direttamente nella funzione booleana ridotta.

Tutti i caratteri "x" sulla medesima riga degli implicanti primi essenziali vanno cancellati, così come tutti i caratteri "x" presenti nelle colonne corrispondenti a tutte le precedenti "x" cancellate, ricavando il seguente grafico:

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Come si vede i soli due implicanti primi essenziali bastano a coprire tutti gli stati logici 1 \; dei mintermini realtivi alla funzione booleana richiesta, pertanto la stessa equivarrà alla somma logica dei due:

O = K_{[2, \; 3] \; [10, \; 11]} + K_{[5, \; 13] \; [7, \; 15]} = I_1 \; \overline {I_2} + I_0 \; I_2

A riprova che sia la funzione booleana richiesta, possiamo ricavarci la relativa tabella della verità:

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Come volevasi dimostrare gli stati logici della funzione booleana d'uscita O \; sono identici a quelli della tabella della verità di inizio paragrafo.

Da questa tabella della verità si nota anche che le uniche condizioni di indifferenza, che vanno considerate a stato logico 1 \;, necessarie per la riduzione della funzione booleana, sono quelle relative ai mintermini m_{10} \;, m_{11} \;, m_{13} \; e m15 che sono poi quelli "manipolati" nei due implicanti primi essenziali.

Con questo abbiamo terminato questo addendum relativo all'utilizzo delle condizioni di indifferenza nella riduzione delle funzioni booleane, questo, come abbiamo detto ad inizio articolo, ci tornerà sicuramente utile in prossimi quando analizzeremo la realizzazione dei circuiti digitali di decodifica.

LogicBignami - Indice articoli correlati

Estratto da "https://www.electroyou.it/mediawiki/index.php?title=UsersPages:Max2433bo:addendum"
2

Commenti e note

Inserisci un commento

di ,

<(_ _)> <(_ _)> <(_ _)> ... \(^.~)/
... non sono riuscito a capire come inserire le emoj, così ho ripiegato sul "japan style"...

Rispondi

di ,

.. .. ..

Rispondi

Inserisci un commento

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