Karnaugh-Veitch-Diagramm

Das Karnaugh-Veitch-Diagramm (bzw. die Karnaugh-Tafel oder der Karnaugh-Plan), kurz KV-Diagramm (engl. Karnaugh map), dient der übersichtlichen Darstellung und Vereinfachung Boolescher Funktionen. Es wurde 1952 von Edward W. Veitch entworfen und 1953 von Maurice Karnaugh zu seiner heutigen Form weiterentwickelt.

Eigenschaften

Mittels eines KV-Diagramms lässt sich jede beliebige boolesche Funktion in eine disjunktive oder konjunktive Normalform (DNF/KNF) umwandeln. Der Vorteil gegenüber anderen Verfahren ist, dass der erzeugte Term (meist) minimal ist. Weitere Vereinfachung ist durch Anwenden des Distributivgesetzes (Ausklammern) möglich. Das entstehende Resultat ist in diesem Fall allerdings keine DNF bzw. KNF mehr. Das Umwandeln beginnt mit dem Erstellen einer Wahrheitstafel, die dann direkt in ein KV-Diagramm umgewandelt wird. Durch geschickte Wahl bestimmter Blöcke innerhalb des Diagramms entstehen die Terme der Normalform. Der Vorteil dieser Normalformen liegt darin, dass sie in Schaltungen ausschließlich durch die Bauteile AND, OR und NOT realisiert werden können.

Wie füllt man ein KV-Diagramm aus?

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. Welche Blockgrößen erlaubt sind, hängt von der Anzahl der Variablen ab. Hier die Blockgrößen für zwei bis fünf Variablen:
- Zwei Variablen: 2 oder 4.
- 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 Kreisring ("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 die 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...

Veranschaulichung durch Hyper-Einheitswürfel

Boolesche Funktionen mit n Variablen lassen sich grafisch mittels Einheitswürfeln der Dimension n veranschaulichen. Würfel beliebiger Dimension bezeichnet man auch als Hyperwürfel. Da Karnaugh-Diagramme selbst eine spezielle Darstellungsform für Boolesche Funktionen sind, überrascht es nicht, dass sich zwischen Hyper-Einheitswürfeln und Karnaugh-Diagrammen ein anschaulicher Zusammenhang herstellen lässt. Und zwar entsprechen Karnaugh-Diagramme für n Variablen umkehrbar eindeutig den Hyper-Einheitswürfeln der Dimension n. Die Ecken-Koordinaten des Hyperwürfels entsprechen dabei den dualen Nummern der Felder im Karnaugh-Diagramm.

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 KV-Diagramm ist ebenfalls nützlich, um Hazards festzustellen und zu eliminieren.

Beispiel

Zu einer Lampe führen drei Schalter A, B und C, die entweder an (1) oder aus (0) sind. Folgende Tabelle zeigt, bei welcher Kombination von Schaltern die Lampe leuchtet (1) oder dunkel bleibt (0):

C	B	A	Lampe
0	0	0	1
0	0	1	0
0	1	0	1
0	1	1	1
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	1

Die disjunktive Normalform lautet also: $l={\bar {A}}{\bar {B}}{\bar {C}}\vee {\bar {A}}B{\bar {C}}\vee AB{\bar {C}}\vee {\bar {A}}{\bar {B}}C\vee {\bar {A}}BC\vee ABC$ , da die Minterme nur des Urbilds 1 gebildet werden (analog werden Maxterme nur des Urbilds 0 gebildet).
Die enthaltenen Konjunktionsterme sind gerade die Minterme.

Das dazugehörige KV-Diagramm sieht nun so aus:

Nach der Minterm-Methode kann man im Diagramm nun zwei Viererblocks bilden, die im einen Fall ${\bar {A}}$ und im anderen Fall $B\,$ enthalten. Die optimierte Funktion lautet demnach: $l={\bar {A}}\vee B$

Das bedeutet, dass die Lampe l leuchtet, wenn der Schalter A ausgeschaltet oder der Schalter B eingeschaltet ist. Der Schalter C hat keine Wirkung.

Nach der Maxterm-Methode fasst man die beiden 0-Felder zu einem Zweierblock zusammen und erhält damit ohne weiteres $l={\bar {A}}\vee B$

Für ggf. vorhandene Pseudotetraden kann man übrigens ein z.B. ein "P" ins KV-Diagramm eintragen, um diese dann nach belieben einzusetzen.

KV-Tafeln für 2 und 4 Variablen

Datei:KV-Diagramm AB.png Datei:KV-Diagramm ABCD.png

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

Dies wird durch eine spezielle Anordnung erreicht:

 7  3  2  6
15 11 10 14
13  9  8 12
 5  1  0  4

Bei dieser Zuordnung wird jeder Zustandsmöglichkeit (bei 4 Signalen sind dies 16) eine Zahl zugeordnet. 0000 = 0, 0001 = 1, 0010 = 2, ..., 1110 = 14, 1111 = 15

Auf diese Weise kann das KV-Diagramm sehr schnell ausgefüllt werden.

Siehe auch

Verfahren nach Quine und McCluskey
Pseudotetraden
Schaltalgebra

Literatur

Maurice Karnaugh: The Map Method for Synthesis of Combinational Logic Circuits, Transactions of the AIEE, Vol. 72, No. 9 (1953), 593—599.
Edward W. Veitch: A chart method for symplifying truth functions, Mai 1952, Proc. Assoc. for Computing Machinery, Pittsburgh.
Klaus Beuth: Digitaltechnik (Kapitel 5), 2001, Vogel Buchverlag, ISBN 3-8023-1755-6

Weblinks