Informations- und Kommunikationstechnik

KV-Diagramme

Edward Veitch entwickelte 1952 ein grafisches Verfahren zur Optimierung digitaler Schaltfunktionen. Es wurde ein Jahr später von Maurice Karnaugh erweitert und wird als Karnaugh-Veitch-Diagramm, kurz KV-Diagramm bezeichnet. Das KV-Diagramm hat zu allen logischen Kombinationen der Eingangsvariablen je ein Feld. Bei n Eingangsvariablen gibt es 2n Felder.

Bei der digitalen Schaltungssynthese wird aus der Wahrheitstabelle die Funktionsgleichung als disjunktive oder konjunktive Normalform erstellt. Die direkte Umsetzung führt fast immer zu einer aufwendigen Digitalschaltung. Mit den De Morganschen Gesetzen und der Schaltalgebra lassen sich optimierte und meist minimierte Funktionsgleichungen finden. Die KV-Diagramme vereinfachen die Optimierung und reduzieren die mathematischen Umrechnungen.

KV-Diagramm für zwei Eingangsvariable

Das folgende Bild zeigt den Zusammenhang zwischen der Wahrheitstafel und dem KV-Diagramm. Jeder Platz entspricht einer schaltalgebraischen Gleichung. In ihr kommt jede Variable in der normalen und negierten Form je einmal vorkommt. Anstelle der Gleichungen schreibt man die Variablen an die Ränder des KV-Diagramms und erhält ein koordinatives Zuordnungssystem. Die Variablennamen können in den Spalten der Wahrheitstabelle anders eingeordnet sein. Die Randbezeichnungen des KV-Diagramms ändern sich entsprechend. Die ermittelbare Funktionsgleichung bleibt davon unbeeinflusst.

allgemeines KV-Diagramm

Jedes Feld ist durch seine Zeilen- und Spaltenvariable eindeutig bestimmt. Ist die optimierte DNF gesucht, dann werden die Minterme mit den Feldwerten 1 betrachtet. Die Variablen sind durch UND verknüpft. Die Einzelverknüpfungen sind durch ODER verbunden. Ist die optimierte KNF gesucht, dann werden Maxterme mit den Feldwerten 0 betrachtet, deren Variablen sind dann durch ODER zu verknüpfen, während die Einzelterme durch UND verbunden werden.

KV-Diagramm für drei Eingangsvariable

Bei drei Eingangsvariablen mit je zwei logischen Schaltzuständen sind acht Felder im KV-Diagramm zu bezeichnen. Die Wahrheitstafel zeigt Minterme mit logischem Ausgang 1. Sie werden nach den oben genannten Regeln in das KV-Diagramm übertragen.

KV-Diagramm für n=3

KV-Diagramm für vier Eingangsvariable

Bei vier Eingangsvariablen besitzt das KV-Diagramm 16 Felder. Die Variablen sind so am Rand zu verteilen, dass sich ungleiche Variablen nicht gegenseitig überschneiden und gleiche Variablennamen paarweise normal und negiert nebeneinander auftreten. Die ebene Darstellung des KV-Diagramms ist über die Diagonalen verbunden als Kugel zu sehen.

KV-Diagramm für n=4

Ab fünf Variablen lassen sich KV-Diagramme nicht mehr in einer Ebene darstellen. Sie bilden Quader mit übereinander liegenden Ebenen. Zur besseren Übersicht werden sie nach rechts abgebaut und nebeneinander gelegt. In allen Fällen sind beim Erstellen der KV-Diagramme folgende Regeln zu beachten:

Erstellen der Funktionsgleichung aus dem KV-Diagramm

Aus der Wahrheitstabelle folgt die Funktionsgleichung entweder durch Herausschreiben der disjunktiven oder konjunktiven Normalform. Ein KV-Diagramm ist eine andere Darstellung der Wahrheitstabelle. Lassen sich die 1-Zustände der Minterme oder 0-Zustände der Maxterme durch besondere Blockbildung zusammenfassen, dann ergeben sich bereits minimierte Funktionsgleichungen. Das erspart eine meist langwierige Optimierung der DNF oder KNF mithilfe der Schaltalgebra. Bei der Blockbildung sind einige Regeln zu beachten:

Beispiele zur Blockbildung

Im KV-Diagramm lassen sich benachbarte Vollkonjunktionen, Feldwerte 1, oder benachbarte Volldisjunktionen, Feldwerte 0, zusammenfassen. Hat man sich für Vollkonjunktionen (UND) entschieden, dann werden eingetragene 0-Werte nicht berücksichtigt. Eine entsprechende Regel gilt für Volldisjunktionen (ODER). KV-Diagramme mit zwei Eingangsvariablen sind sehr einfach zu überblicken. Die Skizze zeigt diese KV-Diagramme mit erlaubten Blöcken für Minterme.

Blockbildung im KV-Diagramm für n=2

Optimierte DNF aus dem KV-Diagramm

Optimierte KNF aus dem KV-Diagramm

Die folgenden drei Beispiele zeigen für Minterme das Erstellen der Funktionsgleichung aus der Wahrheitstabelle mit vollständiger DNF die Optimierung durch die Schaltalgebra oder direkt aus dem KV-Diagramm. Die Blockbildung erfolgt mit benachbarten Vollkonjunktionen. Dabei sollten größtmögliche Schleifen gebildet und überflüssige Schleifen vermieden werden.

Blockbildung im KV-Diagramm für n=3
Blockbildung im KV-Diagramm für n=3

Das letzte Beispiel zeigt, dass auch mit den Maxtermen die Funktionsgleichung aus dem KV-Diagramm ausgelesen werden kann. Dazu werden Blöcke mit den Feldwerten 0 gebildet. Die dort gemeinsam auftretenden Variablen werden negiert durch ODER verknüpft und die Einzelterme dann durch UND verknüpft.

Blockbildung im KV-Diagramm für n=3

KV-Diagramme für vier Eingangsvariable bieten noch mehr Möglichkeiten zur Blockbildung. Das folgende Bild zeigt einige Beispiele zum Erstellen der Funktionsgleichung nach der DNF. Auch hier zeigt das letzte Beispiel, dass mit dem KV-Diagramm gleichermaßen auf Minterme oder Maxterme angewendet recht schnell die optimierte Funktionsgleichung ermittelt werden kann.

Funktionsgleichung aus dem KV-Diagramm für n=4