Lernen › Thema 4

Karnaugh-Diagramme (KV-Diagramme) mit 2, 3 und 4 Variablen und Don't-Cares

7 Min. Lesezeit · bitGateLab-Team

Vereinfachen mit boolescher Algebra funktioniert, hängt aber davon ab, dass du „siehst“, welches Gesetz anzuwenden ist. Das Karnaugh-Diagramm macht aus dieser Suche eine visuelle Übung: Es ordnet die Wahrheitstabelle in einem Raster an, in dem sich benachbarte Felder in nur einer Variablen unterscheiden, und Vereinfachen heißt dann, Blöcke von Einsen einzukreisen. Hier lernst du, Diagramme für 2, 3 und 4 Variablen aufzustellen, richtig Blöcke zu bilden (auch über die Ränder, die „umlaufen“) und die Don't-Care-Bedingungen auszunutzen.

Die Idee: Nachbarfelder, eine Variable Unterschied

Das Nachbarschaftsgesetz besagt AB + AB = A: Zwei Terme, die sich in nur einer Variablen unterscheiden, verschmelzen, und diese Variable entfällt. Das Karnaugh-Diagramm ordnet die Minterme so an, dass jedes Paar von Feldern mit einer gemeinsamen Seite diese Bedingung erfüllt. Dazu folgen die Zeilen- und Spaltenköpfe nicht der binären Reihenfolge 00, 01, 10, 11, sondern dem Gray-Code: 00, 01, 11, 10. Zwischen zwei aufeinanderfolgenden Werten ändert sich nur ein Bit, und ebenso zwischen dem letzten und dem ersten (10 und 00). Deshalb verhält sich das Diagramm so, als wären seine gegenüberliegenden Ränder zusammengeklebt.

Diagramme für 2 und 3 Variablen

Das Diagramm für zwei Variablen hat 4 Felder: A in den Zeilen und B in den Spalten. Das für drei Variablen hat 8 Felder: A in den Zeilen und BC in den Spalten, in Gray-Reihenfolge. Die Nummer in jedem Feld gibt den zugehörigen Minterm an:

Beachte, dass m3 und m2 in dieser Reihenfolge stehen: Das ist die Wirkung des Gray-Codes und die Ursache vieler Fehler beim Ausfüllen des Diagramms von Hand.

Regeln der Blockbildung

• Blöcke dürfen nur Einsen enthalten (oder X, wie du weiter unten siehst), niemals Nullen.
• Die Größe jedes Blocks muss eine Potenz von 2 sein: 1, 2, 4, 8 oder 16 Felder.
• Blöcke sind Rechtecke aus benachbarten Feldern, wobei auch die Nachbarschaft über die Ränder hinweg zählt. Diagonalen zählen nicht.
• Mache jeden Block so groß wie möglich: Ein Block aus 2^k Feldern eliminiert k Variablen.
• Verwende so wenige Blöcke wie möglich, um alle Einsen zu überdecken. Blöcke dürfen sich überlappen.

Um einen Block abzulesen, sieh dir jede Variable an: Behält sie in allen Feldern des Blocks denselben Wert, erscheint sie im Term (ohne Strich, wenn sie 1 ist, mit Strich, wenn sie 0 ist); wechselt sie, entfällt sie.

Diagramm für 4 Variablen und Nachbarschaft über die Ränder

Bei vier Variablen hat das Diagramm 16 Felder: AB in den Zeilen und CD in den Spalten, beide in Gray-Reihenfolge.

Die linke Spalte ist Nachbarin der rechten, und die oberste Zeile ist Nachbarin der untersten. Folglich bilden die vier Ecken (m0, m2, m8, m10) einen gültigen Block aus 4 Feldern: In allen gilt B = 0 und D = 0, sie werden also als BD abgelesen.

Don't-Care-Bedingungen (X)

Manchmal treten bestimmte Eingangskombinationen nie auf, oder ihr Ausgangswert hat keine Folgen. Bei einer BCD-Ziffer zum Beispiel gibt es die Codes 1010 bis 1111 nicht. In diese Zeilen schreibt man ein X (englisch don't care, „egal“) und notiert sie gesondert als d(...). Beim Bilden der Blöcke darf jedes X als 1 genommen werden, wenn es dir zu einem größeren Block verhilft, oder ignoriert werden, wenn nicht. Ein X muss nie überdeckt werden.

Häufige Fehler

• Die Köpfe binär (00, 01, 10, 11) statt im Gray-Code zu ordnen. Dann unterscheiden sich Nachbarfelder nicht mehr in nur einer Variablen, und die Blöcke werden falsch.
• Blöcke aus 3 oder 6 Feldern zu bilden. Zulässig sind nur Potenzen von 2.
• Die Nachbarschaft über die Ränder und die vier Ecken zu vergessen, wodurch die Blöcke kleiner bleiben als nötig.
• Einen Block hinzuzufügen, dessen Felder bereits alle von anderen überdeckt sind. Er ist überflüssig und kostet zusätzliche Gatter.
• Sich zu zwingen, die X zu überdecken. Man verwendet sie nur, wenn sie einen Block vergrößern.

Probiere es im Simulator aus

Das Modul für Karnaugh-Diagramme ordnet die Funktion in Gray-Reihenfolge an, markiert die Blöcke und schreibt den minimalen Ausdruck hin. So kannst du deine Blockbildung mit dem Vorschlag des Werkzeugs vergleichen.

1. Lege eine Funktion von vier Variablen an und trage die Einsen aus Beispiel 2 ein.
2. Bilde die Blöcke zuerst selbst auf Papier und schreibe dein Ergebnis auf.
3. Sieh dir die Blöcke an, die das Diagramm markiert, und den resultierenden Ausdruck; weicht er von deinem ab, prüfe, welcher Block nicht maximal war.
4. Gib Beispiel 3 ein, markiere die Felder 0, 2 und 5 als X und beobachte, wie sich die Vereinfachung ändert, wenn du diese X entfernst.
5. Wandle das Ergebnis in eine Schaltung um und schalte die Eingänge durch, um zu bestätigen, dass sie mit der Tabelle übereinstimmt.

Übungen

1. Vereinfache F(A, B, C) = Σm(0, 2, 4, 6).
   Lösung

   Die Spalten BC = 00 und BC = 10 sind über den Rand benachbart und voll. In allen vier Feldern gilt C = 0: F = C.

2. Vereinfache F(A, B, C, D) = Σm(0, 2, 5, 7, 8, 10, 13, 15).
   Lösung

   Ecken: BD. Mittelblock m5, m7, m13, m15: BD. F = BD + BD, also das XNOR von B und D.

3. Vereinfache F(A, B, C, D) = Σm(4, 5, 6, 7, 12, 13, 14, 15).
   Lösung

   Die Zeilen AB = 01 und AB = 11 bilden einen 8er-Block; nur B bleibt durchgehend 1. F = B.

4. Eine BCD-Ziffer (A ist das höchstwertige Bit) soll einen Ausgang einschalten, wenn sie 5 oder größer ist. Vereinfache F = Σm(5, 6, 7, 8, 9) + d(10, 11, 12, 13, 14, 15).
   Lösung

   Mit den X bilden die Zeilen AB = 11 und AB = 10 einen 8er-Block: A. Der Block m5, m7, m13, m15 ergibt BD, und der Block m6, m7, m14, m15 ergibt BC. F = A + BD + BC = A + B(C + D).

Bei mehr als vier oder fünf Variablen wird das Diagramm schwer lesbar; für solche Fälle gibt es ein tabellarisches Verfahren, das Quine-McCluskey-Verfahren.