Digitale Schaltungstechnik/ Schaltalgebra/ KV-Diagramm

Zurück zu Gesetze der Schaltalgebra | Hoch zu Speicherfreie Logik | Vor zu Übungen

Einleitung

Das Karnaugh-Veitch-Diagramm (KV-Diagramm) ist ein Werkzeug zur Vereinfachung von Schaltungen. Es eignet sich für größere und komplizierte Wahrheitstabellen mit drei oder vier Variablen.

Zahl $Q_{3}$ $Q_{2}$ $Q_{1}$ $Q_{0}$ Ausgang 0 0 0 0 0 1 0 0 0 1 2 0 0 1 0 3 0 0 1 1 4 0 1 0 0 5 0 1 0 1 6 0 1 1 0 7 0 1 1 1 8 1 0 0 0 9 1 0 0 1 10 1 0 1 0 11 1 0 1 1 12 1 1 0 0 13 1 1 0 1 14 1 1 1 0 15 1 1 1 1

Jedem Wahrheitstabellenwert wird ein Kästchen im KV-Diagramm zugewiesen. Ausgang $Q_{3}Q_{2}$ $Q_{3}{\overline {Q_{2}}}$ ${\overline {Q_{3}}}{\overline {Q_{2}}}$ ${\overline {Q_{3}}}Q_{2}$ $Q_{1}Q_{0}$ 15 \ 11 \ 3 \ 7 \ $Q_{1}{\overline {Q_{0}}}$ 14 \ 10 \ 2 \ 6 \ ${\overline {Q_{1}}}{\overline {Q_{0}}}$ 12 \  8 \ 0 \ 4 \ ${\overline {Q_{1}}}Q_{0}$ 13 \  9 \ 1 \ 5 \

Es gibt recht unterschiedliche Darstellungsformen. Wichtig ist nur das sich von Spalte zu Spalte und von Zeile zu Zeile, jeweils nur 1 Zustand ändern darf.

Ein KV-Diagramm dient dazu einen Ausgang darzustellen und ihn zu vereinfachen.

Erklärung an einem Beispiel

Zahl $Q_{3}$ $Q_{2}$ $Q_{1}$ $Q_{0}$ Ausgang 1 Ausgang 2 0 0 0 0 0 0 1 1 0 0 0 1 0 1 2 0 0 1 0 0 1 3 0 0 1 1 1 0 4 0 1 0 0 0 1 5 0 1 0 1 1 0 6 0 1 1 0 0 1 7 0 1 1 1 1 0 8 1 0 0 0 0 1 9 1 0 0 1 1 0 10 1 0 1 0 1 0 11 1 0 1 1 1 0 12 1 1 0 0 0 1 13 1 1 0 1 1 0 14 1 1 1 0 0 1 15 1 1 1 1 1 0

Ausgang 1 $Q_{3}Q_{2}$ $Q_{3}{\overline {Q_{2}}}$ ${\overline {Q_{3}}}{\overline {Q_{2}}}$ ${\overline {Q_{3}}}Q_{2}$ $Q_{1}Q_{0}$ 15 1 11 1 3 1 7 1 $Q_{1}{\overline {Q_{0}}}$ 14 0 10 1 2 0 6 0 ${\overline {Q_{1}}}\ {\overline {Q_{0}}}$ 12 0  8 0 0 0 4 0 ${\overline {Q_{1}}}Q_{0}$ 13 1  9 1 1 0 5 1 Bei einem KV-Diagramm sind die Einsen interessant. Ausgang 1 $Q_{3}Q_{2}$ $Q_{3}\ {\overline {Q_{2}}}$ ${\overline {Q_{3}}}{\overline {Q_{2}}}$ ${\overline {Q_{3}}}\ Q_{2}$ $Q_{1}\ Q_{0}$ 15 1 11 1 3 1 7 1 $Q_{1}{\overline {Q_{0}}}$ 14 0 10 1 2 0 6 0 ${\overline {Q_{1}}}{\overline {Q_{0}}}$ 12 0  8 0 0 0 4 0 ${\overline {Q_{1}}}\ Q_{0}$ 13 1  9 1 1 0 5 1 Man versucht nun möglichst große Blöcke zu bilden. Es gibt nur Blockgrößen, die einer Potenz von 2 entsprechen (1, 2, 4, 8 usw.). Man muss sich das KV-Diagramm in dieser Hinsicht wie eine Kugel vorstellen. Blöcke können horizontal und vertikal liegen. Und da eine Kugel kein Ende hat, kann ein Block auch von der ersten Spalte mit der letzten Spalte gebildet werden. Dasselbe gilt auch für Zeilen. Besonders interessant sind die Ecken des Diagramms. Steht in allen eine Eins, so kann man diese zu einem Vierer-Block zusammenfassen.

