Impara › Argomento 5

Metodo di Quine-McCluskey passo dopo passo

7 min di lettura · Team bitGateLab

La mappa di Karnaugh è rapida con quattro variabili, ma dipende dal tuo colpo d'occhio e smette di essere pratica con cinque o più. Il metodo di Quine-McCluskey fa lo stesso lavoro con tabelle e regole meccaniche: non richiede intuito, trova sempre tutti gli implicanti primi ed è alla base dei programmi che semplificano le funzioni logiche. Qui capirai le sue due fasi, imparerai a individuare gli implicanti primi essenziali e risolverai un esempio completo a quattro variabili.

Vocabolario: implicanti e primi

• Un implicante di F è un termine prodotto che, quando vale 1, garantisce che F vale 1. Ogni mintermine di F è un implicante, e lo è anche qualsiasi gruppo valido di una mappa di Karnaugh.
• Un implicante primo è un implicante che non si può ingrandire ulteriormente; se gli togli una variabile, copre qualche riga in cui F vale 0. Equivale a un gruppo massimo della mappa.
• Un implicante primo essenziale è un primo che copre almeno un mintermine non coperto da nessun altro primo. Deve comparire in qualsiasi soluzione minima.

Il metodo ha due fasi: prima trova tutti gli implicanti primi combinando i termini; poi sceglie il più piccolo insieme di primi che copra tutti i mintermini.

Fase 1: combinare i termini

Ogni termine si scrive in binario, e la posizione di una variabile eliminata si indica con un trattino. Per esempio, con le variabili A, B, C, D, il termine 0-11 significa ACD (B è stata eliminata).

1. Raggruppa i mintermini in base al numero di uni presenti nel loro codice binario.
2. Confronta ogni termine di un gruppo con ogni termine del gruppo successivo. Se differiscono per un solo bit, combinali mettendo un trattino in quella posizione, e segna i due originali come usati.
3. Ripeti con il nuovo elenco. Si combinano soltanto termini che hanno i trattini nelle stesse posizioni.
4. Quando non si può più combinare nulla, i termini che non sono mai stati segnati sono gli implicanti primi.

Fase 2: tabella degli implicanti primi

Si costruisce una tabella con una riga per ogni implicante primo e una colonna per ogni mintermine della funzione (le condizioni di indifferenza non hanno colonna). Si segna quali mintermini copre ciascun primo. Poi:

1. Cerca le colonne con un solo segno. Il primo di quella riga è essenziale: selezionalo e cancella tutte le colonne che copre.
2. Per le colonne rimaste, scegli il minor numero di primi che le copra. Se due primi coprono le stesse colonne, va bene uno qualsiasi; preferisci quello con meno letterali.

Se disegni questa funzione in una mappa di Karnaugh, P1 corrisponde ai quattro angoli, P4 al blocco centrale, P2 alle colonne 11 e 10 delle righe 00 e 10 (unite attraverso il bordo) e P3 all'intera colonna 11. Il metodo tabulare arriva allo stesso risultato senza bisogno di vedere la mappa.

Condizioni di indifferenza e tabelle cicliche

Le condizioni X si includono nella fase 1 come se fossero uni, perché possono aiutare a formare implicanti più grandi. Nella fase 2 si omettono: non hanno colonna, dato che non è obbligatorio coprirle. Un primo formato soltanto da X non serve mai.

A volte, dopo aver scelto gli essenziali, o fin dall'inizio, ogni colonna ha almeno due segni e non c'è un modo ovvio di decidere. Questa situazione si chiama tabella ciclica. Si risolve per tentativi: scegli un primo, togli ciò che copre e ripeti, confrontando le soluzioni ottenute. Per le tabelle grandi esiste un procedimento algebrico (il metodo di Petrick) che elenca tutte le coperture possibili.

Errori comuni

• Combinare termini con i trattini in posizioni diverse, come 0-01 con 00-1. Non è valido anche se sembrano differire per un bit.
• Dimenticare di segnare come usati i due termini di ogni combinazione, e poi elencare come primo qualcosa che non lo è.
• Mettere colonne per le condizioni X nella tabella di copertura, il che obbliga a coprirle senza necessità.
• Scegliere primi non essenziali prima di quelli essenziali. Prima assicura gli essenziali; poi decidi il resto.
• Scrivere male il termine a partire dal codice: in -0-1 la B va negata (vale 0), la D va non negata (vale 1), e A e C scompaiono.

Provalo nel simulatore

Il simulatore semplifica le funzioni con un procedimento di questo tipo, perciò puoi usarlo per controllare ogni fase del tuo lavoro a mano.

1. Crea una tabella di verità a quattro variabili e segna con 1 i mintermini dell'esempio.
2. Svolgi le fasi 1 e 2 sulla carta e scrivi il tuo risultato.
3. Osserva l'espressione minima fornita dallo strumento e la sua mappa di Karnaugh; individua quale gruppo corrisponde a ciascun implicante primo.
4. Converti in circuito le due soluzioni possibili nella stessa area di lavoro e cambia gli ingressi per confermare che danno sempre la stessa uscita.

Esercizi

1. Trova gli implicanti primi e l'espressione minima di F(A, B, C, D) = Σm(0, 1, 3, 7, 8, 9, 11, 15).
   Risposta

   Primi: -00- (BC), -0-1 (BD) e --11 (CD). La colonna 0 è coperta soltanto da BC, e la 7 soltanto da CD: entrambi sono essenziali e insieme coprono tutto. F = BC + CD. Il primo BD è superfluo.

2. Risolvi F(A, B, C) = Σm(0, 1, 2, 5, 6, 7). Ci sono primi essenziali?
   Risposta

   Le coppie sono 00-, 0-0, -01, -10, 1-1 e 11-, e nessuna si combina in un quartetto: sono sei primi. Ogni mintermine è coperto esattamente da due di essi, quindi non ci sono essenziali (tabella ciclica). Due soluzioni minime: AB + BC + AC, oppure AC + BC + AB.

3. Semplifica F(A, B, C, D) = Σm(2, 3, 7, 9, 11, 13) + d(1, 10, 15).
   Risposta

   Includendo le X nella fase 1 si ottengono quattro primi: -0-1 (BD), -01- (BC), --11 (CD) e 1--1 (AD). Nella tabella, senza colonne per 1, 10 e 15: il 2 è coperto soltanto da BC, il 7 soltanto da CD e il 13 soltanto da AD. Tutti e tre sono essenziali e coprono anche 3, 9 e 11. F = BC + CD + AD.

4. Perché nella fase 1 non si confronta il gruppo con un uno con il gruppo con tre uni?
   Risposta

   Perché due codici con uno e tre uni differiscono per almeno due bit, e per combinarsi devono differire esattamente per uno.