Quelltext der Seite Karnaugh-Veitch-Diagramm: Theorie des KV-Diagramms

[[Bild:Karnaugh.svg|thumb|250 px|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]]
[[Bild:Karnaugh map KV 4Variables 02.png|thumb|250 px|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''' (engl. ''Karnaugh map''), dient der übersichtlichen Darstellung und Vereinfachung [[w:Boolesche Funktion|Boolescher Funktionen]] – Umwandlung der [[w:disjunktive Normalform|disjunktiven Normalform]] in einen minimalen logischen Ausdruck. Es wurde 1952 von [[w:Edward W. Veitch|Edward W. Veitch]] [IPA: viːtʃ] entworfen und 1953 von [[w:Maurice Karnaugh|Maurice Karnaugh]] [IPA: ˈkɑːɹnɔː] zu seiner heutigen Form weiterentwickelt.

== Eigenschaften ==
Mittels eines KV-Diagramms lässt sich jede beliebige [[w:disjunktive Normalform|disjunktive Normalform]] (DNF) in einen minimalen 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 [[w:Wahrheitstafel|Wahrheitstafel]], aus der dann die DNF abgeleitet wird, die dann wiederum direkt in ein KV-Diagramm umgewandelt wird.

Da sich benachbarte Felder jeweils in einer Variable nur um ein [[w:Bit|Bit]] unterscheiden, ist folgende Regel anwendbar: A ∨ ¬A = 1. Auf dieser Regel basiert die Reduzierung der Gruppen.

Die inverse Funktion <math>\bar{F}</math> findet man durch Vertauschen von „1“ und „0“ im KV-Diagramm.

Ein KV-Diagramm ist ebenfalls nützlich, um [[w:Glitch (Elektronik)|Hazards]] festzustellen und zu eliminieren.

== Das Ausfüllen des KV-Diagramms ==
Ein KV-Diagramm für n Eingangsvariablen hat 2<sup>n</sup> 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. Mit Hilfe der [[w:Wahrheitstabelle|Wahrheitstabelle]] der zu optimierenden Funktion wird in die einzelnen Felder eine 1 eingetragen, wenn ein ''[[w:Minterm|Minterm]] der Funktion'' vorliegt, andernfalls eine 0. Ein Minterm m der Funktion liegt dann vor, wenn gilt
: <math>m(\underline X) = 1 \Rightarrow F(\underline X) = 1</math>,
wobei <math>\underline X</math> der Vektor der Eingangsvariablen ist. In einer [[w:disjunktive Normalform|disjunktiven Normalform]] gilt dies für jeden [[w:Konjunktionsterm|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 bis zu 5 Eingangsvariablen.

=== Vereinfachung ===
Sind weniger Felder des KV-Diagramms mit 1 als mit 0 ausgefüllt, wählt man die Minterm-Methode, andernfalls die Maxterm-Methode.

==== Minterm-Methode ====
[[Bild:Karnaugh map KV 4mal4 11.svg|thumb|200 px|Bild 2-1: Nachbarfelder des „Einser“-Feldes – rote Felder]]
[[Bild:Karnaugh map KV 4mal4 12.svg|thumb|200 px|Bild 2-2: Nachbarfelder des „Einser“-Feldes – rote Felder]]
[[Bild:Karnaugh map KV 4mal4 13.svg|thumb|200 px|Bild 2-3: Nachbarfelder des „Einser“-Feldes – rote Felder]]
* Man versucht, möglichst viele horizontal und vertikal benachbarte Felder, die eine 1 enthalten (Minterme) zu zusammenhängenden 2er-, 4er-, 8er- oder 16er-Blöcken (sogenannten ''Päckchen'') zusammenzufassen. Als Blockgröße sind alle Potenzen von 2 erlaubt, bei denen der [[w:Exponent|Exponent]] eine natürliche Zahl größer Null und höchstens so groß wie die Anzahl der Variablen ist. Bei Zwei bis Fünf Variablen ergeben sich damit folgende Werte: 
** Zwei Variablen: 2 oder 4 Felder pro Päckchen.
** Drei Variablen: 2, 4 oder 8.
** Vier Variablen: 2, 4, 8 oder 16.
** Fünf Variablen: 2, 4, 8, 16 oder 32.
Je nach Wertetabelle kann es jedoch vorkommen, dass es in der KV-Tafel eine alleinstehende 1 gibt. Diese alleinstehende 1 muss natürlich bei dem späteren Bilden der Schaltgleichung auch mit berücksichtigt werden.
* 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 [[w:Zylinder (Geometrie)|Zylinder]] verstanden werden. Die Felder ganz links und ganz rechts sind also benachbart. KV-Diagramme für vier Variablen müssen im Grunde als [[w:Torus|Torus]] („Donut-Form“) verstanden werden. Die vier Ecken des quadratisch gezeichneten KV-Diagrammes sind im Grunde 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.
* Die gebildeten 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 [[w:Disjunktive Normalform|disjunktive Normalform]].

==== 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 [[w:Disjunktionsterm|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 gibt auch eine Möglichkeit eine sogenannte Ringsummen-Normalform aus einem KV-Diagramm abzulesen. Dazu wählt man die Blöcke aus Nullen und Einsen so, dass die Nullen von einer geraden und die Einsen durch eine ungerade Anzahl von Blöcken überdeckt werden. Die Terme werden dann mit [[w:XOR|XOR]] verknüpft und ergeben eine minimierte Funktion.

== Don’t-Care-Zustände ==
[[Bild:Karnaugh map KV 4mal4 Gruppe08.svg|thumb|180 px|Bild 4: Beispiel für Don’t-Care-Zustände]]
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 X, da sie sowohl den Wert 1 als auch 0 annehmen können. Diese X-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 von [[w:BCD-Code|binär codierten Dezimalzahl]] (BCD). Hier spielen nur die Zahlen 0 bis 9 eine Rolle, die sogenannten [[w:Pseudotetraden|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 [[w:1-aus-n-Decoder|1-aus-n-Decoder]] die nebenstehende Wahrheitstabelle und für seine 4 Ausgänge die 4 nebenstehenden 4 KV-Diagramme.
[[Bild:Karnaugh map KV 1-aus-n-Decoder.svg|thumb|center|500 px|Bild 5-1: Wahrheitstabelle und KV-Diagramm für [[w:1-aus-n-Decoder|1-aus-n-Decoder]] ]]


<br style="clear:both;" />

{| class="prettytable float-right"
|-
! colspan="4 "| Eingabe !! colspan="3" | Ausgabe
|-
! colspan="2 "| Zahl 1!! colspan="2 "| Zahl 2 !! <math>A<B</math> !! <math>A=B</math> !! <math>A>B</math>
|-
! <math>A_1</math> !! <math>A_0</math> !! <math>B_1</math> !!<math>B_0</math> !! <math>X</math> !! <math>Y</math> !! <math>Z</math>
|-
| 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 ein 2+2-Bit-[[w:Komparator (Digitaltechnik)|Vergleicher]]. Er hat 4 Eingangsvariablen und 3 Ausgangvariablen. Die Zahl A besteht aus 2 Bit (<math>A_1</math> und <math>A_0</math>) und die Zahl B besteht aus 2 Bit (<math>B_1</math> und <math>B_0</math>). Je nachdem, ob ''„A < B“'', ''„A = B“'' oder ''„A > B“'' geben die drei Ausgänge (X, Y, Z) 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.

{| class="float-left"
| [[Bild:Karnaugh map KV 2plus2 Komparator 1.svg|thumb|left|160 px|Bild 5-2: Ausgang X]]
| [[Bild:Karnaugh map KV 2plus2 Komparator 2.svg|thumb|left|160 px|Bild 5-3: Ausgang Y]]
| [[Bild:Karnaugh map KV 2plus2 Komparator 4.svg|thumb|left|160 px|Bild 5-4: Ausgang Z]]
|}
<br style="clear:both;" />

== Normalformen ==

{| class="float-right"
|- style="background-color:#f0f0f0;"
! width="20%"| &nbsp; A &nbsp;
! width="20%"| &nbsp; B &nbsp;
! width="20%"| &nbsp; C &nbsp;
! width="20%"| &nbsp; D &nbsp;
! width="20%"| &nbsp; X &nbsp;
|- align="center"
| 0 ||0 ||0 ||0 ||'''0'''
|- align="center"
| 0 ||0 ||0 ||1 ||'''0'''
|- align="center"
| 0 ||0 ||1 ||0 ||'''0'''
|- align="center"
| 0 ||0 ||1 ||1 ||'''0'''
|- align="center"
| 0 ||1 ||0 ||0 ||'''1'''
|- align="center"
| 0 ||1 ||0 ||1 ||'''1'''
|- align="center"
| 0 ||1 ||1 ||0 ||'''0'''
|- align="center"
| 0 ||1 ||1 ||1 ||'''1'''
|- align="center"
| 1 ||0 ||0 ||0 ||'''0'''
|- align="center"
| 1 ||0 ||0 ||1 ||'''0'''
|- align="center"
| 1 ||0 ||1 ||0 ||'''0'''
|- align="center"
| 1 ||0 ||1 ||1 ||'''0'''
|- align="center"
| 1 ||1 ||0 ||0 ||'''1'''
|- align="center"
| 1 ||1 ||0 ||1 ||'''1'''
|- align="center"
| 1 ||1 ||1 ||0 ||'''0'''
|- align="center"
| 1 ||1 ||1 ||1 ||'''1'''
|}

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

Die DNF lautet: ¬AB¬C¬D ∨ ¬AB¬CD ∨ ¬ABCD ∨ AB¬C¬D ∨ AB¬CD ∨ ABCD.<br />

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.

{| class="float-left"
| [[Bild:Karnaugh map KV KNF 1.svg|thumb|180 px|Bild 6-1]]
| [[Bild:Karnaugh map KV KNF 2.svg|thumb|180 px|Bild 6-2: Polynom '''BD ∨ B¬C¬D'''<br />([[w:Minimalpolynom|Minimalpolynom]]: '''B (D ∨ ¬C¬D)''')]]
| [[Bild:Karnaugh map KV KNF 3.svg|thumb|180 px|Bild 6-3: (¬C ∨ D) ∧ B]]
|}
<br style="clear:both;" />

== Kompakte Schreibweise ==

Eine kompakte Schreibweise für ein KV-Diagramm (Bild 7-1) zeigt folgendes Beispiel:<br />
F = &sum; (0, 3, 6, 7, 10, 11, 12, 14, 15)

Ausgehend von einer durchgehenden Nummerierung (genauer gesagt: Indexierung – beginnend bei Feld 0) der Felder, wie in Bild 7-2 dargestellt, werden die Nummern der Felder aufgezählt, in denen eine Eins eingetragen ist.

{| class="float-left"
| [[Bild:Karnaugh map KV 4mal4 Gruppe01j.svg|thumb|200 px|Bild 7-1]]
| [[Bild:Karnaugh map KV Kompakte Schreibweise.svg|thumb|200 px|Bild 7-2]]
|}
<br style="clear:both;" />

== Gesetzmäßigkeiten bei der Reduzierung ==

Durch die Zusammenfassung zu einer Gruppe der Größe 2<sup>n</sup> 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 2x2, 2x4, 4x4 oder 4x4x4 KV-Diagramm handelt.
* Eine Achtergruppe (2<sup>3</sup>) reduziert sich um 3 Variablen (n = 3) – Bild 9-1.
* Eine Vierergruppe (2<sup>2</sup>) reduziert sich um 2 Variablen (n = 2) – Bild 9-2 und 9-3.
* Eine Zweiergruppe (2<sup>1</sup>) reduziert sich um 1 Variable (n = 1) – Bild 9-4 und 9-5.
* Eine Einergruppe (2<sup>0</sup>) reduziert sich um Null Variablen (n = 0) – Bild 9-6.
<br style="clear:both;" />

{| class="float-center"
| [[Bild:Karnaugh map KV 4mal4 Gruppe01n.svg|thumb|left|200 px|Bild 9-1: Ergebnis: '''D''']]
| [[Bild:Karnaugh map KV 4mal4 Gruppe01o.svg|thumb|left|200 px|Bild 9-2: Ergebnis: '''CD''']]
| [[Bild:Karnaugh map KV 4mal4 Gruppe01p.svg|thumb|left|200 px|Bild 9-3: Ergebnis: '''B¬D''']]
|}

{| class="float-center"
| [[Bild:Karnaugh map KV 4mal4 Gruppe01q.svg|thumb|left|200 px|Bild 9-4: Ergebnis: '''AB¬C''']]
| [[Bild:Karnaugh map KV 4mal4 Gruppe01s.svg|thumb|left|200 px|Bild 9-5: Ergebnis: '''¬B¬C¬D''']]
| [[Bild:Karnaugh map KV 4mal4 Gruppe01sa.svg|thumb|left|200 px|Bild 9-6: Ergebnis: '''¬ABCD''']]
|}

<br style="clear:both;" />

== 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.
* 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 ==
{| valign
| [[Bild:2x2_karn.svg|thumb|200px|Bild 1]]
| [[Bild:Karnaugh map KV 4mal4 Gruppe01jA.svg|thumb|200px|Bild 2]]
|}

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

Dies wird bei oben dargestellter Anordnung bei den vier Eingangsvariablen ''A'', ''B'', ''C'' und ''D'' durch folgende Anordnung erreicht:

{| valign
| [[Bild:Karnaugh map KV 4mal4 Gruppe101.svg|thumb|200px|Bild 3]]
| [[Bild:Karnaugh map KV 4mal4 Gruppe102.svg|thumb|200px|Bild 4]]
|}

[[Bild:KarnaughDiagramme.svg|thumb|right|150px|Beispiele für Zusammenfassungen]]
* Bild 3: Verdeutlicht die logischen Werte der 16 Felder; wenn man aus einer Wahrheitstabelle zeilenweise die DNF in das KV-Diagramm überträgt, dann erfolgt die Eintragung in der Reihenfolge der roten Zahlen
* Bild 4: Die roten Zahlen erleichtern die zeilenweise Zuordnung der Wahrheitstabelle zu den einzelnen Feldern; die Reihenfolge hängt von der konkreten Beschriftung des KV-Diagramms ab; die Nummerierung stellt eine Arbeitserleichterung bei umfangreicher Verwendung von KV-Diagrammen dar


Dabei wird jedem Feld ihre Wertigkeit zugeordnet. Bei 4 Signalen sind dies 16 Einträge:

0000 =  0,
0001 =  1,
0010 =  2,
…,
1110 = 14,
1111 = 15

Auf diese Weise kann das KV-Diagramm sehr schnell ausgefüllt werden. Es sind neben oben dargestellter Anordnungen aber auch Variationen der Anordnung der Eingangsvariablen ''A'', ''B'', ''C'' und ''D'' möglich. Dadurch ergeben sich andere Aufteilung der Wertigkeiten in der Matrix.

[[Karnaugh-Veitch-Diagramm|Zur Titelseite: Karnaugh-Veitch-Diagramm]] - zum nächsten Kapitel: [[Karnaugh-Veitch-Diagramm:_Beispiele (Teil_1)|Beispiele (Teil 1)]]