Mögliche Blöcke

Aus dieser Wahrheitstabelle lassen sich folgende Blöcke bilden.

Block 1 Ausgang 1 $Q_{3}Q_{2}$ $Q_{3}\ {\overline {Q_{2}}}$ ${\overline {Q_{3}}}{\overline {Q_{2}}}$ ${\overline {Q_{3}}}\ Q_{2}$ $Q_{1}\ Q_{0}$ 15 1 11 1 3 1 7 1 $Q_{1}{\overline {Q_{0}}}$ 14 0 10 1 2 0 6 0 ${\overline {Q_{1}}}{\overline {Q_{0}}}$ 12 0  8 0 0 0 4 0 ${\overline {Q_{1}}}\ Q_{0}$ 13 1  9 1 1 0 5 1	Block 2 Ausgang 1 $Q_{3}Q_{2}$ $Q_{3}\ {\overline {Q_{2}}}$ ${\overline {Q_{3}}}{\overline {Q_{2}}}$ ${\overline {Q_{3}}}\ Q_{2}$ $Q_{1}\ Q_{0}$ 15 1 11 1 3 1 7 1 $Q_{1}{\overline {Q_{0}}}$ 14 0 10 1 2 0 6 0 ${\overline {Q_{1}}}{\overline {Q_{0}}}$ 12 0  8 0 0 0 4 0 ${\overline {Q_{1}}}\ Q_{0}$ 13 1  9 1 1 0 5 1
Block 3 Ausgang 1 $Q_{3}Q_{2}$ $Q_{3}\ {\overline {Q_{2}}}$ ${\overline {Q_{3}}}{\overline {Q_{2}}}$ ${\overline {Q_{3}}}\ Q_{2}$ $Q_{1}\ Q_{0}$ 15 1 11 1 3 1 7 1 $Q_{1}{\overline {Q_{0}}}$ 14 0 10 1 2 0 6 0 ${\overline {Q_{1}}}{\overline {Q_{0}}}$ 12 0  8 0 0 0 4 0 ${\overline {Q_{1}}}\ Q_{0}$ 13 1  9 1 1 0 5 1	Block 4 Ausgang 1 $Q_{3}Q_{2}$ $Q_{3}\ {\overline {Q_{2}}}$ ${\overline {Q_{3}}}{\overline {Q_{2}}}$ ${\overline {Q_{3}}}\ Q_{2}$ $Q_{1}\ Q_{0}$ 15 1 11 1 3 1 7 1 $Q_{1}{\overline {Q_{0}}}$ 14 0 10 1 2 0 6 0 ${\overline {Q_{1}}}{\overline {Q_{0}}}$ 12 0  8 0 0 0 4 0 ${\overline {Q_{1}}}\ Q_{0}$ 13 1  9 1 1 0 5 1
Block 5 Ausgang 1 $Q_{3}Q_{2}$ $Q_{3}\ {\overline {Q_{2}}}$ ${\overline {Q_{3}}}{\overline {Q_{2}}}$ ${\overline {Q_{3}}}\ Q_{2}$ $Q_{1}\ Q_{0}$ 15 1 11 1 3 1 7 1 $Q_{1}{\overline {Q_{0}}}$ 14 0 10 1 2 0 6 0 ${\overline {Q_{1}}}{\overline {Q_{0}}}$ 12 0  8 0 0 0 4 0 ${\overline {Q_{1}}}\ Q_{0}$ 13 1  9 1 1 0 5 1	Block 6 Ausgang 1 $Q_{3}Q_{2}$ $Q_{3}\ {\overline {Q_{2}}}$ ${\overline {Q_{3}}}{\overline {Q_{2}}}$ ${\overline {Q_{3}}}\ Q_{2}$ $Q_{1}\ Q_{0}$ 15 1 11 1 3 1 7 1 $Q_{1}{\overline {Q_{0}}}$ 14 0 10 1 2 0 6 0 ${\overline {Q_{1}}}{\overline {Q_{0}}}$ 12 0  8 0 0 0 4 0 ${\overline {Q_{1}}}\ Q_{0}$ 13 1  9 1 1 0 5 1
Block 7 Ausgang 1 $Q_{3}Q_{2}$ $Q_{3}\ {\overline {Q_{2}}}$ ${\overline {Q_{3}}}{\overline {Q_{2}}}$ ${\overline {Q_{3}}}\ Q_{2}$ $Q_{1}\ Q_{0}$ 15 1 11 1 3 1 7 1 $Q_{1}{\overline {Q_{0}}}$ 14 0 10 1 2 0 6 0 ${\overline {Q_{1}}}{\overline {Q_{0}}}$ 12 0  8 0 0 0 4 0 ${\overline {Q_{1}}}\ Q_{0}$ 13 1  9 1 1 0 5 1	Block 8 Ausgang 1 $Q_{3}Q_{2}$ $Q_{3}\ {\overline {Q_{2}}}$ ${\overline {Q_{3}}}{\overline {Q_{2}}}$ ${\overline {Q_{3}}}\ Q_{2}$ $Q_{1}\ Q_{0}$ 15 1 11 1 3 1 7 1 $Q_{1}{\overline {Q_{0}}}$ 14 0 10 1 2 0 6 0 ${\overline {Q_{1}}}{\overline {Q_{0}}}$ 12 0  8 0 0 0 4 0 ${\overline {Q_{1}}}\ Q_{0}$ 13 1  9 1 1 0 5 1
Block 9 Ausgang 1 $Q_{3}Q_{2}$ $Q_{3}\ {\overline {Q_{2}}}$ ${\overline {Q_{3}}}{\overline {Q_{2}}}$ ${\overline {Q_{3}}}\ Q_{2}$ $Q_{1}\ Q_{0}$ 15 1 11 1 3 1 7 1 $Q_{1}{\overline {Q_{0}}}$ 14 0 10 1 2 0 6 0 ${\overline {Q_{1}}}{\overline {Q_{0}}}$ 12 0  8 0 0 0 4 0 ${\overline {Q_{1}}}\ Q_{0}$ 13 1  9 1 1 0 5 1	Block 10 Ausgang 1 $Q_{3}Q_{2}$ $Q_{3}\ {\overline {Q_{2}}}$ ${\overline {Q_{3}}}{\overline {Q_{2}}}$ ${\overline {Q_{3}}}\ Q_{2}$ $Q_{1}\ Q_{0}$ 15 1 11 1 3 1 7 1 $Q_{1}{\overline {Q_{0}}}$ 14 0 10 1 2 0 6 0 ${\overline {Q_{1}}}{\overline {Q_{0}}}$ 12 0  8 0 0 0 4 0 ${\overline {Q_{1}}}\ Q_{0}$ 13 1  9 1 1 0 5 1
Block 11 Ausgang 1 $Q_{3}Q_{2}$ $Q_{3}\ {\overline {Q_{2}}}$ ${\overline {Q_{3}}}{\overline {Q_{2}}}$ ${\overline {Q_{3}}}\ Q_{2}$ $Q_{1}\ Q_{0}$ 15 1 11 1 3 1 7 1 $Q_{1}{\overline {Q_{0}}}$ 14 0 10 1 2 0 6 0 ${\overline {Q_{1}}}{\overline {Q_{0}}}$ 12 0  8 0 0 0 4 0 ${\overline {Q_{1}}}\ Q_{0}$ 13 1  9 1 1 0 5 1	Block 12 Ausgang 1 $Q_{3}Q_{2}$ $Q_{3}\ {\overline {Q_{2}}}$ ${\overline {Q_{3}}}{\overline {Q_{2}}}$ ${\overline {Q_{3}}}\ Q_{2}$ $Q_{1}\ Q_{0}$ 15 1 11 1 3 1 7 1 $Q_{1}{\overline {Q_{0}}}$ 14 0 10 1 2 0 6 0 ${\overline {Q_{1}}}{\overline {Q_{0}}}$ 12 0  8 0 0 0 4 0 ${\overline {Q_{1}}}\ Q_{0}$ 13 1  9 1 1 0 5 1

