Karnaugh-Veitch-Diagramm

Grundidee und Nutzen

Das Karnaugh-Veitch-Diagramm, kurz KV-Diagramm, Karnaugh-Tafel oder K-Diagramm, ist eine grafische Methode zur Darstellung und Vereinfachung Boolescher Funktionen. Eine Boolesche Funktion arbeitet mit Wahrheitswerten, meist 0 und 1. Das Ziel ist, aus einer gegebenen Funktion einen möglichst kurzen logischen Ausdruck zu gewinnen, der dieselbe Ausgabe liefert.

Das Verfahren wurde 1952 von Edward W. Veitch entworfen und 1953 von Maurice Karnaugh zur heutigen Form weiterentwickelt. Es wird besonders in der Digitaltechnik verwendet, etwa beim Entwurf logischer Schaltungen. Außerdem kann ein KV-Diagramm helfen, Hazards zu erkennen und zu beseitigen. Hazards sind unerwünschte kurze Fehlzustände in Schaltungen.

Ein KV-Diagramm kann jede disjunktive Normalform (DNF) in einen minimalen disjunktiven logischen Ausdruck umwandeln. Eine DNF ist eine Oder-Verknüpfung von Und-Termen. Der entstehende Term ist meist minimal; falls nicht, kann er durch Ausklammern mit dem Distributivgesetz weiter vereinfacht werden. Die inverse Funktion F̄ erhält man, indem man im Diagramm die Werte 1 und 0 vertauscht.

Aufbau und Ausfüllen

Ein KV-Diagramm mit n Eingangsvariablen besitzt 2^n Felder. Die Variablen stehen an den Rändern des Diagramms jeweils in negierter und nicht negierter Form. Wichtig ist die Anordnung nach dem Gray-Code: Horizontal und vertikal benachbarte Felder dürfen sich nur in genau einer Variablen unterscheiden.

Zum Ausfüllen wird zuerst eine Wahrheitstabelle der zu optimierenden Funktion erstellt. In jedes Feld kommt eine 1, wenn für die entsprechende Kombination der Eingangsvariablen ein Minterm der Funktion vorliegt; sonst kommt eine 0 hinein. Ein Minterm m liegt vor, wenn gilt: m(X) = 1 ⇒ F(X) = 1. Dabei ist X der Vektor der Eingangsvariablen. In einer disjunktiven Normalform gilt das für jeden Konjunktionsterm, der 1 liefert, weil dann auch die gesamte Oder-Verknüpfung und damit die Funktion 1 liefert.

KV-Diagramme eignen sich besonders für Funktionen mit höchstens etwa 4 bis 6 Eingangsvariablen. Bis 4 Variablen bleiben sie übersichtlich. Für 4 Signale gibt es 16 Einträge, die den Binärwerten 0000 = 0, 0001 = 1, 0010 = 2, …, 1110 = 14, 1111 = 15 zugeordnet werden können. Solche Nummerierungen erleichtern das schnelle Übertragen aus einer Wahrheitstabelle.

Vereinfachungsmethoden

Bei der Vereinfachung entscheidet man häufig danach, ob weniger Felder mit 1 oder mit 0 belegt sind. Sind weniger Einsen vorhanden, verwendet man die Minterm-Methode. Sind weniger Nullen vorhanden, verwendet man die Maxterm-Methode.

Bei der Minterm-Methode werden benachbarte 1-Felder zu rechteckigen zusammenhängenden Blöcken, auch Päckchen genannt, zusammengefasst. Erlaubte Blockgrößen sind Potenzen von 2, also 1, 2, 4, 8, 16, 32 usw. Alle 1-Felder müssen durch Blöcke erfasst werden. Ein Block darf über den Rand hinaus fortgesetzt werden, weil die Randfelder in der KV-Struktur benachbart sein können: Bei drei Variablen kann man sich das Diagramm wie einen Zylinder vorstellen, bei vier Variablen wie einen Torus, also eine Donut-Form. Die vier Ecken eines quadratisch gezeichneten KV-Diagramms mit vier Variablen sind daher benachbart.

Aus den gefundenen Blöcken wählt man so viele aus, dass alle Einsen überdeckt sind. Größere Blöcke sind günstiger, weil sie kürzere Terme ergeben. Jeder ausgewählte Block wird in einen Konjunktionsterm, also einen Und-Term, umgewandelt. Variablen, die innerhalb eines Blocks sowohl negiert als auch nicht negiert auftreten, werden weggelassen. Die so entstehenden Und-Terme werden anschließend durch Oder verknüpft und ergeben eine disjunktive Minimalform.

Die Maxterm-Methode arbeitet entsprechend mit den Nullen statt mit den Einsen. Ein Päckchen bildet dabei einen Disjunktionsterm, also einen Oder-Term. Diese Disjunktionsterme werden konjunktiv, also mit Und, verknüpft. Zusätzlich werden die Variablen einzeln negiert.

Eine weitere Möglichkeit ist die Ringsummen-Methode. Sie liest eine Ringsummen-Normalform aus dem KV-Diagramm ab. Da dort nur Minterme ohne Negation vorkommen, dürfen nur Blöcke gebildet werden, die keine Negation enthalten. Durch mehrfache Überdeckung muss gelten: Für alle Nullen liegt eine gerade Anzahl von Überdeckungen vor, für alle Einsen eine ungerade Anzahl. Verwendet werden die Regeln T ⊕ T = 0 und T ⊕ T ⊕ T = T. Jeder Block liefert einen Minterm; die Minterme werden mit XOR verknüpft. Die Ringsummen-Normalform ist bis auf die Reihenfolge der Minterme eindeutig.

Regeln für Gruppen

