Karnaugh-Veitch-Diagramm: Theorie des KV-Diagramms

Bild 1-1: Karnaugh-Veitch-Diagramm: ¬AB¬C¬D ∨ A¬B¬C¬D ∨ A¬B¬CD ∨ A¬BC¬D ∨ A¬BCD ∨ AB¬C¬D ∨ ABC¬D ∨ ABCD = AC ∨ B¬C¬D ∨ A¬B

Das Karnaugh-Veitch-Diagramm (bzw. das Karnaugh-Veitch-Symmetrie-Diagramm, die Karnaugh-Tafel oder der Karnaugh-Plan), kurz KV-Diagramm, KVS-Diagramm oder K-Diagramm (engl. Karnaugh map), dient der übersichtlichen Darstellung und Vereinfachung Boolescher Funktionen – Umwandlung der disjunktiven Normalform in einen minimalen logischen Ausdruck. Es wurde 1952 von Edward W. Veitch [IPA: viːtʃ] entworfen und 1953 von Maurice Karnaugh [IPA: ˈkɑːɹnɔː] zu seiner heutigen Form weiterentwickelt.

Eigenschaften

Mittels eines KV-Diagramms lässt sich jede beliebige disjunktive Normalform (DNF) in einen minimalen logischen Ausdruck umwandeln. Der Vorteil gegenüber anderen Verfahren ist, dass der erzeugte Term (meist) minimal ist. Sollte der Term noch nicht minimal sein, ist eine weitere Vereinfachung durch Anwenden des Distributivgesetzes (Ausklammern) möglich. Das Umwandeln beginnt mit dem Erstellen einer Wahrheitstafel, aus der dann die DNF abgeleitet wird, die dann wiederum direkt in ein KV-Diagramm umgewandelt wird.

Da sich benachbarte Felder jeweils in einer Variable nur um ein Bit unterscheiden, ist folgende Regel anwendbar: A ∨ ¬A = 1. Auf dieser Regel basiert die Reduzierung der Gruppen.

Die inverse Funktion ${\bar {F}}$ findet man durch Vertauschen von „1“ und „0“ im KV-Diagramm.

Ein KV-Diagramm ist ebenfalls nützlich, um Hazards festzustellen und zu eliminieren.

Das Ausfüllen des KV-Diagramms

Ein KV-Diagramm für n Eingangsvariablen hat 2ⁿ Felder (siehe Beispiel). Das KV-Diagramm wird mit den Variablen an den Rändern beschriftet. Dabei kommt jede Variable in negierter und nicht-negierter Form vor. Die Zuordnung der Variablen zu den einzelnen Feldern kann dabei beliebig erfolgen, jedoch ist zu beachten, dass sich horizontal und vertikal benachbarte Felder nur in genau einer Variablen unterscheiden dürfen. Mit Hilfe der Wahrheitstabelle der zu optimierenden Funktion wird in die einzelnen Felder eine 1 eingetragen, wenn ein Minterm der Funktion vorliegt, andernfalls eine 0. Ein Minterm m der Funktion liegt dann vor, wenn gilt

m({\underline {X}})=1\Rightarrow F({\underline {X}})=1

,

wobei ${\underline {X}}$ der Vektor der Eingangsvariablen ist. In einer disjunktiven Normalform gilt dies für jeden Konjunktionsterm, der 1 liefert, da dann auch die Gesamtdisjunktion und folglich auch die Funktion 1 liefert. KV-Diagramme eignen sich für die Vereinfachung von Funktionen mit bis zu 5 Eingangsvariablen.

Vereinfachung

Sind weniger Felder des KV-Diagramms mit 1 als mit 0 ausgefüllt, wählt man die Minterm-Methode, andernfalls die Maxterm-Methode.

Minterm-Methode