Demzufolge lassen sich die Blöcke 1, 2, 3, 4 zu Block 11 zusammen fassen und entfallen damit bei der Vereinfachung. Man fasst so viele Blöcke wie möglich zusammen.

\

Optimale Blöcke

In den Blöcken müssen alle Einsen untergebracht werden, so dass sowenig wie möglich Blöcke entstehen. Dabei dürfen Einsen mehrfach verwendet werden. Also kurz nach der Regel:

Soviel wie nötig. Sowenig wie möglich.

Am Ende sollten dann nur noch die Blöcke 6, 10, 11 und 12 übrig sein (Herleitung siehe eingeklappter Text)

Block 6 Ausgang 1 $Q_{3}\ Q_{2}$ $Q_{3}\ {\overline {Q_{2}}}$ ${\overline {Q_{3}}}\ {\overline {Q_{2}}}$ ${\overline {Q_{3}}}\ Q_{2}$ $Q_{1}\ Q_{0}$ 15 1 11 1 3 1 7 1 $Q_{1}\ {\overline {Q_{0}}}$ 14 0 10 1 2 0 6 0 ${\overline {Q_{1}}}\ {\overline {Q_{0}}}$ 12 0  8 0 0 0 4 0 ${\overline {Q_{1}}}\ Q_{0}$ 13 1  9 1 1 0 5 1	Block 10 Ausgang 1 $Q_{3}\ Q_{2}$ $Q_{3}\ {\overline {Q_{2}}}$ ${\overline {Q_{3}}}\ {\overline {Q_{2}}}$ ${\overline {Q_{3}}}\ Q_{2}$ $Q_{1}\ Q_{0}$ 15 1 11 1 3 1 7 1 $Q_{1}\ {\overline {Q_{0}}}$ 14 0 10 1 2 0 6 0 ${\overline {Q_{1}}}\ {\overline {Q_{0}}}$ 12 0  8 0 0 0 4 0 ${\overline {Q_{1}}}\ Q_{0}$ 13 1  9 1 1 0 5 1
Block 11 Ausgang 1 $Q_{3}\ Q_{2}$ $Q_{3}\ {\overline {Q_{2}}}$ ${\overline {Q_{3}}}\ {\overline {Q_{2}}}$ ${\overline {Q_{3}}}\ Q_{2}$ $Q_{1}\ Q_{0}$ 15 1 11 1 3 1 7 1 $Q_{1}\ {\overline {Q_{0}}}$ 14 0 10 1 2 0 6 0 ${\overline {Q_{1}}}\ {\overline {Q_{0}}}$ 12 0  8 0 0 0 4 0 ${\overline {Q_{1}}}\ Q_{0}$ 13 1  9 1 1 0 5 1	Block 12 Ausgang 1 $Q_{3}\ Q_{2}$ $Q_{3}\ {\overline {Q_{2}}}$ ${\overline {Q_{3}}}\ {\overline {Q_{2}}}$ ${\overline {Q_{3}}}\ Q_{2}$ $Q_{1}\ Q_{0}$ 15 1 11 1 3 1 7 1 $Q_{1}\ {\overline {Q_{0}}}$ 14 0 10 1 2 0 6 0 ${\overline {Q_{1}}}\ {\overline {Q_{0}}}$ 12 0  8 0 0 0 4 0 ${\overline {Q_{1}}}\ Q_{0}$ 13 1  9 1 1 0 5 1

