Karnaugh-Veitch-Diagramm

mini|Bild 1-1: Karnaugh-Veitch-Diagramm: ¬AB¬C¬D ∨ A¬B¬C¬D ∨ A¬B¬CD ∨ A¬BC¬D ∨ A¬BCD ∨ AB¬C¬D ∨ ABC¬D ∨ ABCD = AC ∨ B¬C¬D ∨ A¬B mini|Bild 1-2: Karnaugh-Veitch-Diagramm: ABCD ∨ AB¬CD ∨ ¬AB¬CD ∨ A¬BC¬D ∨ ¬A¬BC¬D ∨ ¬A¬B¬CD = ABD ∨ ¬A¬CD ∨ ¬BC¬D Das Karnaugh-Veitch-Diagramm (bzw. das Karnaugh-Veitch-Symmetrie-Diagramm, die Karnaugh-Tafel oder der Karnaugh-Plan), kurz KV-Diagramm, KVS-Diagramm oder K-Diagramm (), dient der übersichtlichen Darstellung und Vereinfachung Boolescher Funktionen in einen minimalen logischen Ausdruck. Es wurde 1952 von Edward W. Veitch [] entworfen und 1953 von Maurice Karnaugh [] zu seiner heutigen Form weiterentwickelt.

Eigenschaften Mit einem KV-Diagramm lässt sich jede beliebige disjunktive Normalform (DNF) in einen minimalen disjunktiven logischen Ausdruck umwandeln. Der Vorteil gegenüber anderen Verfahren ist, dass der erzeugte Term (meist) minimal ist. Sollte der Term noch nicht minimal sein, ist eine weitere Vereinfachung durch Anwenden des Distributivgesetzes (Ausklammern) möglich. Das Umwandeln beginnt mit dem Erstellen einer Wahrheitstafel, aus der dann die DNF abgeleitet wird, die dann wiederum direkt in ein KV-Diagramm umgewandelt wird.

Da sich die den benachbarten Feldern zugehörigen Minterme jeweils in nur einer Variablen A durch Negierung unterscheiden, wird diese (nach Ausklammern mit dem Distributivgesetz und Anwendung von ) aus dem Term, der die zusammenzufassenden Nachbarfelder beschreibt, eliminiert. Auf dieser Regel basiert die Reduzierung der Gruppen.

Die inverse Funktion findet man durch Vertauschen von „1“ und „0“ im KV-Diagramm.

Ein KV-Diagramm ist ebenfalls nützlich, um Hazards festzustellen und zu eliminieren.

Das Ausfüllen des KV-Diagramms Ein KV-Diagramm für n Eingangsvariablen hat 2n Felder (siehe Beispiel). Das KV-Diagramm wird mit den Variablen an den Rändern beschriftet. Dabei kommt jede Variable in negierter und nicht-negierter Form vor. Die Zuordnung der Variablen zu den einzelnen Feldern kann dabei beliebig erfolgen, jedoch ist zu beachten, dass sich horizontal und vertikal benachbarte Felder nur in genau einer Variablen unterscheiden dürfen (Gray-Code). Mit Hilfe der Wahrheitstabelle der zu optimierenden Funktion wird in die einzelnen Felder eine 1 eingetragen, wenn ein Minterm der Funktion vorliegt, andernfalls eine 0. Ein Minterm der Funktion liegt dann vor, wenn gilt , wobei der Vektor der Eingangsvariablen ist. In einer disjunktiven Normalform gilt dies für jeden Konjunktionsterm, der 1 liefert, da dann auch die Gesamtdisjunktion und folglich auch die Funktion 1 liefert.

KV-Diagramme eignen sich für die Vereinfachung von Funktionen mit maximal ca. 4–6 Eingangsvariablen; bis 4 Variablen sind sie übersichtlich.

Vereinfachung Sind weniger Felder des KV-Diagramms mit 1 als mit 0 belegt, so wählt man die Minterm-Methode, andernfalls die Maxterm-Methode.