Man versucht, möglichst viele horizontal und vertikal benachbarte Felder, die eine 1 enthalten (Minterme) zu zusammenhängenden 2er-, 4er-, 8er- oder 16er-Blöcken (sogenannten Päckchen) zusammenzufassen. Als Blockgröße sind alle Potenzen von 2 erlaubt, bei denen der Exponent eine natürliche Zahl größer Null und höchstens so groß wie die Anzahl der Variablen ist. Bei Zwei bis Fünf Variablen ergeben sich damit folgende Werte:
- Zwei Variablen: 2 oder 4 Felder pro Päckchen.
- Drei Variablen: 2, 4 oder 8.
- Vier Variablen: 2, 4, 8 oder 16.
- Fünf Variablen: 2, 4, 8, 16 oder 32.

Je nach Wertetabelle kann es jedoch vorkommen, dass es in der KV-Tafel eine alleinstehende 1 gibt. Diese alleinstehende 1 muss natürlich bei dem späteren Bilden der Schaltgleichung auch mit berücksichtigt werden.

Ein Block kann unter Umständen über den rechten bzw. unteren Rand des Diagramms fortgesetzt werden. Dies erklärt sich folgendermaßen: KV-Diagramme für drei Variablen müssen im Grunde als Zylinder verstanden werden. Die Felder ganz links und ganz rechts sind also benachbart. KV-Diagramme für vier Variablen müssen im Grunde als Torus („Donut-Form“) verstanden werden. Die vier Ecken des quadratisch gezeichneten KV-Diagrammes sind im Grunde benachbart. Noch komplexere Nachbarschaftsbeziehungen gelten für 5 oder mehr Variablen. Da multidimensionale Gebilde zeichnerisch schwierig zu handhaben sind, wählt man die Darstellung in der Ebene, muss dann aber die Nachbarschaftsbeziehungen im Sinn behalten.
Die gebildeten Päckchen wandelt man nun in Konjunktionsterme um. Dabei werden Variablen innerhalb eines Blockes, die in negierter und nicht negierter Form auftreten, weggelassen.
Diese UND-Verknüpfungen werden durch ODER-Verknüpfungen zusammengefasst und ergeben eine disjunktive Normalform.

Maxterm-Methode

Die Maxterm-Methode unterscheidet sich von der Minterm-Methode lediglich in folgenden Punkten:

Statt Einsen werden Nullen zu Päckchen zusammengefasst.
Ein Päckchen bildet einen Disjunktionsterm (ODER-Verknüpfungen, statt eines Konjunktionsterms).
Die Disjunktionsterme werden konjunktiv (mit UND) verknüpft.
Die Variablen werden zusätzlich einzeln negiert.

Ringsummen-Methode

Es gibt auch eine Möglichkeit eine sogenannte Ringsummen-Normalform aus einem KV-Diagramm abzulesen. Dazu wählt man die Blöcke aus Nullen und Einsen so, dass die Nullen von einer geraden und die Einsen durch eine ungerade Anzahl von Blöcken überdeckt werden. Die Terme werden dann mit XOR verknüpft und ergeben eine minimierte Funktion.

Don’t-Care-Zustände

Häufig gibt es Boolesche Funktionen mit Wahrheitstabellen, in denen nicht für jede Kombination der Eingangsvariablen ein Wert der Ausgangsvariablen definiert sein muss. Man nennt solche Ausgangszustände Don’t-Care-Terme und bezeichnet sie mit X, da sie sowohl den Wert 1 als auch 0 annehmen können. Diese X-Felder dürfen als 1 oder 0 angesehen werden, um in der Minterm- oder Maxterm-Methode Blöcke von Einsen oder Nullen zu vervollständigen. Ein gutes Beispiel dafür ist die Dekodierung von binär codierten Dezimalzahl (BCD). Hier spielen nur die Zahlen 0 bis 9 eine Rolle, die sogenannten Pseudotetraden dürfen ein beliebiges Ergebnis liefern, sind also Don’t-Care-Terme.

KV-Diagramm bei mehreren Ausgängen

Wenn eine Digitalschaltung mehrere Ausgänge hat, die Wahrheitstabelle also mehrere Ergebnisspalten hat, dann muss für jeden Ausgang ein eigenes KV-Diagramm erstellt werden.

Beispielsweise hat ein 1-aus-n-Decoder die nebenstehende Wahrheitstabelle und für seine 4 Ausgänge die 4 nebenstehenden 4 KV-Diagramme.

