Metodo di Quine-McCluskey

Il metodo di Quine-McCluskey (o metodo degli implicanti primi) è un algoritmo sviluppato da Willard Van Orman Quine ed Edward McCluskey che viene utilizzato nelle reti combinatorie a due livelli di logica per la minimizzazione di una funzione booleana di n variabili. Il metodo è funzionalmente identico alla mappa di Karnaugh, ma la sua forma tabellare lo rende più efficiente per essere realizzato al computer; inoltre fornisce anche un modo deterministico per testare la minimizzazione di una funzione booleana.

Il metodo consiste in due passi:

1. Identificare tutti gli implicanti primi della funzione.
2. Riportare gli implicanti primi trovati in una tabella per ricavare gli implicanti primi essenziali della funzione.

Complessità

Sebbene sia più pratico rispetto alle mappe di Karnaugh per funzioni con più di 4 variabili, il metodo di Quine-McCluskey ha comunque un intervallo limitato di utilizzo, poiché il problema che l'algoritmo risolve (la soddisfacibilità booleana) è NP-difficile: il suo runtime cresce esponenzialmente all'aumentare del numero degli ingressi. Si può dimostrare che per una funzione di n variabili il limite superiore sul numero di implicanti primi è 3ⁿ/n. Se n = 32 ci possono essere più di 6.5 * 10¹⁵ implicanti primi. Pertanto, le funzioni con un grande numero di variabili booleane devono essere minimizzate con metodi euristici, come ad esempio il minimizzatore logico Espresso (Espresso heuristic logic minimizer).

Metodo

Il metodo consiste in due fasi principali: la ricerca degli implicanti primi e la successiva ricerca della copertura ottimale. Consideriamo la minimizzazione in forma di somma di prodotti (detta anche SOP, dall'acronimo inglese sum of products), ma il tutto è facilmente estendibile alla forma di prodotto di somme (o POS, product of sums).

Nella prima fase si applica sistematicamente la semplificazione del tipo:

$aP+{\overline {a}}P=(a+{\overline {a}})\cdot P=P$

cioè la proprietà distributiva del prodotto rispetto alla somma, dove P indica un qualsiasi termine prodotto (mintermine). Ovviamente il metodo è estendibile anche a funzioni non completamente specificate e anche a circuiti multiuscita. La prima fase consiste dei passi:

1. tabellare tutti i mintermini della funzione in forma binaria, in ordine crescente come per la tabella della verità;
2. confrontare tra loro tutti i termini esaustivamente: si semplificano i termini che differiscono per un solo bit (distanza di Hamming unitaria) e si marcano, in quanto essi hanno contribuito alla creazione di un implicante;
3. creare quindi una nuova tabella con tutti i termini prodotto marcati che vengono fuori dalla prima tabella e si ripete il passo 2);
4. il processo termina quando non si possono più fare riduzioni.

Al punto della costruzione della tabella è facile vedere che non dobbiamo necessariamente confrontare tutti i termini tra loro, ma effettivamente solo quei termini adiacenti che differiscono per un solo bit 1. Quindi raggruppiamo nella tabella i termini che hanno un numero uguale di 1 nel mintermine.

Esempio

Sia data la seguente funzione:

$f(a,b,c,d)=\sum (1,9,11,12,13,14,15)$

Passo 1: tabella degli implicanti primi

a b c d	$P_{i}$
0 0 0 1	1	...
1 0 0 1	9	...
1 0 1 1	11	...
1 1 0 0	12	...
1 1 0 1	13	...
1 1 1 0	14	...
1 1 1 1	15	...

Passo 2: confronto

Vediamo dalla tabella che il mintermine 1 va confrontato solo con il mintermine 9, che ha due 1 nel suo prodotto e non con gli altri che differiscono di due bit. Confrontando il mintermine 1 con quello 9 vediamo che differiscono solo per il primo bit: la prima riga della successiva tabella deve quindi essere -001 semplificando per l'appunto il primo bit. Il confronto di 1 con 12 non è compatibile perché i due mintermini non differiscono per un solo bit. Viceversa 9 si confronta con 11 e 13 ma non con 14, e 12 si confronta con 13 e 14 ma non con 11. Infine 11, 13, 14 si confrontano con 15. Il risultato finale è tabellato nella successiva tabella.

a b c d	$P_{i}$
− 0 0 1	1,9	...
1 0 − 1	9,11	...
1 − 0 1	9,13	...
1 − 1 1	11,15	...
1 1 0 −	12,13	...
1 1 − 0	12,14	...
1 1 − 1	13,15	...
1 1 1 −	14,15	...

Passo 2: ancora riduzione

Ovviamente dobbiamo nuovamente ridurre finché è possibile. In questo caso possiamo solo confrontare 9,11 con 13,15 che differiscono per il secondo bit e 12,13 con 14,15 che differiscono solo per il terzo bit:

a b c d	$P_{i}$
1 − − 1	9,11,13,15	...
1 1 − −	12,13,14,15	...

Passo 3: selezione implicanti primi

A questo punto non sono possibili altre riduzioni. Gli implicanti primi sono:

$P_{0}(1,9)={\overline {b}}{\overline {c}}d$

$P_{1}(9,11,13,15)=ad$

$P_{2}(12,13,14,15)=ab$

Copertura

La seconda fase riguarda la scelta ottimale degli implicanti. Per fare questo costruiamo una tabella detta tabella di copertura che consiste in una matrice in cui gli indici di riga rappresentano gli implicanti primi identificati, mentre gli indici di colonna rappresentano tutti i mintermini $P_{i}$ della funzione. Gli elementi della tabella di copertura sono caselle segnate con 1 se l'implicante $P_{i}$ copre il mintermine j-esimo, altrimenti sono 0. In alternativa si usa semplicemente una "x" per identificare solo gli uno in tabella.

      1 9  11 12 13 14 15
 -------------------------------
 P0 | x x                |
 P1 |   x  x     x     x |
 P2 |         x  x  x  x |
 -------------------------------