Minterm-Methode mini|Bild 2-1: Die Nachbarfelder des Minterms ¬A¬B¬C¬D sind rot mini|Bild 2-2: Die Nachbarfelder des Minterms ¬A¬B¬CD sind rot mini|Bild 2-3: Die Nachbarfelder des Minterms A¬BCD sind rot Man versucht, möglichst viele horizontal und vertikal benachbarte Felder, die eine 1 enthalten (Minterme) zu rechteckigen zusammenhängenden Blöcken (Päckchen) zusammenzufassen. Als Blockgröße sind alle Potenzen von 2 erlaubt (1, 2, 4, 8, 16, 32, …). Dabei sind alle 1-Felder mit Blöcken zu erfassen. Ein Block kann unter Umständen über den rechten bzw. unteren Rand des Diagramms fortgesetzt werden. Dies erklärt sich folgendermaßen: KV-Diagramme für drei Variablen müssen im Grunde als Zylinder verstanden werden. Die Felder ganz links und ganz rechts bzw. oben und unten sind also benachbart. KV-Diagramme für vier Variablen müssen im Grunde als Torus („Donut-Form“) verstanden werden; die vier Ecken des quadratisch gezeichneten KV-Diagrammes sind benachbart. Noch komplexere Nachbarschaftsbeziehungen gelten für 5 oder mehr Variablen. Da multidimensionale Gebilde zeichnerisch schwierig zu handhaben sind, wählt man die Darstellung in der Ebene, muss dann aber die Nachbarschaftsbeziehungen im Sinn behalten. Von den ermittelten Blöcken sind so viele auszuwählen, dass alle 1-Felder überdeckt werden. Bei vielen Schaltfunktionen sind das alle zusammengefassten Blöcke, es kommt jedoch nicht selten vor, dass es Alternativen gibt. Dann besteht bei gleich großen Blöcken die freie Auswahl, andernfalls sind die größeren Blöcke zu wählen, da sie zu den kleineren (da stärker zusammengefassten) Termen führen. Die gebildeten und ausgewählten Blöcke/Päckchen wandelt man nun in Konjunktionsterme um. Dabei werden Variablen innerhalb eines Blockes, die in negierter und nicht negierter Form auftreten, weggelassen. Diese UND-Verknüpfungen werden durch ODER-Verknüpfungen zusammengefasst und ergeben eine disjunktive Minimalform.

Maxterm-Methode Die Maxterm-Methode unterscheidet sich von der Minterm-Methode lediglich in folgenden Punkten: Statt Einsen werden Nullen zu Päckchen zusammengefasst. Ein Päckchen bildet einen Disjunktionsterm (ODER-Verknüpfungen statt eines Konjunktionsterms). Die Disjunktionsterme werden konjunktiv (mit UND) verknüpft. Die Variablen werden zusätzlich einzeln negiert.

Ringsummen-Methode

Es besteht auch die Möglichkeit, eine so genannte Ringsummen-Normalform aus einem KV-Diagramm abzulesen. Da bei der Ringsummen-Normalform nur Minterme ohne Negation auftreten, dürfen nur Blöcke gebildet werden, die keine Negation enthalten. Durch eine mehrfache Überdeckung der Blöcke muss erreicht werden, dass für alle Nullen eine gerade Anzahl Überdeckungen und für alle Einsen eine ungerade Anzahl Überdeckungen vorliegen. Hierbei wird die Regel bzw. benutzt. Jeder Block liefert einen Minterm, die mittels XOR verknüpft werden. Die Ringsummen-Normalform ist bis auf die Reihenfolge der Minterme eindeutig.

