KV-Diagramm: Vereinfachen mit einem Karnaugh-Veitch-Diagramm
Schaltfunktionen können mit den Regeln der Schaltalgebra umgewandelt, bzw. vereinfacht werden. Diese Anwendung ist jedoch, insbesondere bei großen Schaltfunktionen, sehr aufwendig. Das Problem kann man lösen, indem man für die Vereinfachung der Schaltfunktion eine grafische Methode wählt, nämlich das Karnaugh-Veitch-Diagramm, auch KV-Diagramm genannt.
Ein KV-Diagramm ist ein Minimierungsverfahren, das grafisch lösbar und im Gegensatz zur Schaltalgebra einfacher ist. Dabei werden die Signalzustände der Ausgangsvariablen in das Diagramm übertragen und enthält alle möglichen Miniterme. Bei n Eingangsvariablen hat das KV-Diagramm 2n-Felder. Der Term, bei dem alle Variablen genau einmal vorkommen und die Verknüpfung konjunktiv (UND-Verknüpfung) ist, ist ein Miniterm.
Vorgehensweise bei der Arbeit mit KV-Diagrammen
- Man übernimmt die Terme der disjunktiven Normalform DNF oder der konjunktiven Normalform KNF aus der Wahrheitstabelle.
- Die Felder werden entsprechend der Tabelle mit 0 oder 1 belegt.
- Dann werden die Blöcke zusammengefasst.
- min DNF: Zusammenfassung der Blöcke mit 1
- min KNF: Zusammenfassung der Blöcke mit 0
Aufbau eines KV-Diagrammes
Eine Schaltwerttabelle mit nur einer Variable hat zwei Zeilen, da eine Variable nur zwei mögliche Zustände hat (0 oder 1). Das KV-Diagramm hat somit zwei Kästchen, in die die Zeilennummern der Übersicht halber in kleiner Schrift rechts angezeigt werden.
Hat eine Schaltwerttabelle zwei Variablen, verdoppelt sich die Zeilenanzahl auf 4 (Zeilen 0 bis 3). Das KV-Diagramm muss daher erweitert werden. Hierfür wird das KV-Diagramm nach unten aufgeklappt. Die neu hinzugekommenen Zeilennummern werden gespiegelt eingetragen. Das heißt, nach 0 und 1 wären die nächsten Zeilennummern 2 und 3. Die Zahl 2 würde gespiegelt zu 0 eingetragen. Die Zahl 3 würde gespiegelt zu 1 eingetragen.
Bei drei Variablen verdoppelt sich die Zeilenanzahl erneut (Zeilen 0 bis 7). Das KV-Diagramm wird diesmal nach rechts gespiegelt aufgeklappt. Die neu hinzugekommenen Zeilennummern sind 4, 5, 6, und 7. In diesem Verbund ist 4 die kleinste Zeilennummer und wird daher gespiegelt zu 0 eingetragen, da die Zeilennummer 0 ebenfalls die kleinste Zahl im vorhergehenden Verbund (0, 1, 2, und 3) ist. Die Zeilennummer 5 wird gespiegelt zu 1 eingetragen, die Zeilennummer 6 wird gespiegelt zu 2 eingetragen und die Zeilennummer 7 wird zur Zeilennummer 3 gespiegelt.
Mit einer weiteren Variable wird das KV-Diagramm nach unten aufgeklappt und die neuen Zeilennummer erneut gespiegelt eingetragen. Nach diesem Schema kann man im Grunde beliebig fortführen. Mit jeder hinzukommenden Variable spiegelt man das KV-Diagramm einmal nach rechts und einmal nach unten und trägt die neuen Zeilennummern gespiegelt zu vorhergehenden Zeilennummern ein. Allerdings wird das irgendwann sehr unübersichtlich und man braucht sehr viel Platz, da das KV-Diagramm mit jeder neuen Variable sich die doppelte Größe einnimmt.
Die Ausgänge schreibt man in das KV-Diagramm in großer Schrift. Im folgenden Beispiel führt der Ausgang in den Zeilen 0, 1, 2 und 4 das Signal 1 und die übrigen Zeilen das Signal 0. Die Zustände werden im KV-Diagramm entsprechend eingetragen.
Zusammenfassen der Terme
Folgende Regeln gelten zum Zusammenfassen:
- Es können nur Blöcke mit 2, 4, 8, 16, usw. Elementen zusammengefasst werden.
- Die Elemente sind entweder benachbart, und/oder symmetrisch bezüglich einer oder mehrerer horizontalen oder vertikalen Symmetrieachsen.
Auf den folgenden zwei Abbildung sind z.B. Blöcke mit zwei oder vier Elementen zusammengefasst.
Man könnte Blöcke aus 4 oder 8 Elementen auch wie folgt zusammenfassen.
Man muss sich das KV-Diagramm dabei wie eine Kugel vorstellen und erhält so benachbarte Elemente. Daher ist sind auch folgende Zusammenfassungen möglich.
Vereinfachung anhand eines Beispiels
Die folgende Schaltwerttabelle soll mit Hilfe eines KV-Diagramms vereinfacht werden.
Bei der Reihenfolge der Zusammenfassung ist man frei. In diesem Beispiel werden zunächst die Zeilen 0 und 1 zusammengefasst. Die Terme der Zeilen sind wie folgt:
- Zeile 0: ¬a ∧ ¬b ∧ ¬c ∧ ¬d
- Zeile 1: a ∧ ¬b ∧ ¬c ∧ ¬d
Auf a kommt es nicht an. Daher werden die beiden Terme wie folgt zusammengefasst: ¬b ∧ ¬c ∧ ¬d
Im nächsten Schritt werden die Zeilen 0 und 2 zusammengefasst.
- Zeile 0: ¬a ∧ ¬b ∧ ¬c ∧ ¬d
- Zeile 2: ¬a ∧ b ∧ ¬c ∧ ¬d
Auf b kommt es nicht an und die Zusammenfassung ist wie folgt: ¬a ∧ ¬c ∧ ¬d
Zum Schluss werden die Zeilen 0 und 4 zusammengefasst.
- Zeile 0: ¬a ∧ ¬b ∧ ¬c ∧ ¬d
- Zeile 4: ¬a ∧ ¬b ∧ c ∧ ¬d
Auf c kommt es nicht an und die Zusammenfassung ist: ¬a ∧ ¬b ∧ ¬d
Die vereinfachte Schaltfunktion wäre: ¬b ∧ ¬c ∧ ¬d ∨ ¬a ∧ ¬c ∧ ¬d ∨ ¬a ∧ ¬b ∧ ¬d
Aus 4 Termen wurden 3 Terme und das KV-Diagramm bot dabei eine hilfreiche Unterstützung.