Esempio

$f(A,B,C,D)=\sum m(4,8,10,11,12,15)+d(9,14)$

     A B C D   f 
 m0  0 0 0 0   0
 m1  0 0 0 1   0
 m2  0 0 1 0   0
 m3  0 0 1 1   0
 m4  0 1 0 0   1
 m5  0 1 0 1   0
 m6  0 1 1 0   0 
 m7  0 1 1 1   0
 m8  1 0 0 0   1
 m9  1 0 0 1   -
m10  1 0 1 0   1
m11  1 0 1 1   1 
m12  1 1 0 0   1
m13  1 1 0 1   0
m14  1 1 1 0   -
m15  1 1 1 1   1

Dalla tabella si può ricavare la forma canonica della funzione sotto forma di somma di prodotti (disgiuntiva) semplicemente sommando i mintermini con uscita "1" (ma tralasciando quelli con uscita don't care "-"):

$f_{A,B,C,D}=A'BC'D'+AB'C'D'+AB'CD'+AB'CD+ABC'D'+ABCD$

La funzione, ovviamente, non è in forma minima. Quindi, per minimizzarla, si riportano su una tabella tutti i mintermini con uscita "1" (comprendendo anche quelli con il don't care come uscita), ordinandoli in classi a seconda del numero di "1" presenti in ciascun mintermine:

Numero di "1"   Mintermine  Rappresentazione binaria
--------------------------------------------
1               m4          0100
                m8          1000
--------------------------------------------
2               m9          1001
                m10         1010
                m12         1100
--------------------------------------------
3               m11         1011
                m14         1110
--------------------------------------------
4               m15         1111

A questo punto, si può iniziare a combinare i mintermini tra di loro. Se due mintermini, appartenenti a classi diverse, hanno una distanza di Hamming pari a 1 (ossia differiscono per una sola variabile), allora possono essere uniti, inserendo nella variabile non in comune un don't care. I mintermini che non possono essere combinati tra di loro sono indicati nell'esempio con un asterisco ("*"). Una volta esauriti tutti gli implicanti del 4º ordine, si passa all'eventuale semplificazione di quelli del 3º ordine, dove in questo caso vanno uniti tra loro i mintermini con distanza di Hamming pari a 2. Alla fine si perviene alla seguente tabella:

Implicanti del 4º ordine       | Implicanti del 3º ordine | Implicanti del 2º ordine
-------------------------------|--------------------------|-------------------------
Numero di "1"     Mintermine   |                          |
-------------------------------|--------------------------|-------------------------
1             m4       0100    | m(4,12)  -100*           | m(8,9,10,11)   10--*
              m8       1000    | m(8,9)   100-            | m(8,10,12,14)  1--0*
-------------------------------| m(8,10)  10-0            |-------------------------
2             m9       1001    | m(8,12)  1-00            | m(10,11,14,15) 1-1-*
              m10      1010    |--------------------------|
              m12      1100    | m(9,11)  10-1            |
-------------------------------| m(10,11) 101-            |
3             m11      1011    | m(10,14) 1-10            |
              m14      1110    | m(12,14) 11-0            |
-------------------------------|--------------------------|
4             m15      1111    | m(11,15) 1-11            |
                               | m(14,15) 111-            |

Passo 2: mappa di copertura

Una volta terminata la ricerca degli implicanti primi, questi vengono riportati in una tabella apposita, scrivendo sulle righe gli implicanti e sulle colonne i mintermini.

	4	8	9	10	11	12	14	15
m(4,12)*	X					X			-100
m(8,9,10,11)*		X	X	X	X				10--
m(8,10,12,14)*		X		X		X	X		1--0
m(10,11,14,15)*				X	X		X	X	1-1-

Per poter procedere alla scelta delle coperture si applicano i seguenti criteri:

• Scelta dell'implicante essenziale: Un implicante è detto essenziale se una marcatura presente in una colonna è coperta in una sola riga. Nel qual caso si aggiunge l'implicante all'insieme delle coperture e si elimina la riga e tutte le colonne in cui è presente una marcatura dell'implicante. Nell'esempio, il primo implicante è essenziale poiché è l'unico a coprire il mintermine 4.Lo stesso vale per il secondo implicante che copre il mintermine 9 e per il quarto implicante che copre il mintermine 15.
• Dominanza di riga: La riga i domina la riga j se l'implicante Pi copre tutti i mintermini che copre l'implicante Pj più almeno uno.

• Dominanza di colonna: La colonna i domina la colonna j se il mintermine mj è coperto dagli stessi implicanti da cui è coperto mi più almeno uno.

In questo caso, il terzo implicante primo può essere coperto dal secondo, dal primo e dal quarto, quindi non è essenziale. In alcuni casi, si presentano situazioni di mappe cicliche in cui non sono presenti condizioni di dominanza né di essenzialità, per cui vanno utilizzate altre procedure per la semplificazione. Un modo sistematico ed efficiente è rappresentato dal metodo di Petrick. In quest'esempio, gli implicanti primi essenziali coinvolgono tutti i mintermini, quindi non c'è bisogno di combinare gli implicanti essenziali con quelli non essenziali, e si ottiene la seguente equazione:

$f_{A,B,C,D}=B{\bar {C}}{\bar {D}}+A{\bar {B}}+AC\$

Le equazioni ricavate sono funzionalmente equivalenti all'equazione originaria:

$f_{A,B,C,D}=A'BC'D'+AB'C'D'+AB'C'D+AB'CD'+AB'CD+ABC'D'+ABCD'+ABCD\$