Introduzione alla Minimizzazione delle Funzioni Booleane

Concetti Chiave

La minimizzazione delle funzioni booleane è un aspetto cruciale nella progettazione di circuiti logici efficienti.
Comprendere le tecniche di minimizzazione può portare a circuiti più semplici e veloci.
Alla base della minimizzazione delle funzioni booleane vi è l'uso della relazione:

$xy + x\overline{y} = x$
Rappresentando geometricamente le funzioni booleane, possiamo ottenere una migliore comprensione delle loro proprietà e delle tecniche di minimizzazione.

Introduzione alla Minimizzazione delle Funzioni Booleane

Lo sviluppo di una tecnica di progettazione di circuiti logici tale da produrre un progetto ottimale non è un compito semplice. La motivazione principale sta nel fatto che le specifiche di un circuito logico sono spesso in conflitto.

La realizzazione di un circuito ottimo richiede considerazioni su tre aspetti principali:

Il costo del circuito che dipende dal numero di porte logiche e dalla loro complessità;
La velocità (che dipende dal ritardo) del circuito; ogni porta logica ha un certo ritardo che influisce sulla velocità complessiva del circuito. Maggiore è il numero di porte logiche, maggiore sarà il ritardo.
L'affidabilità del circuito.

Il ritardo del circuito dipende dal numero di porte logiche e si riferisce al tempo necessario affinché si abbia un cambio del segnale di output in risposta ad una variazione dell'input. Questo tempo è funzione del numero di porte attraverso le quali un segnale deve propagarsi per raggiungere l'output. Il massimo numero di porte attraverso le quali un segnale deve passare determina il numero di livelli o di stadi del circuito.

Esiste un conflitto tra il costo del circuito ed il suo ritardo. Infatti, aumentando il numero di porte logiche per ridurre il costo, si aumenta anche il ritardo del circuito.

Allo stesso modo, l'affidabilità è in conflitto con il costo. Per aumentare l'affidabilità, è necessario utilizzare più porte logiche ridondanti, il che aumenta il costo del circuito. Oppure, bisogna adoperare componenti più affidabili e, di conseguenza, più costosi.

Diventa chiaro, quindi, che una realizzazione ottima richieda un compromesso tra questi tre aspetti: costo, velocità e affidabilità.

Sfortunatamente, non esistono tecniche di progettazione che, dati i requisiti di compromesso, possano garantire una soluzione ottimale in tutti i casi.

L'unico caso in cui è possibile ottenere una soluzione ottimale è quando si restringe il compromesso alla minimizzazione del circuito logico, ossia quando si desidera ridurre il numero di porte logiche utilizzate nel circuito e, di conseguenza, il ritardo.

Questa restrizione impone di realizzare circuiti logici con al massimo due livelli di porte in forma somma di prodotti o prodotto di somme, ossia in forma standard.

Dal momento che esistono più forme minime di una stessa funzione booleana, bisogna determinare quale fra queste corrisponde all'implementazione circuitale con il costo minore.

Possiamo ottenere una relazione diretta tra il costo e il numero di porte e il numero di input di tali porte. Analogamente, la corrispondenza tra queste quantità, numero di porte e numero di input, può essere messa in relazione diretta con l'espressione algebrica della funzione in questione:

Il numero di porte può essere direttamente calcolato come il numero di termini nell'espressione booleana che contengono più di una variabile, più uno.

Ad esempio, se prendiamo la seguente funzione booleana:

$F = a + b'cd + bc'$

Il numero di porte (escluso gli invertitori) per realizzarla è pari a 3. Infatti, abbiamo due termini con più di una variabile: $b'cd$ e $bc'$ , che richiedono ciascuno una porta AND, e un termine con una sola variabile: $a$ , che richiede una porta OR. Questo se scegliamo una realizzazione come somma di prodotti. Ma vale lo stesso anche se scegliamo una realizzazione in forma di prodotto di somme.
Il numero di input alle porte è dato, invece, dal numero di letterali che compaiono più il numero di termini che contengono più di un letterale.

Tornando all'esempio di prima:

$F = a + b'cd + bc'$

Abbiamo sei letterali, $a$ , $b'$ , $c$ , $d$ , $c$ e $d$ , e due termini con un numero di letterali maggiore di uno. Per cui, il numero di input alle porte è dato da $6 + 2 = 8$ .

In generale, la forma minima di un circuito logico può essere definita in questo modo:

Definizione

Forma Minima di una Funzione Booleana

Una funzione booleana è in forma minima se rispetta uno o più dei seguenti criteri:

Contiene il minor numero possibile di termini;
Contiene il minor numero possibile di letterali;
Richiede il minor numero possibile di input alle porte.

I criteri da adoperare dipendono dal tipo di hardware impiegato. Se si adoperano, ad esempio, moduli logici standard TTL (famiglia 74) o CMOS (famiglia 4000) probabilmente bisogna usare il primo criterio per minimizzare il numero di porte logiche utilizzate.