Eingabe				Ausgabe
Zahl 1		Zahl 2		$A<B$	$A=B$	$A>B$
$A_{1}$	$A_{0}$	$B_{1}$	$B_{0}$	$X$	$Y$	$Z$
0	0	0	0	0	1	0
0	0	0	1	1	0	0
0	0	1	0	1	0	0
0	0	1	1	1	0	0
0	1	0	0	0	0	1
0	1	0	1	0	1	0
0	1	1	0	1	0	0
0	1	1	1	1	0	0
1	0	0	0	0	0	1
1	0	0	1	0	0	1
1	0	1	0	0	1	0
1	0	1	1	1	0	0
1	1	0	0	0	0	1
1	1	0	1	0	0	1
1	1	1	0	0	0	1
1	1	1	1	0	1	0

Ein weiteres Beispiel für mehrere Ausgänge ist ein ein 2+2-Bit-Vergleicher. Er hat 4 Eingangsvariablen und 3 Ausgangvariablen. Die Zahl A besteht aus 2 Bit ( $A_{1}$ und $A_{0}$ ) und die Zahl B besteht aus 2 Bit ( $B_{1}$ und $B_{0}$ ). Je nachdem, ob „A < B“, „A = B“ oder „A > B“ geben die drei Ausgänge (X, Y, Z) eine 1 oder 0 aus.

Die dazugehörige Wahrheitstabelle ist rechts. Die Bilder 5-2 bis 5-4 zeigen die 3 KV-Diagramme für die 3 Ausgänge.

Normalformen

A	B	C	D	X
0	0	0	0	0
0	0	0	1	0
0	0	1	0	0
0	0	1	1	0
0	1	0	0	1
0	1	0	1	1
0	1	1	0	0
0	1	1	1	1
1	0	0	0	0
1	0	0	1	0
1	0	1	0	0
1	0	1	1	0
1	1	0	0	1
1	1	0	1	1
1	1	1	0	0
1	1	1	1	1

Üblicherweise werden Gruppen für die Einsen gebildet (Bild 6-2). Die Einsen leiten sich aus der Disjunktiven Normalform (DNF) ab. Es gibt aber auch die Möglichkeit Gruppen aus den Nullen zu bilden (in Bild 3 sind die Nullen nicht extra eingezeichnet, aber trotzdem vorhanden). Die Nullen stehen für die Konjunktive Normalform (KNF).

Die DNF lautet: ¬AB¬C¬D ∨ ¬AB¬CD ∨ ¬ABCD ∨ AB¬C¬D ∨ AB¬CD ∨ ABCD.

Die KNF lautet: (A∨B∨C∨D) ∧ (A∨B∨C∨¬D) ∧ (A∨B∨¬C∨D) ∧ (A∨B∨¬C∨¬D) ∧ (A∨¬B∨¬C∨D) ∧ (¬A∨B∨C∨D) ∧ (¬A∨B∨C∨¬D) ∧ (¬A∨B¬∨C∨D) ∧ (¬A∨B∨¬C∨¬D) ∧ (¬A∨¬B∨¬C∨D).

Die DNF wird aus der Tabelle ausgelesen, indem jede Zeile mit dem Ausgabewert „Eins“ aufgeschrieben wird. Die Eingangsvariablen für die eine Null steht, werden in negierter Form genommen. Alle Terme für die Zeilen (im vorliegenden Beispiel 6 Zeilen) werden durch „∨“ verbunden.

Für die KNF werden alle Zeilen mit dem Ausgabewert „Null“ rausgeschrieben, wobei Eingangsvariablen für die eine „Eins“ steht, in negierter Form genommen werden. Alle Terme für die Zeilen (im vorliegenden Beispiel 10 Zeilen) werden durch „∧“ verbunden, die Literale selber werden durch „∨“ verbunden.

Kompakte Schreibweise

Eine kompakte Schreibweise für ein KV-Diagramm (Bild 7-1) zeigt folgendes Beispiel:
F = ∑ (0, 3, 6, 7, 10, 11, 12, 14, 15)

