Lernen › Thema 5
Das Quine-McCluskey-Verfahren Schritt für Schritt
7 Min. Lesezeit · bitGateLab-Team
Das Karnaugh-Diagramm ist bei vier Variablen schnell, hängt aber von deinem Blick ab und wird ab fünf Variablen unpraktisch. Das Quine-McCluskey-Verfahren erledigt dieselbe Arbeit mit Tabellen und mechanischen Regeln: Es braucht keine Intuition, findet immer alle Primimplikanten und ist die Grundlage der Programme, die logische Funktionen vereinfachen. Hier lernst du seine beiden Phasen kennen, erkennst die wesentlichen Primimplikanten und löst ein vollständiges Beispiel mit vier Variablen.
Begriffe: Implikanten und Primimplikanten
- Ein Implikant von F ist ein Produktterm, der garantiert, dass F gleich 1 ist, sobald er selbst 1 ist. Jeder Minterm von F ist ein Implikant, ebenso jeder gültige Block eines Karnaugh-Diagramms.
- Ein Primimplikant ist ein Implikant, der sich nicht weiter vergrößern lässt; nimmst du ihm eine Variable weg, überdeckt er eine Zeile, in der F gleich 0 ist. Er entspricht einem maximalen Block im Diagramm.
- Ein wesentlicher Primimplikant ist ein Primimplikant, der mindestens einen Minterm überdeckt, den kein anderer Primimplikant überdeckt. Er muss in jeder Minimallösung vorkommen.
Das Verfahren hat zwei Phasen: Zuerst findet es durch Zusammenfassen von Termen alle Primimplikanten; danach wählt es die kleinste Menge von Primimplikanten aus, die alle Minterme überdeckt.
Phase 1: Terme zusammenfassen
Jeder Term wird binär geschrieben, und die Stelle einer eliminierten Variablen wird mit einem Strich markiert. Mit den Variablen A, B, C, D bedeutet der Term 0-11 zum Beispiel ACD (B wurde eliminiert).
- Ordne die Minterme in Gruppen nach der Anzahl der Einsen in ihrem Binärcode.
- Vergleiche jeden Term einer Gruppe mit jedem Term der nächsten Gruppe. Unterscheiden sie sich in nur einem Bit, fasse sie zusammen, indem du an dieser Stelle einen Strich setzt, und hake die beiden ursprünglichen Terme als verwendet ab.
- Wiederhole das mit der neuen Liste. Zusammengefasst werden nur Terme, deren Striche an denselben Stellen stehen.
- Wenn sich nichts mehr zusammenfassen lässt, sind die Terme, die nie abgehakt wurden, die Primimplikanten.
Phase 2: Primimplikantentabelle
Man stellt eine Tabelle auf mit einer Zeile für jeden Primimplikanten und einer Spalte für jeden Minterm der Funktion (Don't-Care-Bedingungen bekommen keine Spalte). Man markiert, welche Minterme jeder Primimplikant überdeckt. Danach:
- Suche Spalten mit nur einer Markierung. Der Primimplikant dieser Zeile ist wesentlich: Wähle ihn aus und streiche alle Spalten, die er überdeckt.
- Wähle für die verbleibenden Spalten die kleinste Anzahl von Primimplikanten, die sie überdeckt. Überdecken zwei Primimplikanten dasselbe, ist jeder von beiden geeignet; bevorzuge den mit weniger Literalen.
Vollständiges Beispiel. Vereinfache F(A, B, C, D) = Σm(0, 2, 3, 5, 7, 8, 10, 11, 13, 15).
Schritt 1. Nach der Anzahl der Einsen gruppieren.
| Einsen | Minterme |
|---|---|
| 0 | 0 (0000) |
| 1 | 2 (0010), 8 (1000) |
| 2 | 3 (0011), 5 (0101), 10 (1010) |
| 3 | 7 (0111), 11 (1011), 13 (1101) |
| 4 | 15 (1111) |
Schritt 2. Erstes Zusammenfassen (Paare). Verglichen werden benachbarte Gruppen. Die 8 lässt sich weder mit der 3 noch mit der 5 zusammenfassen, weil sie sich in mehr als einem Bit unterscheiden.
| Gruppen | Gebildete Paare |
|---|---|
| 0 und 1 | (0,2) 00-0; (0,8) -000 |
| 1 und 2 | (2,3) 001-; (2,10) -010; (8,10) 10-0 |
| 2 und 3 | (3,7) 0-11; (3,11) -011; (5,7) 01-1; (5,13) -101; (10,11) 101- |
| 3 und 4 | (7,15) -111; (11,15) 1-11; (13,15) 11-1 |
Alle zehn Minterme sind als verwendet abgehakt; es gibt 13 Paare.
Schritt 3. Zweites Zusammenfassen (Vierergruppen). Zusammengefasst werden Paare mit dem Strich an derselben Stelle, die sich in einem Bit unterscheiden:
- (0,2) mit (8,10) oder auch (0,8) mit (2,10): -0-0, überdeckt 0, 2, 8, 10.
- (2,3) mit (10,11) oder (2,10) mit (3,11): -01-, überdeckt 2, 3, 10, 11.
- (3,7) mit (11,15) oder (3,11) mit (7,15): --11, überdeckt 3, 7, 11, 15.
- (5,7) mit (13,15) oder (5,13) mit (7,15): -1-1, überdeckt 5, 7, 13, 15.
Alle 13 Paare wurden in irgendeiner Vierergruppe verwendet. Die vier Vierergruppen lassen sich untereinander nicht mehr zusammenfassen (keine hat die Striche an denselben Stellen wie eine andere und unterscheidet sich von ihr in nur einem Bit). Die Primimplikanten sind daher:
- P1 = -0-0 = BD
- P2 = -01- = BC
- P3 = --11 = CD
- P4 = -1-1 = BD
Schritt 4. Überdeckungstabelle.
| Primimplikant | 0 | 2 | 3 | 5 | 7 | 8 | 10 | 11 | 13 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|
| P1 BD | ✔ | ✔ | ✔ | ✔ | ||||||
| P2 BC | ✔ | ✔ | ✔ | ✔ | ||||||
| P3 CD | ✔ | ✔ | ✔ | ✔ | ||||||
| P4 BD | ✔ | ✔ | ✔ | ✔ |
Schritt 5. Wesentliche Primimplikanten. Die Spalten 0 und 8 haben nur bei P1 eine Markierung, also ist P1 wesentlich. Die Spalten 5 und 13 haben nur bei P4 eine Markierung, also ist auch P4 wesentlich. Zusammen überdecken sie 0, 2, 5, 7, 8, 10, 13 und 15.
Schritt 6. Den Rest überdecken. Es fehlen die Minterme 3 und 11. P2 überdeckt beide, P3 ebenfalls. Jeder der beiden vervollständigt die Lösung mit derselben Anzahl von Literalen.
Ergebnis: F = BD + BD + BC oder auch F = BD + BD + CD. Beide haben drei Terme und sechs Literale.
Zeichnest du diese Funktion in ein Karnaugh-Diagramm, dann sind P1 die vier Ecken, P4 ist der Mittelblock, P2 sind die Spalten 11 und 10 der Zeilen 00 und 10 (über den Rand verbunden), und P3 ist die gesamte Spalte 11. Das tabellarische Verfahren kommt zum selben Ergebnis, ohne dass man das Diagramm sehen muss.
Don't-Care-Bedingungen und zyklische Tabellen
Die X-Bedingungen werden in Phase 1 wie Einsen einbezogen, weil sie helfen können, größere Implikanten zu bilden. In Phase 2 lässt man sie weg: Sie bekommen keine Spalte, da sie nicht überdeckt werden müssen. Ein Primimplikant, der nur aus X besteht, wird nie benötigt.
Manchmal hat nach der Auswahl der wesentlichen Primimplikanten, oder schon von Anfang an, jede Spalte mindestens zwei Markierungen, und es gibt keinen offensichtlichen Weg zur Entscheidung. Diese Situation nennt man zyklische Tabelle. Man löst sie durch Ausprobieren: Du wählst einen Primimplikanten, entfernst alles, was er überdeckt, wiederholst das und vergleichst die Lösungen, die sich ergeben. Für große Tabellen gibt es ein algebraisches Verfahren (das Petrick-Verfahren), das alle möglichen Überdeckungen aufzählt.
Häufige Fehler
- Terme mit Strichen an unterschiedlichen Stellen zusammenzufassen, etwa 0-01 mit 00-1. Das ist nicht zulässig, auch wenn sie sich scheinbar nur in einem Bit unterscheiden.
- Zu vergessen, die beiden Terme jeder Zusammenfassung als verwendet abzuhaken, und dann etwas als Primimplikanten aufzulisten, das keiner ist.
- In der Überdeckungstabelle Spalten für die X-Bedingungen anzulegen, was dazu zwingt, sie unnötig zu überdecken.
- Nicht wesentliche Primimplikanten vor den wesentlichen auszuwählen. Sichere zuerst die wesentlichen; entscheide dann über den Rest.
- Den Term falsch aus dem Code abzulesen: In -0-1 steht B negiert (es ist 0), D steht nicht negiert (es ist 1), und A und C entfallen.
Probiere es im Simulator aus
Der Simulator vereinfacht Funktionen mit einem Verfahren dieser Art. Du kannst ihn also nutzen, um jede Phase deiner Handrechnung zu überprüfen.
- Lege eine Wahrheitstabelle mit vier Variablen an und setze die Minterme des Beispiels auf 1.
- Führe die Phasen 1 und 2 auf Papier durch und schreibe dein Ergebnis auf.
- Sieh dir den minimalen Ausdruck an, den das Werkzeug liefert, und sein Karnaugh-Diagramm; ordne jedem Primimplikanten den passenden Block zu.
- Wandle die beiden möglichen Lösungen auf derselben Schaltungsfläche in Schaltungen um und schalte die Eingänge durch, um zu bestätigen, dass sie immer denselben Ausgang liefern.
Übungen
- Bestimme die Primimplikanten und den minimalen Ausdruck von F(A, B, C, D) = Σm(0, 1, 3, 7, 8, 9, 11, 15).
Lösung
Primimplikanten: -00- (BC), -0-1 (BD) und --11 (CD). Die Spalte 0 wird nur von BC überdeckt und die Spalte 7 nur von CD: Beide sind wesentlich und überdecken zusammen alles. F = BC + CD. Der Primimplikant BD ist überflüssig.
- Löse F(A, B, C) = Σm(0, 1, 2, 5, 6, 7). Gibt es wesentliche Primimplikanten?
Lösung
Die Paare sind 00-, 0-0, -01, -10, 1-1 und 11-, und keines lässt sich zu einer Vierergruppe zusammenfassen: Es sind sechs Primimplikanten. Jeder Minterm wird von genau zweien überdeckt, es gibt also keine wesentlichen (zyklische Tabelle). Zwei Minimallösungen: AB + BC + AC oder AC + BC + AB.
- Vereinfache F(A, B, C, D) = Σm(2, 3, 7, 9, 11, 13) + d(1, 10, 15).
Lösung
Bezieht man die X in Phase 1 ein, ergeben sich vier Primimplikanten: -0-1 (BD), -01- (BC), --11 (CD) und 1--1 (AD). In der Tabelle, ohne Spalten für 1, 10 und 15: Die 2 wird nur von BC überdeckt, die 7 nur von CD und die 13 nur von AD. Alle drei sind wesentlich und überdecken auch 3, 9 und 11. F = BC + CD + AD.
- Warum vergleicht man in Phase 1 die Gruppe mit einer Eins nicht mit der Gruppe mit drei Einsen?
Lösung
Weil sich zwei Codes mit einer und mit drei Einsen in mindestens zwei Bits unterscheiden; zum Zusammenfassen müssen sie sich aber in genau einem unterscheiden.