1010. Schaltgleichungen grafisch vereinfachen mittels KV-Diagramm

Zu Beginn …

Vielleicht ist dir bei den Übungen zum rechnerischen Vereinfachen von Schaltgleichungen aufgefallen, dass dieses Vorgehen doch so seine Tücken hat. Wenn man hierin keine große Übung hat oder die Gleichungen komplizierter werden, dann übersieht man oftmals Vereinfachungsmöglichkeiten.

Daher wurde für die manuelle Vereinfachung von Schaltgleichungen auch ein grafisches Verfahren entwickelt, die sogenannten KV-Diagramme. Sie sind benannt nach Ihren Entwicklern Maurice Karnaugh und Edward Veitch. Sie dienen dazu, eine Schaltbelegungstabelle so aufzuschreiben, dass man mit wenig Mühe daraus direkt die vereinfachte Schaltgleichung in einer der Normalformen ablesen kann.

Die das funktioniert? Das lernst du auf dieser Seite!

Beispiel "Dualzahlen-Vergleicher"

Wir schauen uns nun ein ganz konkretes Beispiel an, bei dem wir aus einer Aufgabenstellung heraus zunächst die Schaltbelegungstabelle aufstellen. Diese wandeln wir dann in ein KV-Diagramm um und lesen daraus direkt eine vereinfachte Schaltgleichung in Normalform ab.

Aufgabenstellung

Ermittle eine möglichst minimale Schaltgleichung für ein Schaltnetz, welches zwei zweistellige Dualzahlen ($a_{1}a_0$ und $b_{1}b_0$) miteinander vergleichen kann. Das Ergebnis soll $1$ sein, wenn $a < b$. Es soll dagegen $0$ sein, wenn $a \ge b$.

Schritt 1: Schaltbelegungstabelle aufstellen

Wir haben als Eingangswerte zwei zweistellige Dualzahlen und somit insgesamt vier Dualziffern, die sich ändern können. Wie viele Zeilen braucht also unsere Tabelle?

Richtig ;)

Für die Kombination der vier Dualziffern gibt es $2^4 = 16$ verschiedene Möglichkeiten. Somit braucht unsere Schaltbelegungstabelle auch 16 Zeilen. In diese können wir gleich die Eingangswerte eintragen:

Wenn man jetzt mit einer so langen Tabelle hantiert, so bietet es sich der Übersicht halber an, die Zeilen zu nummerieren. Bei einem Blick auf die Eingangswerte in der Tabelle fällt auf, dass diese zeilenweise die Dezimalzahlen 0 bis 15 als Dualzahlen beinhalten (0000 bis 1111). So kann man dies gleich für die Nummerierung ausnutzen:

Jetzt müssen wir noch die Ausgangswerte eintragen: Diese sollen $1$ sein, wenn $a < b$ (und $0$, wenn $a \ge b$). Fülle diese Spalte zur Übung am Besten selbst einmal aus, bevor zu weiterliest!

So, die vollständige Schaltbelegungstabelle sieht folgendermaßen aus:

Zwischenfazit:

In der Spalte der Ausgangswerte stehen sechs Einsen und 10 Nullen. Würden wir jetzt einfach die Normalformen aus der Tabelle ablesen, so hätte die DNF sechs Klammerausdrücke (Min-Terme) und die KNF sogar 10 Klammerausdrücke (Max-Terme) mit je 4 Schaltvariablen. Diese Schaltgleichungen "per Hand" rechnerisch zu vereinfachen wäre schon recht aufwändig …

Schritt 2: KV-Diagramm aufstellen

Daher nutzt man für die manuelle Vereinfachung lieber die grafische Variante mittels KV-Diagramm (auch Karnaugh-Tafel genannt). Diese beruht auf den Regeln der Schaltalgebra und hier vor allem darauf, dass eine Schaltvariable in einem Term oft entfallen kann, wenn sie sowohl negiert als auch nichtnegiert darin auftritt.

a) Matrix aufzeichnen und beschriften

Zunächst müssen wir eine sogenannte Matrix aufstellen - quasi eine "Spezial- Tabelle". Da wir in unserer Schaltbelegungstabelle 16 Zeilen haben, hat die Matrix 16 Felder. Wir brauchen somit eine 4x4-Matrix.

An der linken und der oberen Seite wird die Beschriftung angefügt. In unserem Fall erscheinen links die beiden Eingangswerte der Dualzahl $a$ und oben die beiden Eingangswerte der Dualzahl $b$. Für beide Dualzahlen gibt es ja vier verschiedene Möglichkeiten: $00$, $01$, $10$ und $11$.

Man könnte nun einfach die vier Zeilen und Spalten der Matrix in dieser Reihenfolge damit beschriften. Allerdings bekommt man dann kein KV-Diagramm ;)

Bei einem KV-Diagramm müssen die Felder nämlich so angeordnet werden, dass nachher die Schaltvariablen möglichst negiert als auch nichtnegiert nebeneinander stehen - nur dann lassen sie sich nämlich herauskürzen. Das gelingt genau dann, wenn sich die Beschriftungen der Zeilen bzw. Spalten nacheinander nur in jeweils 1 Bit unterscheiden.

Konkret heißt das:

• Bei der ersten Zeile und Spalte sind die Eingangswerte jeweils $00$.

• Bei der zweiten Zeile und Spalte darf nun nur eine der Nullen zu einer Eins werden. Also erhalten sie die Beschriftung $01$. (Das hätte man wohl auch intuitiv als zweites genommen.)

• Bei der dritten Zeile und Spalte müssen wir allerdings aufpassen: statt dual weiter zu zählen (und eine $10$ zu vergeben), werden diese mit $11$ beschriftet !!!