Ausgehend von einer durchgehenden Nummerierung (genauer gesagt: Indexierung – beginnend bei Feld 0) der Felder, wie in Bild 7-2 dargestellt, werden die Nummern der Felder aufgezählt, in denen eine Eins eingetragen ist.

Gesetzmäßigkeiten bei der Reduzierung

Durch die Zusammenfassung zu einer Gruppe der Größe 2ⁿ reduziert sich der logische Ausdruck um n Variablen. Das ist unabhängig davon, welche Lage oder Form die Gruppe hat oder ob sie über die Ränder hinwegreicht. Das ist auch unabhängig davon, ob es sich um ein 2x2, 2x4, 4x4 oder 4x4x4 KV-Diagramm handelt.

Eine Achtergruppe (2³) reduziert sich um 3 Variablen (n = 3) – Bild 9-1.
Eine Vierergruppe (2²) reduziert sich um 2 Variablen (n = 2) – Bild 9-2 und 9-3.
Eine Zweiergruppe (2¹) reduziert sich um 1 Variable (n = 1) – Bild 9-4 und 9-5.
Eine Einergruppe (2⁰) reduziert sich um Null Variablen (n = 0) – Bild 9-6.

Regeln für die Gruppenbildung

Benachbarte Felder in die eine Eins eingetragen ist, werden zu Gruppen zusammengefasst.
Eine Gruppe darf keine Felder mit Nullen enthalten. (Oft werden die Nullen nicht mitgeschrieben und die Felder leer gelassen. In diesem Fall darf eine Gruppe keine leeren Felder enthalten.)
Alle Einsen müssen in Gruppen zusammengefasst werden.
Benachbarte Felder mit Einsen werden zu einer Gruppe zusammengefasst. (Felder, die sich an den Ecken berühren, diagonal, zählen nicht als benachbart.)
Die Gruppen müssen so groß wie möglich sein.
Es müssen so wenig Gruppen wie möglich gebildet werden.
Die Gruppen dürfen nur Größen haben, die Zweierpotenzen entsprechen (1, 2, 4, 8, 16, 32, 64 …).
Die Gruppen müssen rechteckige Blöcke sein.
Die Gruppen dürfen sich überlappen.
Die Gruppen dürfen über die Ränder hinweggehen.
Es darf keine Gruppe vollständig von einer anderen Gruppe umschlossen werden.

Zusammenfassung: Man sucht eine vollständige Überdeckung der Einsen mit möglichst großen rechteckigen Blöcken.

KV-Tafeln für 2 und 4 Variablen

Wer häufig mit dem KV-Diagramm arbeitet, wünscht sich eine Methode, ein KV-Diagramm schnell ausfüllen zu können.

Dies wird bei oben dargestellter Anordnung bei den vier Eingangsvariablen A, B, C und D durch folgende Anordnung erreicht:

Bild 3: Verdeutlicht die logischen Werte der 16 Felder; wenn man aus einer Wahrheitstabelle zeilenweise die DNF in das KV-Diagramm überträgt, dann erfolgt die Eintragung in der Reihenfolge der roten Zahlen
Bild 4: Die roten Zahlen erleichtern die zeilenweise Zuordnung der Wahrheitstabelle zu den einzelnen Feldern; die Reihenfolge hängt von der konkreten Beschriftung des KV-Diagramms ab; die Nummerierung stellt eine Arbeitserleichterung bei umfangreicher Verwendung von KV-Diagrammen dar

Dabei wird jedem Feld ihre Wertigkeit zugeordnet. Bei 4 Signalen sind dies 16 Einträge:

0000 = 0, 0001 = 1, 0010 = 2, …, 1110 = 14, 1111 = 15

Auf diese Weise kann das KV-Diagramm sehr schnell ausgefüllt werden. Es sind neben oben dargestellter Anordnungen aber auch Variationen der Anordnung der Eingangsvariablen A, B, C und D möglich. Dadurch ergeben sich andere Aufteilung der Wertigkeiten in der Matrix.

Zur Titelseite: Karnaugh-Veitch-Diagramm - zum nächsten Kapitel: Beispiele (Teil 1)