Nun kann man mit der Vereinfachung der Gleichung beginnen. Man schaut an die Seiten und vergleicht, welche Zustände gleich bleiben und welche sich ändern. Die sich ändernden Zustände sind irrelevant für das Ergebnis. Man schreibt die gleichbleibenden Zustände heraus.

Block 6 Ausgang 1 $Q_{3}\ Q_{2}$ $Q_{3}\ {\overline {Q_{2}}}$ ${\overline {Q_{3}}}\ {\overline {Q_{2}}}$ ${\overline {Q_{3}}}\ Q_{2}$ $Q_{1}\ Q_{0}$ 15 1 11 1 3 1 7 1 $Q_{1}\ {\overline {Q_{0}}}$ 14 0 10 1 2 0 6 0 ${\overline {Q_{1}}}\ {\overline {Q_{0}}}$ 12 0  8 0 0 0 4 0 ${\overline {Q_{1}}}\ Q_{0}$ 13 1  9 1 1 0 5 1	Man kann hier ablesen, dass $Q_{3}\ {\overline {Q_{2}}}$ und $Q_{1}$ gleich bleiben. Deshalb schreibt man aus diesem Diagramm $Q_{3}\ {\overline {Q_{2}}}\ Q_{1}$ heraus.
Block 10 Ausgang 1 $Q_{3}\ Q_{2}$ $Q_{3}\ {\overline {Q_{2}}}$ ${\overline {Q_{3}}}\ {\overline {Q_{2}}}$ ${\overline {Q_{3}}}\ Q_{2}$ $Q_{1}\ Q_{0}$ 15 1 11 1 3 1 7 1 $Q_{1}\ {\overline {Q_{0}}}$ 14 0 10 1 2 0 6 0 ${\overline {Q_{1}}}\ {\overline {Q_{0}}}$ 12 0  8 0 0 0 4 0 ${\overline {Q_{1}}}\ Q_{0}$ 13 1  9 1 1 0 5 1	Man kann hier ablesen, dass $Q_{3}$ und $Q_{0}$ gleich bleiben. Deshalb schreibt man aus diesem Diagramm $Q_{3}\ Q_{0}$ heraus.
Block 11 Ausgang 1 $Q_{3}\ Q_{2}$ $Q_{3}\ {\overline {Q_{2}}}$ ${\overline {Q_{3}}}\ {\overline {Q_{2}}}$ ${\overline {Q_{3}}}\ Q_{2}$ $Q_{1}\ Q_{0}$ 15 1 11 1 3 1 7 1 $Q_{1}\ {\overline {Q_{0}}}$ 14 0 10 1 2 0 6 0 ${\overline {Q_{1}}}\ {\overline {Q_{0}}}$ 12 0  8 0 0 0 4 0 ${\overline {Q_{1}}}\ Q_{0}$ 13 1  9 1 1 0 5 1	Man kann hier ablesen, dass $Q_{1}Q_{0}$ gleich bleiben. Deshalb schreibt man aus diesem Diagramm $Q_{1}Q_{0}$ heraus.
Block 12 Ausgang 1 $Q_{3}\ Q_{2}$ $Q_{3}\ {\overline {Q_{2}}}$ ${\overline {Q_{3}}}\ {\overline {Q_{2}}}$ ${\overline {Q_{3}}}\ Q_{2}$ $Q_{1}\ Q_{0}$ 15 1 11 1 3 1 7 1 $Q_{1}\ {\overline {Q_{0}}}$ 14 0 10 1 2 0 6 0 ${\overline {Q_{1}}}\ {\overline {Q_{0}}}$ 12 0  8 0 0 0 4 0 ${\overline {Q_{1}}}\ Q_{0}$ 13 1  9 1 1 0 5 1	Man kann hier ablesen, dass $Q_{2}$ und $Q_{0}$ gleich bleiben. Deshalb schreibt man aus diesem Diagramm $Q_{2}Q_{0}$ heraus.

Am Ende schreibt man alles in einer Gleichung auf und verbindet die Ergebnisse der KV-Diagramme mit einen ODER.

$Ausgang=Q_{3}\ {\overline {Q_{2}}}\ Q_{1}\quad \lor \quad Q_{3}\ Q_{0}\quad \lor \quad Q_{1}Q_{0}\quad \lor \quad Q_{2}Q_{0}$

Wir haben nun die minimierte/vereinfachte Gleichung dieses ersten Ausgangs gefunden. Für den zweiten wird analog verfahren.

Weiterführende Literatur

• Karnaugh-Veitch-Diagramm

  Dieses Buch behandelt KV-Diagramme wesentlich tiefer und ausführlicher, während sich dieses Kapitel mehr auf das in der praktischen Digitaltechnik relvanten beschränkt.

  Zu den Konventionen: Die Konventionen weichen geringfügig ab. Beispielsweise wird $A\lor {\overline {A}}$ als A ∨ ¬A = 1 dargestellt.

Zurück zu Gesetze der Schaltalgebra | Hoch zu Speicherfreie Logik | Vor zu Übungen