Sebbene i teoremi dell'algebra booleana forniscono le basi per la minimizzazione delle funzioni booleane, la loro applicabilità diretta diventa sempre più complessa al crescere della dimensione delle funzioni stesse e della loro implementazione hardware. Per questo motivo, esistono procedure automatiche o comunque semi-automatiche che permettono di velocizzare il processo.

Esistono tecniche di tipo geometrico (le mappe di Karnaugh che vedremo nelle prossime lezioni) che offrono un approccio visivo e sistematico per la minimizzazione delle funzioni booleane. Esse sono, però, applicabili quando il numero di variabili è relativamente ridotto (generalmente fino a 4 o 5 variabili).

Esistono poi, tecniche più complesse di minimizzazione che sfruttano algoritmi più complessi. Uno di questi è l'algoritmo di Quine-McCluskey.

Infine, esistono tecniche euristiche, che a differenza dei casi precedenti, non garantiscono una soluzione ottimale, ma possono fornire risultati soddisfacenti in tempi ragionevoli. Queste tecniche si basano su approcci pratici e sperimentali per ridurre la complessità delle funzioni booleane. Per tal motivo, le mappe di Karnaugh e l'algoritmo di Quine-McCluskey vengono spesso chiamati algoritmi di minimizzazione esatta per distinguere le loro capacità di trovare soluzioni ottimali rispetto alle tecniche euristiche.

In ogni caso, tutte queste tecniche sfruttano sempre in modo sistematico i teoremi dell'algebra booleana che abbiamo visto nelle lezioni precedenti.

Fondamenti della Minimizzazione

La maggior parte delle tecniche di minimizzazione discusse nelle prossime lezioni richiedono che le funzioni siano inizialmente in forma canonica.

Le tecniche per minimizzare espressioni canoniche di funzioni booleane utilizzano tutte la relazione

xy + x\overline{y} = x

Infatti, applicando la proprietà distributiva, possiamo riscrivere l'equazione di sopra come:

xy + x\overline{y} = x(y + \overline{y}) = x \cdot 1 = x

Come esempio, consideriamo l'applicazione di questa relazione all'espressione

f = abc + ab\overline{c} + a\overline{b}c + \overline{a}bc + \overline{a}b\overline{c}.

Questa espressione può essere ridotta a due espressioni somma-di-prodotti ugualmente minimizzate:

f = ab(c + \overline{c}) + a\overline{b}(c + \overline{c}) + ac(b + \overline{b}) = ab + a\overline{b} + ac

f = ab(c + \overline{c}) + a\overline{b}(c + \overline{c}) + \overline{b}c(a + \overline{a}) = ab + a\overline{b} + \overline{b}c.

Poiché le due espressioni sono forme ugualmente minimizzate della funzione, vengono chiamate minimali piuttosto che espressioni minime.

Se la funzione precedente viene modificata per includere il termine $\overline{a}b\overline{c}$ , scopriamo che il grado di minimizzazione dipende da quali coppie di termini vengono combinate. Per esempio, se combiniamo i termini in tre gruppi come

f = ab(c + \overline{c}) + a\overline{c}(b + \overline{b}) + \overline{b}c(a + \overline{a}),

otteniamo l'espressione minimizzata

f = ab + a\overline{c} + \overline{b}c;

mentre se combiniamo i termini in quattro gruppi come

f = ab(c + \overline{c}) + a\overline{c}(b + \overline{b}) + ac(b + \overline{b}) + a\overline{b}(c + \overline{c}),

otteniamo l'espressione minimizzata

f = ab + a\overline{c} + ac + a\overline{b}.

Qui abbiamo due versioni minimizzate dell'espressione, una con meno termini rispetto all'altra. Entrambe le espressioni sono chiamate somme irridondanti, poiché nessun termine può essere ulteriormente ridotto o eliminato.

Due problemi sono evidenziati nella discussione precedente. Il primo riguarda il riconoscimento delle coppie di termini che possono essere combinate utilizzando la relazione

xy + x\overline{y} = x;

il secondo riguarda la scelta delle combinazioni che produrranno un'espressione minima. Rimandiamo la discussione del secondo problema alle prossime lezioni.

La procedura di semplificazione descritta sopra ha coinvolto coppie di termini che differiscono nello stato barrato e non barrato di una singola variabile. Tali termini si dicono adiacenti; queste adiacenze sono più evidenti se utilizziamo le equivalenti rappresentazioni binarie come segue:

f = abc + ab\overline{c} + a\overline{b}c + \overline{a}bc + \overline{a}b\overline{c}

= 111 + 110 + 101 + 001 + 000.

Vediamo che le rappresentazioni binarie di termini adiacenti differiscono in una sola posizione di cifra. Questo fatto, che dobbiamo considerare la combinazione solo di quelle coppie di termini binari che differiscono in una sola posizione, viene utilizzato nelle mappe di Karnaugh che vedremo nelle prossime lezioni.

Consideriamo ora alcune rappresentazioni geometriche di funzioni che sono utili nella visualizzazione di termini adiacenti.

Rappresentazione Geometrica delle Funzioni Booleane