Don’t-Care-Zustände mini|Bild 4: Beispiel für Don’t-Care-Zustände. Wenn die X-Felder als 1 angesehen werden, können in der Minterm-Methode die Blöcke von Einsen vervollständigt werden. Häufig gibt es Boolesche Funktionen mit Wahrheitstabellen, in denen nicht für jede Kombination der Eingangsvariablen ein Wert der Ausgangsvariablen definiert sein muss. Man nennt solche Ausgangszustände Don’t-Care-Terme und bezeichnet sie mit , da sie sowohl den Wert 1 als auch 0 annehmen können. Diese -Felder dürfen als 1 oder 0 angesehen werden, um in der Minterm- oder Maxterm-Methode Blöcke von Einsen oder Nullen zu vervollständigen. Ein gutes Beispiel dafür ist die Dekodierung einer binär codierten Dezimalzahl (BCD). Hier spielen nur die Zahlen 0 bis 9 eine Rolle, die sogenannten Pseudotetraden dürfen ein beliebiges Ergebnis liefern, sind also Don’t-Care-Terme.

KV-Diagramm bei mehreren Ausgängen Wenn eine Digitalschaltung mehrere Ausgänge hat, die Wahrheitstabelle also mehrere Ergebnisspalten hat, dann muss für jeden Ausgang ein eigenes KV-Diagramm erstellt werden.

Beispielsweise hat ein 1-aus-n-Decoder die nebenstehende Wahrheitstabelle und für seine 4 Ausgänge die 4 nebenstehenden KV-Diagramme. mini|zentriert|hochkant=2|Bild 5-1: Wahrheitstabelle und KV-Diagramm für 1-aus-n-Decoder

Eingabe Ausgabe Zahl 1 Zahl 2 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 1 0 1 0 1 0 1 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 1 0 0 0 0 0 1 1 0 0 1 0 0 1 1 0 1 0 0 1 0 1 0 1 1 1 0 0 1 1 0 0 0 0 1 1 1 0 1 0 0 1 1 1 1 0 0 0 1 1 1 1 1 0 1 0

Ein weiteres Beispiel für mehrere Ausgänge ist ein 2+2-Bit-Komparator. Er hat vier Eingangsvariablen und drei Ausgangvariablen. Die Zahl A besteht aus 2 Bit ( und ) und die Zahl B besteht aus 2 Bit ( und ). Je nachdem, ob „“, „“ oder „“ geben die drei Ausgänge eine 1 oder 0 aus.

Die dazugehörige Wahrheitstabelle ist rechts. Die Bilder 5-2 bis 5-4 zeigen die 3 KV-Diagramme für die 3 Ausgänge.

Normalformen

A B C D X 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 1 0 1 0 1 1 0 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 0 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 1

Üblicherweise werden Gruppen für die Einsen gebildet (Bild 6-2). Die Einsen leiten sich aus der Disjunktiven Normalform (DNF) ab. Es gibt aber auch die Möglichkeit, Gruppen aus den Nullen zu bilden (in Bild 6-1 und den nachfolgenden sind die Nullen nicht extra eingezeichnet, aber trotzdem vorhanden). Die Nullen stehen für die Konjunktive Normalform (KNF).

Die DNF lautet: ¬AB¬C¬D ∨ ¬AB¬CD ∨ ¬ABCD ∨ AB¬C¬D ∨ AB¬CD ∨ ABCD.

Die KNF lautet: (A∨B∨C∨D) ∧ (A∨B∨C∨¬D) ∧ (A∨B∨¬C∨D) ∧ (A∨B∨¬C∨¬D) ∧ (A∨¬B∨¬C∨D) ∧ (¬A∨B∨C∨D) ∧ (¬A∨B∨C∨¬D) ∧ (¬A∨B∨¬C∨D) ∧ (¬A∨B∨¬C∨¬D) ∧ (¬A∨¬B∨¬C∨D).

Die DNF wird aus der Tabelle ausgelesen, indem jede Zeile mit dem Ausgabewert „Eins“ aufgeschrieben wird. Die Eingangsvariablen für die eine Null steht, werden in negierter Form genommen. Alle Terme für die Zeilen (im vorliegenden Beispiel 6 Zeilen) werden durch „∨“ verbunden.

