Tabellarische Quine-McCluskey-Methode
Im vorherigen Kapitel haben wir die K-Map-Methode besprochen, eine bequeme Methode zum Minimieren von Booleschen Funktionen auf bis zu 5 Variablen. Mit dieser Methode ist es jedoch schwierig, die Booleschen Funktionen mit mehr als 5 Variablen zu vereinfachen.
Die tabellarische Quine-McClukey-Methode ist eine tabellarische Methode, die auf dem Konzept der Hauptimplikanten basiert. Wir wissen dasprime implicant ist ein Produkt- (oder Summen-) Begriff, der nicht weiter reduziert werden kann, indem er mit anderen Produkt- (oder Summen-) Begriffen der angegebenen Booleschen Funktion kombiniert wird.
Diese tabellarische Methode ist nützlich, um die Hauptimplikanten durch wiederholtes Verwenden der folgenden booleschen Identität zu erhalten.
xy + xy '= x (y + y') = x.1 = x
Verfahren der tabellarischen Quine-McCluskey-Methode
Befolgen Sie diese Schritte, um die Booleschen Funktionen mithilfe der tabellarischen Quine-McClukey-Methode zu vereinfachen.
Step 1 - Ordnen Sie die angegebenen Mindestbedingungen in einem ascending orderund machen Sie die Gruppen basierend auf der Anzahl der in ihren binären Darstellungen vorhandenen. Also wird es gebenat most ‘n+1’ groups wenn es in einer Booleschen Funktion 'n' Boolesche Variablen oder 'n' Bits im binären Äquivalent von min Termen gibt.
Step 2 - Vergleichen Sie die in successive groups. Wenn sich nur die Ein-Bit-Position ändert, nehmen Sie das Paar dieser beiden Min-Terme. Platzieren Sie dieses Symbol '_' an der unterschiedlichen Bitposition und behalten Sie die verbleibenden Bits bei.
Step 3 - Wiederholen Sie Schritt 2 mit neu gebildeten Begriffen, bis wir alle erhalten prime implicants.
Step 4 - Formulieren Sie die prime implicant table. Es besteht aus einer Reihe von Zeilen und Spalten. Hauptimplikanten können zeilenweise und Min-Terme spaltenweise platziert werden. Platzieren Sie '1' in den Zellen, die den minimalen Begriffen entsprechen, die in jedem Hauptimplikanten enthalten sind.
Step 5- Finden Sie die wesentlichen Hauptimplikanten, indem Sie jede Spalte beobachten. Wenn die Mindestlaufzeit nur von einem Hauptimplikanten abgedeckt wird, ist dies der Fallessential prime implicant. Diese wesentlichen Hauptimplikanten werden Teil der vereinfachten Booleschen Funktion sein.
Step 6- Reduzieren Sie die Prim-Implikantentabelle, indem Sie die Zeile jedes wesentlichen Prim-Implikanten und die Spalten entfernen, die den Mindesttermen entsprechen, die in diesem wesentlichen Prim-Implikanten behandelt werden. Wiederholen Sie Schritt 5 für die Reduced Prime Implicant-Tabelle. Beenden Sie diesen Prozess, wenn alle Mindestterme der angegebenen Booleschen Funktion abgelaufen sind.
Beispiel
Lasst uns simplify die folgende Boolesche Funktion, $ f \ left (W, X, Y, Z \ right) = \ sum m \ left (2,6,8,9,10,11,14,15 \ right) $ unter Verwendung von Quine-McClukey tabellarische Methode.
Die angegebene Boolesche Funktion ist in sum of min termsbilden. Es hat 4 Variablen W, X, Y & Z. Die angegebenen Min-Terme sind 2, 6, 8, 9, 10, 11, 14 und 15. Die aufsteigende Reihenfolge dieser Min-Terme basiert auf der Anzahl der in ihnen vorhandenen Das binäre Äquivalent ist 2, 8, 6, 9, 10, 11, 14 und 15. Die folgende Tabelle zeigt diesemin terms and their equivalent binary Darstellungen.
| Gruppenname | Mindestlaufzeiten | 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 |
Die angegebenen Min-Terme sind in 4 Gruppen unterteilt, basierend auf der Anzahl der in ihren binären Äquivalenten vorhandenen. Die folgende Tabelle zeigt die möglichenmerging of min terms von benachbarten Gruppen.
| Gruppenname | Mindestlaufzeiten | 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 | - - |
Die Min-Terme, die sich nur in einer Ein-Bit-Position von benachbarten Gruppen unterscheiden, werden zusammengeführt. Dieses abweichende Bit wird mit dem Symbol '-' dargestellt. In diesem Fall gibt es drei Gruppen und jede Gruppe enthält Kombinationen von zwei Min-Termen. Die folgende Tabelle zeigt die möglichenmerging of min term pairs von benachbarten Gruppen.
| Gruppenname | Mindestlaufzeiten | 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 | - - |
Die aufeinanderfolgenden Gruppen von Min-Term-Paaren, die sich nur in der Ein-Bit-Position unterscheiden, werden zusammengeführt. Dieses abweichende Bit wird mit dem Symbol '-' dargestellt. In diesem Fall gibt es zwei Gruppen und jede Gruppe enthält Kombinationen von vier Minuten. Hier sind diese Kombinationen von 4-Minuten-Begriffen in zwei Zeilen verfügbar. So können wir die wiederholten Zeilen entfernen. Die reduzierte Tabelle nach dem Entfernen der redundanten Zeilen ist unten dargestellt.
| Gruppenname | Mindestlaufzeiten | W. | X. | Y. | Z. |
|---|---|---|---|---|---|
| GC1 | 2,6,10,14 | - - | - - | 1 | 0 |
| 8,9,10,11 | 1 | 0 | - - | - - | |
| GC2 | 10,11,14,15 | 1 | - - | 1 | - - |
Eine weitere Zusammenführung der Kombinationen von Min-Termen benachbarter Gruppen ist nicht möglich, da sie sich in mehr als einer Bitposition unterscheiden. Die obige Tabelle enthält drei Zeilen. Jede Zeile ergibt also einen Hauptimplikanten. deshalb, dieprime implicants sind YZ ', WX' & WY.
Das prime implicant table wird unten gezeigt.
| Mindestlaufzeiten / Hauptimplikanten | 2 | 6 | 8 | 9 | 10 | 11 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|
| YZ’ | 1 | 1 | 1 | 1 | ||||
| WX’ | 1 | 1 | 1 | 1 | ||||
| WY | 1 | 1 | 1 | 1 |
Die Hauptimplikanten werden zeilenweise und die Min-Terme spaltenweise platziert. 1s werden in die gemeinsamen Zellen der wichtigsten impliziten Zeilen und die entsprechenden Min-Term-Spalten eingefügt.
Die Mindestterme 2 und 6 werden nur von einem Hauptimplikanten abgedeckt YZ’. Also ist es einessential prime implicant. Dies wird Teil der vereinfachten Booleschen Funktion sein. Entfernen Sie nun diese primäre implizite Zeile und die entsprechenden Min-Term-Spalten. Die reduzierte primäre Implikantentabelle ist unten gezeigt.
| Mindestlaufzeiten / Hauptimplikanten | 8 | 9 | 11 | 15 |
|---|---|---|---|---|
| WX’ | 1 | 1 | 1 | |
| WY | 1 | 1 |
Die Mindestterme 8 und 9 werden nur von einem Hauptimplikanten abgedeckt WX’. Also ist es einessential prime implicant. Dies wird Teil der vereinfachten Booleschen Funktion sein. Entfernen Sie nun diese primäre implizite Zeile und die entsprechenden Min-Term-Spalten. Die reduzierte primäre Implikantentabelle ist unten gezeigt.
| Mindestlaufzeiten / Hauptimplikanten | 15 |
|---|---|
| WY | 1 |
Der Mindestterm 15 wird nur von einem Hauptimplikanten abgedeckt WY. Also ist es einessential prime implicant. Dies wird Teil der vereinfachten Booleschen Funktion sein.
In diesem Beispielproblem haben wir drei Hauptimplikanten und alle drei sind wesentlich. deshalb, diesimplified Boolean function ist
f(W,X,Y,Z) = YZ’ + WX’ + WY.