Indietro

ⓘ Metodo di Quine-McCluskey




                                     

ⓘ Metodo di Quine-McCluskey

Il metodo di Quine-McCluskey è 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:

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

1. 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 lalgoritmo risolve la soddisfacibilità booleana è NP-difficile: il suo runtime cresce esponenzialmente allaumentare del numero degli ingressi. Si può dimostrare che per una funzione di n variabili il limite superiore sul numero di implicanti primi è 3 n / n. Se n = 32 ci possono essere più di 6.5 * 10 15 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 heuristic logic minimizer.

                                     

2. 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, dallacronimo 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:

a P + a ¯ P = a + a ¯ ⋅ P = P {\displaystyle 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:

  • tabellare tutti i mintermini della funzione in forma binaria, in ordine crescente come per la tabella della verità;
  • il processo termina quando non si possono più fare riduzioni.
  • 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;
  • creare quindi una nuova tabella con tutti i termini prodotto marcati che vengono fuori dalla prima tabella e si ripete il passo 2);

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.

                                     

2.1. Metodo Esempio

Sia data la seguente funzione:

f a, b, c, d = ∑ 1, 9, 11, 12, 13, 14, 15 {\displaystyle fa,b,c,d=\sum 1.9.11.12.13.14.15}
                                     

2.2. Metodo 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:

                                     

2.3. Metodo Passo 3: selezione implicanti primi

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

P 0 1, 9 = b ¯ c ¯ d {\displaystyle P_{0}1.9={\overline {b}}{\overline {c}}d} P 1 9, 11, 13, 15 = a d {\displaystyle P_{1}9.11.13.15=ad} P 2 12, 13, 14, 15 = a b {\displaystyle P_{2}12.13.14.15=ab}
                                     

3. 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 {\displaystyle P_{i}} della funzione. Gli elementi della tabella di copertura sono caselle segnate con 1 se limplicante P i {\displaystyle 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 | P1 | x | P2 | x | -------------------------------
                                     

4. Esempio

f A, B, C, D = ∑ m 4, 8, 10, 11, 12, 15 + d 9, 14 {\displaystyle fA,B,C,D=\sum m4.8.10.11.12.15+d9.14}

A B C D f m0 0 m1 0 1 0 m2 0 1 0 m3 0 1 0 m4 0 1 0 1 m5 0 1 0 1 0 m6 0 1 0 m7 0 1 0 m8 1 0 1 m9 1 0 1 - m10 1 0 1 0 1 m11 1 0 1 m12 1 0 1 m13 1 0 1 0 m14 1 0 - m15 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 dont care "-":

f A, B, C, D = A ′ B C ′ D ′ + A B ′ C ′ D ′ + A B ′ C D ′ + A B ′ C D + A B C ′ D ′ + A B C D {\displaystyle f_{A,B,C,D}=ABCD+ABCD+ABCD+ABCD+ABCD+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 dont 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 dont care. I mintermini che non possono essere combinati tra di loro sono indicati nellesempio con un asterisco "*". Una volta esauriti tutti gli implicanti del 4º ordine, si passa alleventuale 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 | m4.12 -100* | m8.9.10.11 10--* m8 1000 | m8.9 100- | m8.10.12.14 1--0* -------------------------------| m8.10 10-0 |------------------------- 2 m9 1001 | m8.12 1-00 | m10.11.14.15 1-1-* m10 1010 |--------------------------| m12 1100 | m9.11 10-1 | -------------------------------| m10.11 101- | 3 m11 1011 | m10.14 1-10 | m14 1110 | m12.14 11-0 | -------------------------------|--------------------------| 4 m15 1111 | m11.15 1-11 | | m14.15 111- |


                                     

4.1. Esempio Passo 2: tabella degli implicanti primi

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.

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

  • Dominanza di riga: La riga i domina la riga j se limplicante Pi copre tutti i mintermini che copre limplicante 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.
  • Scelta dellimplicante essenziale: Un implicante è detto essenziale se una marcatura presente in una colonna è coperta in una sola riga. Nel qual caso si aggiunge limplicante allinsieme delle coperture e si elimina la riga e tutte le colonne in cui è presente una marcatura dellimplicante. Nellesempio, il primo implicante è essenziale poiché è lunico 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.

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 questesempio, 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 C ′ D ′ + A B ′ + A C {\displaystyle f_{A,B,C,D}=BCD+AB+AC\ }

Le equazioni ricavate sono funzionalmente equivalenti allequazione originaria:

f A, B, C, D = A ′ B C ′ D ′ + A B ′ C ′ D ′ + A B ′ C ′ D + A B ′ C D ′ + A B ′ C D + A B C ′ D ′ + A B C D ′ + A B C D {\displaystyle f_{A,B,C,D}=ABCD+ABCD+ABCD+ABCD+ABCD+ABCD+ABCD+ABCD\ }


                                     
  • congiuntiva, minimizzata tramite tecniche quali la mappa di Karnaugh o il metodo di Quine - McCluskey I primi dispositivi PLA ad essere stati prodotti implementano
  • in particolare sono utilizzati nei metodi di semplificazione come le mappe di Karnaugh o il metodo di Quine - McCluskey Un implicante non contenuto in nessun
  • minore di porte logiche per essere realizzata. Un alternativa alle mappe di Karnaugh, utile nei casi già elencati, è il metodo di semplificazione Quine McCluskey

Anche gli utenti hanno cercato:

14 pugni di mccluskey, i 14 punti di mccluskey, mccluskey il padrino, metodo di petrick esercizi,

...
...
...