• Die vierte Zeile und Spalte erhalten schließlich die Beschriftung $10$.

Das Ganze sieht dann folgendermaßen aus:

b) Matrix-Felder nummerieren

Wenn man sich nun einmal die erste Zeile der Matrix anschaut, so erkennt man schnell deren "Abstammung" von der Schaltbelegungstabelle: Das erste Feld der Matrix entspricht der ersten Zeile der Schaltbelegungstabelle (Zeile Nr. 0, alle Eingangswerte sind $0$).

Das zweite Feld entspricht der zweiten Zeile (Zeile Nr.1, nur der Eingangswert $b_0$ ist $1$). Das dritte Feld der Matrix entspricht durch die "besondere Anordnung" allerdings der vierten Zeile der Tabelle - und das vierte Feld der dritten Zeile.

Um den Überblick zu behalten, lohnt es sich daher, die Felder passend zu den Tabellenzeilen zu nummerieren:

Zwischenfazit:

Ganz schön viel Aufwand, oder? Und das soll schneller und fehlerfreier gehen als die rechnerische Variante? Ja! Denn für eine häufig auftretende Schaltbelegungstabelle mit 16 Zeilen sieht das Grundgerüst eines KV-Diagramms immer so aus - nur die Variablen heißen anders. Aber die sonstige Beschriftung und Nummerierung ändert sich nicht. Hat man sich das Prinzip einmal eingeprägt, geht das Aufschreiben fix von der Hand! Aber sehen wir weiter …

c) Ausgangswerte aus Schaltbelegungstabelle eintragen

Dieser Schritt ist nun wirklich simpel: Einfach die Ausgangswerte aus der jeweiligen Zeile der Schaltbelegungstabelle in das entsprechende Feld des KV-Diagramms übertragen. Dabei erhältst du folgendes Ergebnis:

d) Blockbildung von Werten im KV-Diagramm

Jetzt kommt endlich die grafische Komponente ins Spiel. Es lohnt sich also, ein paar verschiedenfarbige Stifte zur Hand zu haben.

An dieser Stelle bildet man nun rechteckige Blöcke von Einsen (für eine DNF) oder Nullen (für eine KNF). Wir wählen hier effizienter Weise die Blockbildung von Einsen, da es weniger von ihnen gibt.

Die Blöcke müssen jeweils eine Anzahl von Einsen beinhalten, die einer Zweierpotenz entspricht (1, 2, 4, 8, usw.). Diese sollen möglichst groß sein und sie dürfen sich auch überlappen. Die Blöcke können auch über den Rand hinaus gehen - sie setzen dann an der gegenüberliegenden Seite fort. Am Ende sollen alle Einsen einem Block angehören.

Bei unserem Beispiel können wir rechts oben einen Viererblock bilden (Felder 2,3,6,7), einen "normalen" Zweierblock (Felder 1 und 3), sowie einen Zweierblock "über den Rand hinaus" (Felder 3 und 11). In das Diagramm eingetragen ergibt sich folgendes Bild:

Schritt 3: Schaltgleichung ablesen

Nun können wir mithilfe der Blöcke direkt die minimierte Schaltgleichung in disjunktiver Normalform ablesen.

Innerhalb der Blöcke können dabei alle Schaltvariablen entfallen, die sowohl negiert, als auch nicht negiert auftauchen.

Schauen wir uns dazu den Viererblock an (türkis; Felder 2, 3, 6, 7):

• In diesem ist $b_0$ einmal mit dem Eingangswert $1$ (3. Spalte) und einmal mit dem Eingangswert $0$ (4. Spalte) vertreten - also einmal nichtnegiert und einmal negiert. Daher entfällt $b_0$ bei der anschließenden Min-Term-Bildung dieses Blocks.

• Dasselbe gilt für die Schaltvariable $a_0$. Diese ist in der 1. Zeile mit Eingangswert $0$ vorhanden und in der 2. Zeile mit Eingangswert $1$). Daher entfällt auch sie bei der Min-Term-Bildung dieses Blocks.

• Übrig bleiben also nur noch die Schaltvariable $a_1$ (Eingangswert $0$ in den Zeilen 1 und 2), sowie die Schaltvariable $b_1$ (Eingangswert $1$ in den Spalten 3 und 4).

• Der Min-Term des Viererblocks lautet also: $\quad \color{#009999} {\overline{a_1} \wedge b_1}$

"Normaler" Zweierblock (grün; Felder 1 und 3):

• In diesem ist $b_1$ mit unterschiedlichen Eingangswerten enthalten (2. und 3. Spalte) und kann deshalb bei der anschließenden Min-Term-Bildung dieses Blocks entfallen. Alle anderen Schaltvariablen werden einbezogen.

• Der Min-Term des "normalen" Zweierblocks lautet somit: $\color{#006400} {\quad \overline{a_1} \wedge \overline{a_0} \wedge b_0}$

Zweierblock "über den Rand hinaus" (orange; Felder 3 und 11):

• In diesem ist $a_1$ mit unterschiedlichen Eingangswerten enthalten (1. und 4. Zeile) und kann deshalb bei der anschließenden Min-Term-Bildung dieses Blocks entfallen. Alle anderen Schaltvariablen werden einbezogen.

• Der Min-Term dieses Zweierblocks lautet somit: $\color{#ff6600} {\quad \overline{a_0} \wedge {b_1} \wedge b_0}$

Die komplette Schaltgleichung lautet somit:

Lösung im Überblick

• Ausgefülltes KV-Diagramm:

• minimierte Schaltgleichung in disjunktiver Normalform:

Das Vereinfachen war doch tatsächlich einfach, nicht wahr ;)