Una rappresentazione geometrica utile di una funzione è quella che permette la visualizzazione non solo di coppie di termini adiacenti che possono essere combinati per formare termini singoli di $n - 1$ variabili, ma anche di insiemi di coppie adiacenti di termini che possono essere combinati per formare termini singoli di meno di $n - 1$ variabili.

Una di queste rappresentazioni è fornita dal cubo n-dimensionale, in cui i termini canonici di una funzione sono rappresentati come punti nello spazio n-dimensionale. Il cubo n-dimensionale è costituito da $2^n$ nodi o vertici, uno per ciascun termine canonico possibile di una funzione di $n$ variabili, e da linee di interconnessione che uniscono coppie di nodi o termini adiacenti.

Cubi a una, due e tre dimensioni sono mostrati nelle figure seguenti:

Il cubo unidimensionale in figura rappresenta una variabile binaria: ogni nodo rappresenta uno dei due valori che può assumere la variabile.

Il cubo bidimensionale in figura ha quattro nodi, ognuno dei quali rappresenta uno dei quattro possibili valori combinati che possono essere assunti da due variabili.

Il cubo tridimensionale in figura ha otto nodi, corrispondenti agli otto possibili valori combinati di tre variabili.

Nella sezione precedente, la minimizzazione dell'espressione canonica è stata ottenuta combinando coppie adiacenti di termini per formare termini singoli contenenti $n - 1$ variabili. Questi termini sono rappresentati dalle linee del cubo n-dimensionale. Ad esempio, nella seconda figura la linea che collega i due nodi inferiori rappresenta la somma dei due termini $a\overline{b}$ e $ab$ , che è $b$ . I termini $a\overline{b}$ e $ab$ si dice alternativamente che sono contenuti in, coprono o sussumono il termine $b$ .

Per combinare un insieme di termini in un termine singolo contenente $n - k$ variabili, è necessario che l'insieme contenga $2^k$ termini, ciascuno dei quali è adiacente a $k$ altri termini e in cui i valori delle $n - k$ variabili restano costanti. L'insieme di nodi corrispondenti a questi termini forma un cubo k-dimensionale o sottocubo del cubo n-dimensionale.

Consideriamo il sottocubo corrispondente alla faccia inferiore del cubo tridimensionale mostrato nella figura seguente, per il quale $k$ vale due:

**Figura 4:** Sotto-cubo corrispondente al letterale c

Vediamo che il valore della variabile $c$ resta costante a 1, mentre tutti i valori possibili combinati sono presi dalle variabili $a$ e $b$ . I termini corrispondenti ai quattro nodi del sottocubo si combinano per formare la somma $(ab + a\overline{b} + \overline{a}b + \overline{a}\overline{b})c = c$ .

La funzione $f(a,b,c) = \Sigma (0,1,5,6,7)$ è mostrata mappata nella figura seguente:

**Figura 5:** Rappresentazione Geometrica della Funzione f

Ogni termine dell'espressione canonica è rappresentato da un nodo scuro, e i nodi adiacenti sono connessi da linee continue. Tutte le altre linee sono tratteggiate. Vediamo che ciascun nodo di questa funzione è incluso in almeno una delle linee continue, cosicché tutti i termini della funzione saranno inclusi nella seguente espressione ridotta, formata dalla somma dei termini corrispondenti alle linee continue:

f = \overline{a}\overline{b} + \overline{b}c + ac + ab.

Questa espressione può essere ulteriormente ridotta con le seguenti considerazioni: poiché il nodo $ab\overline{c}$ è contenuto solo nella linea $ab + a\overline{b}$ e il nodo $\overline{a}b\overline{c}$ solo nella linea $a\overline{b} + \overline{a}b$ , ogni espressione ridotta deve includere i termini corrispondenti a queste due linee. La somma di questi termini, $ab + a\overline{b}$ , copre tutti i termini canonici eccetto il termine $a\overline{b}c$ , e questo termine può essere coperto da uno qualsiasi dei termini ridotti $ac$ o $\overline{b}c$ . Ci sono quindi due somme ugualmente ridotte per questa funzione, cioè:

f = ab + a\overline{b} + ac

f = ab + a\overline{b} + \overline{b}c,

come abbiamo visto in precedenza.

Il cubo n-dimensionale perde la sua efficacia per $n > 3$ , poiché diventa sempre più difficile visualizzare i sottocubi per cui $k \geq 3$ .

L'utilità del cubo n-dimensionale può essere estesa oltre $n = 3$ se utilizziamo una rappresentazione alternativa. Consideriamo la rappresentazione del cubo tridimensionale mostrato nella figura che segue:

**Figura 6:** Rappresentazione Alternativa del Cubo Tridimensionale

Se le linee superiori e inferiori di questo diagramma vengono eliminate e a ciascun nodo viene assegnata un'area invece di un punto nello spazio bidimensionale, allora otteniamo quella che viene chiamata mappa. Questa rappresentazione è alla base della tecnica chiamata mappa di Karnaugh che vedremo nella prossima lezione.