Zum Inhalt springen

Karnaugh-Veitch-Diagramm: Mengendiagramm und Hyper-Einheitswürfel

Aus Wikibooks

Mengendiagramm

[Bearbeiten]

Das Karnaugh-Veitch-Diagramm ist eine abgewandelte, abstrakte Form des Mengendiagramms (Venn-Diagramm).

Die Bilder 1 bis 4 zeigen ein Venn-Diagramm und das äquivalente KV-Diagramm.

Die Bilder 5 bis 8 zeigen noch einmal die einzelnen Teilmengen, aus denen sich das Venn-Diagramm in Bild 4 zusammensetzt.

Veranschaulichung durch Hyper-Einheitswürfel

[Bearbeiten]
Bild 3-1: Hyperwü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.

Bild 3-2 zeigt den Einheitswürfel für 3 Variablen. Das entspricht einem 2x4 KV-Diagramm. Das KV-Diagramm in Bild 3-3 ist in Bild 3-4 entsprechend markiert (grüne Ebene). Die Knoten (Eckpunkt oder Kreise) am Hyper-Einheitswürfel entsprechen jeweils einem Feld im KV-Diagramm. Die Übergänge (Nachbarschaft der Felder) sind durch die Kanten des Würfels symbolisiert. Beim Wandern auf der Kante entsteht ein Gray-Code. Auf jeder Kante ändert sich genau 1 Bit. Eine wesentliche Eigenschaft ist, dass sich die Gray-Codes für zwei benachbarte Zahlen nur um 1 Ziffer, bei Binärcode also 1 Bit, unterscheiden (Hamming-Distanz).

Das KV-Diagramm hat so viel Nachbarschaften, wie der Würfel Kanten hat. Bild 3-5 zeigt eine ebene Darstellung des Hyper-Einheitswürfels. Ohne seine innere Struktur der Übergänge zu ändern lässt sich der Würfel in beliebige Richtungen „umstülpen“, wie in der Animation in Bild 3-9 dargestellt ist. So ist zu erklären, warum es KV-Diagramm mit verschiedenen Anordnungen der Variablen gibt (Randbeschriftung). Sie wurden praktisch wie ein Würfel „umgestülpt“.

Bild 3-2
Bild 3-3
Bild 3-4
Bild 3-5

Für das KV-Diagramm mit 2 Variablen (2x2 Feld) ergibt sich ein einfacherer Hyper-Einheitswürfel (Bild 3-6). Bei 1 Variable ist der „Würfel“ trivial (Bild 3-7). Mit zunehmenden Variablen steigt die Anzahl der Kanten allerdings exponentiell an. So gibt es bei 4 Variablen (Bild 3-8) bereits 32 Kanten.

Bild 3-6
Bild 3-7
Bild 3-8
Bild 3-9

Siehe auch

[Bearbeiten]

Literatur

[Bearbeiten]
  • 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 simplifying truth functions, Mai 1952, Proc. Assoc. for Computing Machinery, Pittsburgh, 127–133.
  • Klaus Beuth: Digitaltechnik (Kapitel 5), 2001, Vogel Buchverlag, ISBN 3-8023-1755-6
  • Günter Wellenreuther, Dieter Zastrow: Steuerungstechnik mit SPS: Von der Steuerungsaufgabe zum Steuerprogramm (Kapitel 4.5.2), 1998, Vieweg+Teubner Verlag, ISBN 3-5284-4580-7
[Bearbeiten]

Zur Titelseite: Karnaugh-Veitch-Diagramm - zum vorherigen Kapitel: Beispiele (Teil 3) - Ende des Buches