Karnaugh-Veitch-Diagramm
Das Karnaugh-Veitch-Diagramm, kurz KV-Diagramm (engl. Karnaugh map), dient der übersichtlichen Darstellung und Vereinfachung logischer Funktionen. Es wurde etwa zeitgleich von Maurice Karnaugh und Edward W. Veitch entwickelt.
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 müssen. Mit Hilfe der Wahrheitstabelle der zu optimierenden Funktion wird in die einzelnen Felder eine 1 eingetragen, wenn eine Vollkonjunktion vorliegt, andernfalls eine 0. 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
- Man versucht, möglichst viele horizontal und vertikal benachbarte Felder, die eine 1 enthalten (Vollkonjunktionen) zu zusammenhängenden 2er-, 4er, 8er oder 16er-Blöcken zusammen zu fassen. Ein Block kann über den rechten bzw. unteren Rand des Diagramms fortgesetzt werden. Die Nachbarn sind dann in der linken Spalte bzw. oberen Reihe zu finden.
- Variablen innerhalb eines Blockes, die in negierter und nicht negierter Form auftreten, werden weggelassen.
- Die verbleibenden Variablen werden UND-verknüpft
- Diese UND-Verknüpfungen werden durch ODER-Verknüpfungen zusammen gefasst und ergeben die minimierte Funktion
Maxterm-Methode
- Man versucht, möglichst viele horizontal und vertikal benachbarte Felder, die eine 0 enthalten (Volldisjunktionen) zu zusammenhängenden 2er-, 4er, 8er oder 16er-Blöcken zusammen zu fassen. Ein Block kann über den rechten bzw. unteren Rand des Diagramms fortgesetzt werden. Die Nachbarn sind dann in der linken Spalte bzw. oberen Reihe zu finden.
- Variablen innerhalb eines Blockes, die in negierter und nicht negierter Form auftreten, werden weggelassen.
- Die verbleibenden Variablen werden ODER-verknüpft
- Diese ODER-Verknüpfungen werden durch UND-Verknüpfungen zusammen gefasst und ergeben die minimierte Funktion
Don't-Care-Zustände
Häufig gibt es logische 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 KV-Diagramm ist ebenfalls nützlich, um Hazards festzustellen und zu eliminieren.
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):
| A | B | C | Lampe l | |
| 0 | 0 | 0 | 1 | |
| 0 | 0 | 1 | 1 | |
| 0 | 1 | 0 | 1 | |
| 0 | 1 | 1 | 1 | |
| 1 | 0 | 0 | 0 | |
| 1 | 0 | 1 | 0 | |
| 1 | 1 | 0 | 1 | |
| 1 | 1 | 1 | 1 |
Die DNF lautet also:
Das dazugehörige KV-Diagramm sieht nun so aus:
Nach der Minterm-Methode kann man im Diagramm nun zwei Viererblocks 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
KV-Tafeln für 2 und 4 Variablen
Datei:KV-Diagramm AB.png Datei:KV-Diagramm ABCD.png
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.