Mit Google fortfahren
Karnaugh-Veitch-Diagramm einfach erklärt
Ein Karnaugh-Veitch-Diagramm, kurz KV-Diagramm, ordnet die Werte einer Wahrheitstabelle so an, dass du benachbarte Einsen oder Nullen zusammenfassen kannst. Dadurch verschwinden veränderliche Variablen aus dem booleschen Ausdruck.
Du lernst, ein KV-Diagramm auszufüllen, gültige Gruppen zu erkennen und daraus eine vereinfachte Funktion abzulesen.
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Warum verschwinden Variablen?
Zwei benachbarte Felder unterscheiden sich in genau einer Variable. Ist die Funktion in beiden Feldern 1, spielt diese wechselnde Variable für das Ergebnis keine Rolle mehr.
Die beiden Terme $A\land B$ und $A\land\neg B$ unterscheiden sich nur in $B$:
$$(A\land B)\lor(A\land\neg B)=A$$
$A$ bleibt immer wahr. Ob $B$ wahr oder falsch ist, ändert das Ergebnis nicht. Deshalb entfällt $B$.
Eine Gruppe mit $2^k$ Feldern entfernt genau $k$ Variablen. In einem Diagramm mit $n$ Variablen bleiben also $n-k$ Literale übrig.
| Gruppengröße | Entfallende Variablen |
|---|---|
| 1 | 0 |
| 2 | 1 |
| 4 | 2 |
| 8 | 3 |
Wie ist ein KV-Diagramm aufgebaut?
Bei $n$ Eingangsvariablen besitzt das Diagramm $2^n$ Felder. Vier Variablen ergeben daher $2^4=16$ Felder.
Jedes Feld steht für genau eine Eingabekombination. Die Zeilen und Spalten folgen einer Gray-Code-Reihenfolge, zum Beispiel:
$00, 01, 11, 10$
Dadurch unterscheiden sich benachbarte Beschriftungen stets in genau einem Bit. Auch der erste und der letzte Eintrag dieser Reihenfolge sind benachbart.
Gegenüberliegende Ränder des Diagramms berühren sich gedanklich:
- links ist mit rechts benachbart;
- oben ist mit unten benachbart;
- bei vier Variablen bilden dadurch auch die vier Eckfelder gemeinsam eine gültige Vierergruppe;
- diagonal angrenzende Felder sind nicht benachbart.
Wie überträgst du eine Wahrheitstabelle?
Gehe für eine disjunktive Normalform, kurz DNF, so vor:
- Lege für jede Eingabekombination das zugehörige KV-Feld fest.
- Trage dort eine 1 ein, wenn die Funktion den Wert 1 besitzt.
- Trage sonst eine 0 ein.
- Prüfe die Zuordnung nochmals anhand der Gray-Code-Beschriftung.
Ein Minterm beschreibt genau eine Eingabekombination, für die die Funktion 1 ist. In seiner vollständigen Form enthält er jede Eingangsvariable entweder negiert oder nicht negiert.
Für drei Variablen $x_2,x_1,x_0$ verwenden wir die Zeilenvariable $x_2$ und die Spaltenfolge $x_1x_0=00,01,11,10$.
Die Funktion sei bei den binären Eingaben mit den Indizes $0,1,4,5,6,7$ gleich 1. Der Index ist dabei der Binärwert von $x_2x_1x_0$.
| $x_2$ / $x_1x_0$ | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 |
Beispielsweise gehört der Index 6 zur Eingabe $110$. Er steht deshalb in der Zeile $x_2=1$ und in der Spalte $x_1x_0=10$.
Welche Gruppen sind gültig?
Bei der Minterm-Methode überdeckst du alle Einsen mit möglichst großen rechteckigen Gruppen.
Eine gültige Gruppe erfüllt diese Regeln:
- Sie enthält $1,2,4,8,\ldots$ Felder.
- Ihre Höhe und Breite sind Zweierpotenzen.
- Sie enthält keine 0.
- Ihre Felder sind waagerecht oder senkrecht benachbart, gegebenenfalls über einen Rand hinweg.
- Gruppen dürfen sich überlappen; eine 1 darf mehrfach verwendet werden.
- Alle Einsen müssen am Ende abgedeckt sein.
- Eine Gruppe soll nicht vollständig in einer größeren gültigen Gruppe liegen.
Ein Dreierblock ist nicht erlaubt. Drei nebeneinanderliegende Einsen kannst du stattdessen mit zwei überlappenden Zweiergruppen abdecken.
Suche zuerst die größten Gruppen. Große Gruppen liefern Ausdrücke mit weniger Literalen. Danach deckst du noch unberücksichtigte Einsen mit möglichst wenigen weiteren Gruppen ab.
Wie liest du den vereinfachten Ausdruck ab?
Betrachte jede gewählte Gruppe einzeln:
- Prüfe für jede Variable, ob ihr Wert innerhalb der gesamten Gruppe konstant bleibt.
- Streiche jede Variable, die zwischen 0 und 1 wechselt.
- Schreibe konstante Variablen mit Wert 1 nicht negiert auf.
- Schreibe konstante Variablen mit Wert 0 negiert auf.
- Verbinde die Literale einer Gruppe mit UND.
- Verbinde die Terme aller Gruppen mit ODER.
Wir verwenden erneut das Diagramm mit Einsen bei $0,1,4,5,6,7$.
Die gesamte untere Zeile ist eine Vierergruppe. Dort gilt stets $x_2=1$, während $x_1$ und $x_0$ wechseln. Ihr Term ist daher $x_2$.
Die ersten beiden Spalten bilden über beide Zeilen hinweg eine weitere Vierergruppe. Dort gilt stets $x_1=0$, während $x_2$ und $x_0$ wechseln. Ihr Term ist daher $\neg x_1$.
Die vereinfachte Funktion lautet:
$$F=\neg x_1\lor x_2$$
Kontrolle: Für $x_2=1$ ist die ganze untere Zeile 1. Für $x_2=0$ wird die Funktion nur dann 1, wenn $x_1=0$ ist. Das stimmt mit dem Diagramm überein.
Was ändert sich bei Nullen und Don’t-Cares?
Sind nur wenige Nullen vorhanden, kannst du statt der Einsen die Nullen gruppieren. Jeder Nullblock liefert einen ODER-Term; die Blockterme werden anschließend mit UND verbunden. Das Ergebnis ist eine vereinfachte konjunktive Normalform, kurz KNF.
Beim Ablesen eines Nullblocks gilt gegenüber der Einsgruppen-Methode:
- Eine konstant 0 gesetzte Variable erscheint nicht negiert.
- Eine konstant 1 gesetzte Variable erscheint negiert.
- Innerhalb des Blocks wechselnde Variablen entfallen.
Ein Don’t-Care wird mit $X$ markiert. Für diese Eingabekombination ist der Ausgang nicht festgelegt. Du darfst das Feld wie eine 0 oder eine 1 verwenden, wenn dadurch eine größere Gruppe entsteht. Bringt es keinen Vorteil, lässt du es unbenutzt. Ein Don’t-Care muss nicht abgedeckt werden.
Für jeden Ausgang einer Schaltung brauchst du eine eigene boolesche Funktion und damit ein eigenes KV-Diagramm. Das Verfahren ist besonders übersichtlich bis vier Variablen. Bei mehr Variablen werden Nachbarschaften und gültige Gruppen deutlich schwerer erkennbar.
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- Karnaugh-Veitch-Diagramm
- Wahrheitstabelle in $2^n$ Gray-Code-Felder übertragen
- Einsen für eine vereinfachte DNF gruppieren
- Nullen für eine vereinfachte KNF gruppieren
- Gruppen nur in Zweierpotenzgrößen bilden
- Gegenüberliegende Ränder als benachbart behandeln
- Wechselnde Variablen aus dem Blockterm streichen
- Große Gruppen und wenige Terme anstreben
- Don’t-Cares nur bei einem Vereinfachungsvorteil nutzen
Abschluss-Check
Kannst du den Weg nun selbst beschreiben? Werte übertragen, große gültige Gruppen bilden, wechselnde Variablen streichen und die verbleibenden Blockterme verbinden.