1. Was ein Karnaugh-Diagramm ist
Ein Karnaugh-Diagramm ist eine Wahrheitstabelle, neu gezeichnet als Raster. Maurice Karnaugh stellte es 1953 in den Bell Labs vor, um Schaltnetze mit dem Auge zu vereinfachen, und es ist bis heute der schnellste Weg, eine kleine boolesche Funktion von Hand zu minimieren: keine Algebra, keine Gesetze zum Auswendiglernen, nur Rechtecke.
Jedes Feld des Diagramms enthält eine Zeile der Wahrheitstabelle. Mehr als eine Umsortierung wird daraus durch die Reihenfolge, in der diese Zeilen stehen: benachbarte Felder unterscheiden sich in genau einer Variablen.
Diese eine Eigenschaft erledigt die ganze Arbeit. Sind zwei benachbarte Felder beide wahr, dann kann die Variable, die sich zwischen ihnen ändert, nicht der Grund dafür sein - sie fällt weg, und ein einziger Term deckt beide Felder ab. Vereinfachen heißt damit: die größtmöglichen Rechtecke zeichnen.
2. Warum die Spalten unsortiert wirken
Die Spalten eines Karnaugh-Diagramms zählen nicht 00, 01, 10, 11. Sie laufen 00, 01, 11, 10 - der reflektierte Gray-Code, eine Ordnung, in der sich jeder Wert vom nächsten in genau einem Bit unterscheidet. Binäres Zählen würde 01 neben 10 stellen, und die unterscheiden sich in zwei Bits: benachbarte Felder sagten dann nichts mehr aus.
| A \ BC | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 0 | 1 | 3 | 2 |
| 1 | 4 | 5 | 7 | 6 |
Auch die Ränder sind benachbart. Die erste und die letzte Spalte unterscheiden sich in einer Variablen, ebenso die erste und die letzte Zeile - eine Gruppe darf also über einen Rand hinauslaufen und auf der anderen Seite weitergehen, weshalb die vier Ecken eines Diagramms mit vier Variablen eine einzige Gruppe bilden. Ein Karnaugh-Diagramm ist eigentlich auf einem Torus gezeichnet; das flache Blatt ist nur bequemer.
3. Die Einsen gruppieren
Um eine minimale Summe von Produkten abzulesen, deckt man jedes Feld mit einer 1 durch rechteckige Gruppen ab - nach vier Regeln:
- Eine Gruppe ist ein Rechteck aus 1, 2, 4, 8 … Feldern - je Seite eine Zweierpotenz.
- Eine Gruppe darf über die Ränder des Diagramms hinweggehen, waagerecht, senkrecht oder beides.
- Gruppen dürfen sich überlappen. Ein doppelt abgedecktes Feld kostet nichts; ein nicht abgedecktes verändert die Funktion.
- Mache jede Gruppe so groß wie möglich und verwende dann so wenige Gruppen, wie alle Einsen abdecken.
Jede Gruppe wird zu einem Term. Man liest ihn ab, indem man fragt, welche Variablen über die ganze Gruppe hinweg gleich bleiben: die stehen im Term - unverändert, wo sie 1 sind, negiert, wo sie 0 sind - und jede Variable, die sich ändert, fällt weg. Eine Gruppe aus zwei Feldern verliert eine Variable, eine aus vier verliert zwei, eine aus acht verliert drei. Der minimale Ausdruck ist die Disjunktion der Terme.
4. Ein durchgerechnetes Beispiel
Nehmen wir (A ∧ B) ∨ (¬A ∧ C) ∨ (B ∧ C ∧ D). Das Diagramm hat vier Variablen: A und B in den Zeilen, C und D in den Spalten.
| AB \ CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 0 | 0 | 1 | 1 |
| 01 | 0 | 0 | 1 | 1 |
| 11 | 1 | 1 | 1 | 1 |
| 10 | 0 | 0 | 0 | 0 |
Zwei Gruppen decken alle Einsen ab. Die eine ist der Block aus vier Feldern in den beiden Zeilen mit A = 0 und den beiden Spalten mit C = 1: darin ändern sich B und D, sie fallen also weg und der Term ist ¬A ∧ C. Die andere ist die ganze Zeile, in der A und B beide 1 sind, über alle vier Spalten: C und D ändern sich darin, übrig bleibt A ∧ B.
Die Minimalform ist also (¬A ∧ C) ∨ (A ∧ B). Der dritte Term des Originals, B ∧ C ∧ D, ist verschwunden: jedes Feld, das er abdeckte, war bereits von einer der beiden Gruppen abgedeckt. Genau so sieht Absorption aus, wenn man sie sehen kann.
5. Primimplikanten und wesentliche Implikanten
Eine Gruppe, die sich nicht weiter vergrößern lässt, heißt Primimplikant. Die Primimplikanten aufzuzählen ist die leichte Hälfte des Problems; auszuwählen, welche davon bleiben, ist die Hälfte, die schiefgeht.
Wird ein Feld nur von einem einzigen Primimplikanten abgedeckt, so ist dieser wesentlich: keine Minimalform kann ihn weglassen, weil nichts sonst dieses Feld abdeckt. Nimm zuerst die wesentlichen Implikanten und decke den Rest dann mit so wenigen der übrigen Gruppen wie möglich ab.
Gierig vorzugehen - immer wieder die größte noch verfügbare Gruppe zu nehmen - ist verlockend und geht nicht immer gut. Auf einer zyklischen Tafel, auf der kein Implikant wesentlich ist und jedes Feld doppelt abgedeckt wird, kann die gierige Wahl mit einem Term mehr enden als die beste Lösung. Das Diagramm auf dieser Seite durchsucht die verbleibenden Möglichkeiten stattdessen vollständig, was bei vier Variablen nichts kostet.
6. Stattdessen die Nullen gruppieren
Alles Bisherige funktioniert genauso gut mit den Nullen. Decke sie mit denselben Rechtecken ab, lies jede Gruppe mit negierten Literalen - eine Variable, die in der ganzen Gruppe 1 ist, erscheint negiert, eine, die 0 ist, unverändert - und verbinde die Gruppen mit ∧ statt mit ∨.
Das Ergebnis ist ein Produkt von Summen: eine Konjunktion von Disjunktionen, die genau in den Feldern falsch ist, in denen der Ausdruck falsch ist, und damit überall sonst wahr. Welche der beiden Formen kürzer ist, hängt von der Funktion ab - eine Formel mit wenigen Einsen hat eine kurze Summe von Produkten, eine mit wenigen Nullen ein kurzes Produkt von Summen -, es lohnt sich also, beide abzulesen, bevor man wählt.
7. Größere Diagramme und Don't-Care-Felder
Fünf und sechs Variablen lassen sich als zwei oder vier übereinandergelegte Diagramme mit vier Variablen zeichnen, wobei Felder an gleicher Stelle benachbarter Ebenen als benachbart gelten. Das funktioniert, aber die Nachbarschaft, die das Verfahren anschaulich machte, muss man sich nun merken, statt sie zu sehen. Darüber hinaus leistet der Quine-McCluskey-Algorithmus dasselbe in Tabellenform: er ist die mechanische Fassung genau dieser Gruppierung - und er läuft hinter den Diagrammen hier.
Der Hardwareentwurf fügt noch einen Gedanken hinzu. Manche Eingangskombinationen treten nie auf - eine BCD-Ziffer ist nie 1010 -, dem Entwerfer ist also gleichgültig, was die Schaltung damit tut. Solche Felder werden mit X markiert und dürfen als der Wert gelesen werden, der die Gruppen größer macht. Die Diagramme in diesem Rechner entstehen aus einer Formel, die jeder Belegung einen Wert gibt, also ist hier kein Feld je ein Don't-Care.
8. Probiere es selbst
Gib im Rechner einen Ausdruck mit zwei bis vier Variablen ein, und sein Diagramm erscheint unter der Wahrheitstabelle - jede Gruppe in eigener Farbe umrandet und die Minimalform darunter ausgeschrieben. Schalte auf Produkt von Summen um, um stattdessen die Nullen gruppiert zu sehen.