Metodo tabulare Quine-McCluskey
Nel capitolo precedente, abbiamo discusso il metodo K-map, che è un metodo conveniente per ridurre al minimo le funzioni booleane fino a 5 variabili. Tuttavia, è difficile semplificare le funzioni booleane con più di 5 variabili utilizzando questo metodo.
Il metodo tabulare di Quine-McClukey è un metodo tabulare basato sul concetto di primi implicanti. Lo sappiamoprime implicant è un termine prodotto (o somma), che non può essere ulteriormente ridotto combinando con qualsiasi altro termine prodotto (o somma) della funzione booleana data.
Questo metodo tabulare è utile per ottenere i primi implicanti utilizzando ripetutamente la seguente identità booleana.
xy + xy '= x (y + y') = x.1 = x
Procedura del metodo tabulare Quine-McCluskey
Seguire questi passaggi per semplificare le funzioni booleane utilizzando il metodo tabulare Quine-McClukey.
Step 1 - Disporre i termini minimi dati in un file ascending ordere creare i gruppi in base al numero di quelli presenti nelle loro rappresentazioni binarie. Quindi ci saràat most ‘n+1’ groups se ci sono 'n' variabili booleane in una funzione booleana o 'n' bit nell'equivalente binario dei termini min.
Step 2 - Confronta i termini minimi presenti in successive groups. Se c'è un cambiamento solo nella posizione di un bit, prendi la coppia di questi due termini minimi. Posizionare questo simbolo "_" nella posizione del bit diverso e mantenere i bit rimanenti così com'è.
Step 3 - Ripeti il passaggio 2 con i termini appena formati finché non otteniamo tutti prime implicants.
Step 4 - Formulare il file prime implicant table. Consiste di un insieme di righe e colonne. I primi implicanti possono essere inseriti in riga e i termini minimi possono essere inseriti in colonna. Posiziona "1" nelle celle corrispondenti ai termini minimi che sono coperti in ogni primo implicante.
Step 5- Trova i primi implicanti essenziali osservando ciascuna colonna. Se il termine minimo è coperto solo da un primo implicante, allora lo èessential prime implicant. Questi primi implicanti essenziali faranno parte della funzione booleana semplificata.
Step 6- Ridurre la tabella dei primi implicanti rimuovendo la riga di ogni primo implicante essenziale e le colonne corrispondenti ai termini minimi che sono coperti in quel primo implicante essenziale. Ripetere il passaggio 5 per la tabella implicante prime ridotte. Interrompi questo processo quando tutti i termini minimi di una determinata funzione booleana sono terminati.
Esempio
Lasciateci simplify la seguente funzione booleana, $ f \ left (W, X, Y, Z \ right) = \ sum m \ left (2,6,8,9,10,11,14,15 \ right) $ usando Quine-McClukey metodo tabulare.
La funzione booleana data è in sum of min termsmodulo. Ha 4 variabili W, X, Y e Z. I termini minimi dati sono 2, 6, 8, 9, 10, 11, 14 e 15. L'ordine ascendente di questi termini minimi basato sul numero di quelli presenti nel loro l'equivalente binario è 2, 8, 6, 9, 10, 11, 14 e 15. La tabella seguente li mostramin terms and their equivalent binary rappresentazioni.
| Nome del gruppo | Termini minimi | W | X | Y | Z |
|---|---|---|---|---|---|
| GA1 | 2 | 0 | 0 | 1 | 0 |
| 8 | 1 | 0 | 0 | 0 | |
| GA2 | 6 | 0 | 1 | 1 | 0 |
| 9 | 1 | 0 | 0 | 1 | |
| 10 | 1 | 0 | 1 | 0 | |
| 11 | 1 | 0 | 1 | 1 | |
| 14 | 1 | 1 | 1 | 0 | |
| GA4 | 15 | 1 | 1 | 1 | 1 |
I termini minimi forniti sono organizzati in 4 gruppi in base al numero di quelli presenti nei loro equivalenti binari. La tabella seguente mostra il possibilemerging of min terms da gruppi adiacenti.
| Nome del gruppo | Termini minimi | W | X | Y | Z |
|---|---|---|---|---|---|
| GB1 | 2,6 | 0 | - | 1 | 0 |
| 2,10 | - | 0 | 1 | 0 | |
| 8,9 | 1 | 0 | 0 | - | |
| 8,10 | 1 | 0 | - | 0 | |
| GB2 | 6,14 | - | 1 | 1 | 0 |
| 9,11 | 1 | 0 | - | 1 | |
| 10,11 | 1 | 0 | 1 | - | |
| 10,14 | 1 | - | 1 | 0 | |
| 11,15 | 1 | - | 1 | 1 | |
| 14,15 | 1 | 1 | 1 | - |
I termini minimi, che differiscono solo nella posizione di un bit dai gruppi adiacenti, vengono uniti. Quel bit diverso è rappresentato con questo simbolo, '-'. In questo caso, ci sono tre gruppi e ogni gruppo contiene combinazioni di due termini min. La tabella seguente mostra il possibilemerging of min term pairs da gruppi adiacenti.
| Nome del gruppo | Termini minimi | W | X | Y | Z |
|---|---|---|---|---|---|
| GB1 | 2,6,10,14 | - | - | 1 | 0 |
| 2,10,6,14 | - | - | 1 | 0 | |
| 8,9,10,11 | 1 | 0 | - | - | |
| 8,10,9,11 | 1 | 0 | - | - | |
| GB2 | 10,11,14,15 | 1 | - | 1 | - |
| 10,14,11,15 | 1 | - | 1 | - |
I gruppi successivi di coppie di termini min, che differiscono solo nella posizione di un bit, vengono uniti. Quel bit diverso è rappresentato con questo simbolo, '-'. In questo caso, ci sono due gruppi e ogni gruppo contiene combinazioni di quattro termini min. Qui, queste combinazioni di termini di 4 min sono disponibili su due righe. Quindi, possiamo rimuovere le righe ripetute. La tabella ridotta dopo aver rimosso le righe ridondanti è mostrata di seguito.
| Nome del gruppo | Termini minimi | W | X | Y | Z |
|---|---|---|---|---|---|
| GC1 | 2,6,10,14 | - | - | 1 | 0 |
| 8,9,10,11 | 1 | 0 | - | - | |
| GC2 | 10,11,14,15 | 1 | - | 1 | - |
Non è possibile unire ulteriormente le combinazioni di termini min da gruppi adiacenti, poiché differiscono per posizioni di più di un bit. Ci sono tre righe nella tabella sopra. Quindi, ogni riga darà un primo implicante. quindi, ilprime implicants sono YZ ', WX' e WY.
Il prime implicant table è mostrato sotto.
| Termini minimi / Prime implicazioni | 2 | 6 | 8 | 9 | 10 | 11 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|
| YZ’ | 1 | 1 | 1 | 1 | ||||
| WX’ | 1 | 1 | 1 | 1 | ||||
| WY | 1 | 1 | 1 | 1 |
I primi implicanti sono posti in riga e i termini min sono posti in colonna. Gli 1 vengono inseriti nelle celle comuni delle prime righe implicanti e nelle corrispondenti colonne del termine minimo.
I termini minimi 2 e 6 sono coperti solo da un primo implicante YZ’. Quindi è un fileessential prime implicant. Questo farà parte della funzione booleana semplificata. Ora, rimuovi questa prima riga implicante e le corrispondenti colonne del termine minimo. La tabella dei primi implicanti ridotti è mostrata di seguito.
| Termini minimi / Prime implicazioni | 8 | 9 | 11 | 15 |
|---|---|---|---|---|
| WX’ | 1 | 1 | 1 | |
| WY | 1 | 1 |
I termini minimi 8 e 9 sono coperti solo da un primo implicante WX’. Quindi è un fileessential prime implicant. Questo farà parte della funzione booleana semplificata. Ora, rimuovi questa prima riga implicante e le corrispondenti colonne del termine minimo. La tabella dei primi implicanti ridotti è mostrata di seguito.
| Termini minimi / Prime implicazioni | 15 |
|---|---|
| WY | 1 |
Il termine minimo 15 è coperto solo da un primo implicante WY. Quindi è un fileessential prime implicant. Questo farà parte della funzione booleana semplificata.
In questo problema di esempio, abbiamo tre implicanti primi e tutti e tre sono essenziali. quindi, ilsimplified Boolean function è
f(W,X,Y,Z) = YZ’ + WX’ + WY.