Karnaugh-Veitch-Diagramm
aus Wikipedia, der freien Enzyklopädie
Das Karnaugh-Veitch-Diagramm (bzw. die Karnaugh-Tafel oder der Karnaugh-Plan), kurz KV-Diagramm oder K-Diagramm (engl. Karnaugh map), dient der übersichtlichen Darstellung und Vereinfachung Boolescher Funktionen - Umwandlung der disjunktiven Normalform in einen minimalen logischen Ausdruck. Es wurde 1952 von Edward W. Veitch entworfen und 1953 von Maurice Karnaugh zu seiner heutigen Form weiterentwickelt.
Inhaltsverzeichnis |
[Bearbeiten] Eigenschaften
Mittels eines KV-Diagramms lässt sich jede beliebige boolesche Funktion in eine disjunktive oder konjunktive Normalform (DNF/KNF) umwandeln. Der Vorteil gegenüber anderen Verfahren ist, dass der erzeugte Term (meist) minimal ist. Weitere Vereinfachung ist durch Anwenden des Distributivgesetzes (Ausklammern) möglich. Das entstehende Resultat ist in diesem Fall allerdings keine DNF bzw. KNF mehr. Das Umwandeln beginnt mit dem Erstellen einer Wahrheitstafel, die dann direkt in ein KV-Diagramm umgewandelt wird. Durch geschickte Wahl bestimmter Blöcke innerhalb des Diagramms entstehen die Terme der Normalform. Der Vorteil dieser Normalformen liegt darin, dass sie in Schaltungen ausschließlich durch die Bauteile AND, OR und NOT realisiert werden können.
[Bearbeiten] Wie füllt man ein KV-Diagramm aus?
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. 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 m 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 bis zu 5 Eingangsvariablen.
[Bearbeiten] Vereinfachung
Sind weniger Felder des KV-Diagramms mit 1 als mit 0 ausgefüllt, wählt man die Minterm-Methode, andernfalls die Maxterm-Methode.
[Bearbeiten] Minterm-Methode
- 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. Welche Blockgrößen erlaubt sind, hängt von der Anzahl der Variablen ab. Hier die Blockgrößen für zwei bis fünf Variablen:
- Zwei Variablen: 2 oder 4.
- 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 Zylinder verstanden werden. Die Felder ganz links und ganz rechts sind also benachbart. KV-Diagramme für vier Variablen müssen im Grunde als Kreisring ("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 die disjunktive Normalform.
[Bearbeiten] 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.
[Bearbeiten] 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 XOR verknüpft und ergeben eine minimierte Funktion...
[Bearbeiten] Veranschaulichung durch Hyper-Einheitswürfel
Boolesche Funktionen mit n Variablen lassen sich grafisch mittels Einheitswürfeln der Dimension n veranschaulichen. Würfel beliebiger Dimension bezeichnet man auch als Hyperwürfel. Da Karnaugh-Diagramme selbst eine spezielle Darstellungsform für Boolesche Funktionen sind, überrascht es nicht, dass sich zwischen Hyper-Einheitswürfeln und Karnaugh-Diagrammen ein anschaulicher Zusammenhang herstellen lässt. Und zwar entsprechen Karnaugh-Diagramme für n Variablen umkehrbar eindeutig den Hyper-Einheitswürfeln der Dimension n. Die Ecken-Koordinaten des Hyperwürfels entsprechen dabei den dualen Nummern der Felder im Karnaugh-Diagramm.
[Bearbeiten] 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 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.
[Bearbeiten] Beispiel
Zu einer Lampe führen drei Schalter A, B und C, die entweder an (1) oder aus (0) sind. Folgende Tabelle zeigt, bei welcher Kombination von Schaltern die Lampe leuchtet (1) oder dunkel bleibt (0):
| C | B | A | Lampe |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Die disjunktive Normalform lautet also: 
, da die Minterme nur des Urbilds 1 gebildet werden (analog werden Maxterme nur des Urbilds 0 gebildet).
Die enthaltenen Konjunktionsterme sind gerade die Minterme.
Das dazugehörige KV-Diagramm sieht nun so aus:
Nach der Minterm-Methode kann man im Diagramm nun zwei Viererblöcke bilden, die im einen Fall 
und im anderen Fall 
enthalten. Die optimierte Funktion lautet demnach: 
Das bedeutet, dass die Lampe l leuchtet, wenn der Schalter A ausgeschaltet oder der Schalter B eingeschaltet ist. Der Schalter C hat keine Wirkung.
Nach der Maxterm-Methode fasst man die beiden 0-Felder zu einem Zweierblock zusammen und erhält damit ohne weiteres
Ein KV-Diagramm ist ebenfalls nützlich, um Hazards festzustellen und zu eliminieren.
[Bearbeiten] KV-Tafeln für 2 und 4 Variablen
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:
| 7 | 3 | 2 | 6 |
| 15 | 11 | 10 | 14 |
| 13 | 9 | 8 | 12 |
| 5 | 1 | 0 | 4 |
Dabei wird jedem Feld ihre Wertigkeit zuordnet. 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.
[Bearbeiten] Siehe auch
Verfahren nach Quine und McCluskey
Pseudotetraden
Schaltalgebra
[Bearbeiten] Literatur
- Maurice Karnaugh: The Map Method for Synthesis of Combinational Logic Circuits, Transactions of the AIEE, Vol. 72, No. 9 (1953), 593—599.
- Edward W. Veitch: A chart method for symplifying truth functions, Mai 1952, Proc. Assoc. for Computing Machinery, Pittsburgh.
- Klaus Beuth: Digitaltechnik (Kapitel 5), 2001, Vogel Buchverlag, ISBN 3-8023-1755-6
[Bearbeiten] Weblinks
- Java-Applet zum KV-Diagramm von der Universität Karlsruhe
- Java-Applet zum KV-Diagramm von der Universität Erlangen-Nürnberg
- Kostenloses Lernprogramm. Lernziele: Aufstellen von Wahrheitstabellen und der disjunktiven Normalform (DNF), Vereinfachen von Schaltnetzen mit KV-Tafeln für 2 bis 5 Variable.
- Java-Applet zum KV-Diagramm mit Wertetabelle
- Herleitung einer Formel mittels KV-Diagramm zur Bestimmung, ob Rechtecke mit partiell gleichem Flächeninhalt überlappend angeordnet werden können, ein Artikel von Herbert Glarner [en]