Die wichtigste Regel lautet: Man sucht eine vollständige Überdeckung der Einsen mit möglichst großen rechteckigen Blöcken. Benachbarte Felder mit einer 1 werden zu Gruppen zusammengefasst. Diagonal berührende Felder zählen nicht als benachbart. Eine Gruppe darf keine Nullen enthalten; wenn Nullen nicht eingetragen werden, darf eine Gruppe entsprechend keine leeren Felder enthalten.

Alle Einsen müssen in Gruppen vorkommen. Die Gruppen sollen möglichst groß sein, und es sollen möglichst wenige Gruppen entstehen. Ihre Größen müssen Zweierpotenzen sein: 1, 2, 4, 8, 16, 32, 64 usw. Gruppen müssen rechteckige Blöcke bilden, dürfen sich aber überlappen und über die Ränder des Diagramms hinweggehen. Zwei Gruppen dürfen nicht exakt dieselben Einsen umfassen, und keine Gruppe darf vollständig von einer anderen Gruppe umschlossen sein.

Für die Reduzierung gilt: Eine Gruppe der Größe 2^n reduziert den logischen Ausdruck um n Variablen. Eine Achtergruppe (2^3) reduziert also um 3 Variablen, eine Vierergruppe (2^2) um 2 Variablen, eine Zweiergruppe (2^1) um 1 Variable und eine Einergruppe (2^0) um keine Variable. Das gilt unabhängig von Lage, Form und Randüberschreitung der Gruppe.

Normalformen und besondere Fälle

Bei KV-Diagrammen unterscheidet man vor allem zwischen disjunktiver Normalform (DNF) und konjunktiver Normalform (KNF). Die DNF entsteht aus den Zeilen der Wahrheitstabelle, in denen der Ausgabewert 1 ist. Steht bei einer Eingangsvariablen in einer solchen Zeile eine 0, wird diese Variable negiert geschrieben. Die einzelnen Terme werden mit ∨ verbunden.

Die KNF entsteht aus den Zeilen der Wahrheitstabelle, in denen der Ausgabewert 0 ist. Dabei werden Eingangsvariablen, für die eine 1 steht, negiert geschrieben. Die Literale innerhalb eines Terms werden mit ∨ verbunden, die gesamten Terme mit ∧.

Manchmal gibt es Wahrheitstabellen, in denen für bestimmte Eingangskombinationen kein fester Ausgangswert benötigt wird. Diese Zustände heißen Don’t-Care-Terme und werden mit X bezeichnet. Sie dürfen je nach Vorteil als 1 oder 0 betrachtet werden, um bei der Minterm- oder Maxterm-Methode größere Blöcke zu bilden. Ein Beispiel ist die Dekodierung einer binär codierten Dezimalzahl (BCD): Dort spielen nur die Zahlen 0 bis 9 eine Rolle; die sogenannten Pseudotetraden dürfen ein beliebiges Ergebnis liefern.

Hat eine Digitalschaltung mehrere Ausgänge, dann besitzt die Wahrheitstabelle mehrere Ergebnisspalten. Für jeden Ausgang muss ein eigenes KV-Diagramm erstellt werden. Ein Beispiel ist ein 2+2-Bit-Komparator mit vier Eingangsvariablen und drei Ausgangsvariablen: Die Zahl A besteht aus A1 und A0, die Zahl B aus B1 und B0. Die Ausgänge X, Y und Z zeigen an, ob A < B, A = B oder A > B gilt.

Anschauliche Deutung und Erweiterung

Das KV-Diagramm kann als abgewandelte, abstrakte Form eines Venn-Diagramms verstanden werden. In der Mengenalgebra betrachtet man dabei Teilmengen von Mintermen, die an der Funktion beteiligt sind.

Eine weitere Veranschaulichung erfolgt über Hyper-Einheitswürfel. Boolesche Funktionen mit n Variablen lassen sich mit Einheitswürfeln der Dimension n darstellen; solche Würfel beliebiger Dimension heißen Hyperwürfel. KV-Diagramme für n Variablen entsprechen umkehrbar eindeutig Hyper-Einheitswürfeln der Dimension n. Die Eckkoordinaten des Hyperwürfels entsprechen den dualen Nummern der Felder im KV-Diagramm.

Beim Einheitswürfel für 3 Variablen entspricht jedes Feld des 2×4-KV-Diagramms einem Knoten des Würfels. Nachbarschaften im KV-Diagramm entsprechen Kanten des Würfels. Beim Übergang entlang einer Kante ändert sich genau 1 Bit; das ist die zentrale Eigenschaft des Gray-Codes. Zwei benachbarte Zahlen unterscheiden sich also nur in einer Ziffer, bei Binärcode in genau 1 Bit. Bei 4 Variablen besitzt der entsprechende Hyperwürfel bereits 32 Kanten.

Für mehr als 4 Eingangsvariablen ist die ursprüngliche Form des KV-Diagramms weniger geeignet. Eine verallgemeinerte Form ist das Symmetriediagramm. Es entsteht, indem ein KV-Diagramm mit n−1 Eingangsvariablen gespiegelt und dadurch verdoppelt wird. Die neue Hälfte entspricht der neu hinzugekommenen Variablen in nicht-negierter Form, die bisherige Hälfte der negierten Form. Durch wiederholte Spiegelung kann man im Zweidimensionalen Diagramme für beliebig viele Eingangsvariablen erzeugen. Ab 5 Eingangsvariablen reicht die einfache Regel zusammenhängender Rechtecke jedoch nicht mehr aus: Entscheidend ist dann, ob eine Gruppe durch Spiegelung und Beibehalten erzeugt werden kann. Das macht die Anwendung schwieriger, weil gültige Gruppen nicht immer als zusammenhängende Blöcke auffallen.