Für die KNF werden alle Zeilen mit dem Ausgabewert „Null“ rausgeschrieben, wobei Eingangsvariablen für die eine „Eins“ steht, in negierter Form genommen werden. Alle Terme für die Zeilen (im vorliegenden Beispiel 10 Zeilen) werden durch „∧“ verbunden, die Literale selber werden durch „∨“ verbunden.

mini|Bild 6-1 mini|Bild 6-2: Polynom BD ∨ B¬C¬D(Minimalpolynom: B (D ∨ ¬C¬D)) mini|Bild 6-3: (¬C ∨ D) ∧ B

Fehler in Bild 6-2: Das Minimalpolynom lautet: B (D ∨ ¬C), da das rote Zweier-Kästchen nach oben hin zu einem Vierer-Kästchen erweitert werden kann, wodurch mehr Literale wegfallen und das endgültige Minimalpolynom der Länge 4 (BD ∨ B¬C) entsteht. Wichtig hierbei zu beachten ist, dass dadurch zwar zwei einschlägige Indizes mehrfach verwendet werden, dies aber sowohl erlaubt als auch nötig ist, um das Minimalpolynom zu bilden.

Gesetzmäßigkeiten bei der Reduzierung

Durch die Zusammenfassung zu einer Gruppe der Größe 2n reduziert sich der logische Ausdruck um n Variablen. Das ist unabhängig davon, welche Lage oder Form die Gruppe hat oder ob sie über die Ränder hinwegreicht. Das ist auch unabhängig davon, ob es sich um ein 2×2, 2×4, 4×4 oder 4x4x4 KV-Diagramm handelt. Eine Achtergruppe (23) reduziert sich um 3 Variablen (n = 3) – Bild 9-1. Eine Vierergruppe (22) reduziert sich um 2 Variablen (n = 2) – Bild 9-2 und 9-3. Eine Zweiergruppe (21) reduziert sich um 1 Variable (n = 1) – Bild 9-4 und 9-5. Eine Einergruppe (20) reduziert sich um Null Variablen (n = 0) – Bild 9-6.

Regeln für die Gruppenbildung Benachbarte Felder, in die eine Eins eingetragen ist, werden zu Gruppen zusammengefasst. Eine Gruppe darf keine Felder mit Nullen enthalten. (Oft werden die Nullen nicht mitgeschrieben und die Felder leer gelassen. In diesem Fall darf eine Gruppe keine leeren Felder enthalten.) Alle Einsen müssen in Gruppen zusammengefasst werden. Benachbarte Felder mit Einsen werden zu einer Gruppe zusammengefasst. (Felder, die sich an den Ecken berühren, diagonal, zählen nicht als benachbart.) Die Gruppen müssen so groß wie möglich sein. Es müssen so wenig Gruppen wie möglich gebildet werden. Die Gruppen dürfen nur Größen haben, die Zweierpotenzen entsprechen (1, 2, 4, 8, 16, 32, 64 …). Die Gruppen müssen rechteckige Blöcke sein. Die Gruppen dürfen sich überlappen. Die Gruppen dürfen über die Ränder hinweggehen. Zwei Gruppen dürfen nicht exakt die gleichen Einsen umfassen. Es darf keine Gruppe vollständig von einer anderen Gruppe umschlossen werden. Zusammenfassung: Man sucht eine vollständige Überdeckung der Einsen mit möglichst großen rechteckigen Blöcken.

KV-Tafeln für 2 und 4 Variablen mini|Bild 1 mini|Bild 2

Wer häufig mit dem KV-Diagramm arbeitet, wünscht sich eine Methode, ein KV-Diagramm schnell ausfüllen zu können.

Karnaugh-Veitch-Diagramm

Bron en licentie