Karnaugh-Diagramme: Visuelle Vereinfachung boolescher Ausdrücke

TL;DR: Ein Karnaugh-Diagramm (KV-Diagramm) ordnet eine Wahrheitstabelle in einem Gray-codierten 2D-Raster an, in dem benachbarte Zellen sich in genau einer Variablen unterscheiden. Das Gruppieren benachbarter Einsen zu rechteckigen Zweierpotenzen liefert unmittelbar minimale disjunktive Normalformen – ganz ohne Algebra. KV-Diagramme minimieren Funktionen mit bis zu 4 Variablen zuverlässig; für 5–6 nutzt man Quine–McCluskey, darüber hinaus algorithmische Synthese im Stil von ESPRESSO.

Die algebraische Vereinfachung mit booleschen Gesetzen funktioniert, hängt aber davon ab, das richtige Faktorisieren zum richtigen Zeitpunkt zu erkennen. Eine verpasste Gelegenheit, und man landet bei einem suboptimalen Ergebnis. Für Ausdrücke mit vier oder mehr Variablen explodiert die Zahl möglicher Umformungen.

Das Karnaugh-Diagramm (KV-Diagramm) löst dieses Problem, indem es die algebraische Vereinfachung in visuelle Mustererkennung verwandelt. Entwickelt 1953 vom Bell-Labs-Physiker Maurice Karnaugh, ordnet es eine Wahrheitstabelle in einem zweidimensionalen Raster an, in dem benachbarte Zellen sich in genau einer Variablen unterscheiden. Das Gruppieren benachbarter Einsen auf dem Raster liefert unmittelbar minimale disjunktive Normalformen – keine algebraische Umformung erforderlich.

Bauteildiagramm AND-Gatter

Die visuelle Wahrheitstabelle: Was ist ein KV-Diagramm?

Im Kern ist ein Karnaugh-Diagramm eine getarnte Wahrheitstabelle. Während eine Wahrheitstabelle Ein- und Ausgänge linear, vertikal auflistet, ordnet das KV-Diagramm sie in einem zweidimensionalen Raster an. Das ist nicht bloß Optik. Das Geniale am KV-Diagramm liegt in der spezifischen Anordnung der Zellen.

In einer normalen Wahrheitstabelle folgen die Zeilen einer binären Zählung (00, 01, 10, 11). In einem KV-Diagramm folgen Zeilen und Spalten einer Folge, die als Gray-Code bekannt ist. In einer Gray-Code-Folge unterscheiden sich benachbarte Zahlen – ganz gleich, ob horizontal oder vertikal – in nur einem einzigen Bit. Diese Eigenschaft, die logische Nachbarschaft, ist der Motor der Vereinfachung. Wenn Sie benachbarte Zellen mit ‚1’ gruppieren, identifizieren Sie visuell jene Variablen, die wechseln (und damit das Ergebnis nicht beeinflussen) und eliminieren sie, sodass ein minimaler boolescher Term übrigbleibt.

Bevor wir uns den komplexen 4-Variablen-Diagrammen aus modernem ALU-Entwurf zuwenden, betrachten wir das grundlegende 2-Variablen-Diagramm für die Eingänge $A$ und $B$ . Es besteht aus $2^2 = 4$ Zellen, die die vier möglichen Minterme repräsentieren.

	$B=0$ ( $\overline{B}$ )	$B=1$ ( $B$ )
$A=0$ ( $\overline{A}$ )	$m_0$ ( $\overline{A}\overline{B}$ )	$m_1$ ( $\overline{A}B$ )
$A=1$ ( $A$ )	$m_2$ ( $A\overline{B}$ )	$m_3$ ( $AB$ )

Beachten Sie die Nachbarschaft: Beim Wechsel von $m_0$ zu $m_1$ ändert sich nur die Variable $B$ . Beim Wechsel von $m_1$ zu $m_3$ ändert sich nur die Variable $A$ . Diese physische Nähe auf dem Raster steht für eine logische Beziehung, die wir nutzen, um die Gatterzahl zu reduzieren.

Grundlegende Logik in Aktion sehen

Die Kunst des Gruppierens: Vom Diagramm zur minimalen Logik

Das Ziel eines KV-Diagramms ist es, alle Einsen mit möglichst großen rechteckigen Gruppen abzudecken. Allerdings gibt es einen Haken: Die Zellenanzahl jeder Gruppe muss eine Zweierpotenz sein (1, 2, 4, 8, 16 usw.). Jede Gruppe, die Sie einzeichnen, entspricht einem vereinfachten Produktterm. Ihr endgültiger optimierter Ausdruck ist schlicht die „Summe der Produkte” (ODER-Verknüpfung der Ergebnisse dieser Gruppen).

Die Regeln zum Gruppieren sind streng, aber überschaubar. Wer sie mechanisch befolgt, erhält ein garantiert minimales Ergebnis.

Jede ‚1’ abdecken: Jede ‚1’ im Diagramm muss zu mindestens einer Gruppe gehören. Keine ‚1’ darf ohne Gruppe bleiben.
Nur Zweierpotenzen: Gruppen müssen genau $2^k$ Zellen enthalten: 1, 2, 4, 8 oder 16. Sie können keine Gruppe von 3, 5 oder 6 bilden. Eine Region mit sechs Einsen wird durch überlappende Gruppen von 4 und 2 abgedeckt.
Gruppengröße maximieren: Größere Gruppen eliminieren mehr Variablen. Eine Gruppe von 2 eliminiert 1 Variable; eine von 4 eliminiert 2; eine von 8 eliminiert 3. Suchen Sie immer zuerst nach der größtmöglichen Gruppe.
Überlappen ist erlaubt: Eine einzelne ‚1’ darf zu mehreren Gruppen gehören. Nutzen Sie Überlappungen aktiv, um größere Gruppen zu bilden.
Nur rechteckige Form: Gruppen müssen Rechtecke (auch Quadrate) bilden. L-Formen, T-Formen und Diagonalen sind ungültig.
Das Diagramm wickelt sich um sich selbst: Die linke Spalte ist zur rechten Spalte benachbart. Die obere Zeile ist zur unteren benachbart. Stellen Sie sich das Diagramm als Torus vor – die vier Ecken sind wechselseitig benachbart.

Vertiefung: Das 4-Variablen-KV-Diagramm

Schauen wir uns ein praxisnahes Szenario an. Angenommen, wir entwerfen ein bestimmtes Logikstück für eine CONTROL_UNIT, das ein Signal feuern muss, wenn ein 4-Bit-Eingang bestimmte Bedingungen erfüllt. Unsere Funktion ist $F(A,B,C,D) = \Sigma m(0, 2, 5, 7, 8, 10, 13, 15)$ .

Die $\Sigma m$ -Notation ist eine Kurzschreibweise für „der Ausgang ist HIGH, wenn der binäre Eingang einem dieser Dezimalwerte entspricht”. Zunächst füllen wir unser Raster mit 16 Zellen.

	$CD=00$	$CD=01$	$CD=11$	$CD=10$
$AB=00$	1 ( $m_0$ )	0	0	1 ( $m_2$ )
$AB=01$	0	1 ( $m_5$ )	1 ( $m_7$ )	0
$AB=11$	0	1 ( $m_{13}$ )	1 ( $m_{15}$ )	0
$AB=10$	1 ( $m_8$ )	0	0	1 ( $m_{10}$ )

Nun suchen wir nach Mustern.

Gruppe 1: Die vier Ecken

Sehen Sie sich die Einsen bei $m_0, m_2, m_8$ und $m_{10}$ an. Weil sich das Diagramm sowohl horizontal als auch vertikal umwickelt, sind diese vier Ecken tatsächlich benachbart! Sie bilden eine einzige Gruppe von vier.

Variable A: Wechselt von 0 zu 1. (Verwerfen)
Variable B: Bleibt 0. (Beibehalten als $\overline{B}$ )
Variable C: Wechselt von 0 zu 1. (Verwerfen)
Variable D: Bleibt 0. (Beibehalten als $\overline{D}$ )
Ergebnis: $\overline{B}\overline{D}$

Gruppe 2: Der Mittelblock

Wir haben ein perfektes 2×2-Quadrat in der Mitte bei $m_5, m_7, m_{13}$ und $m_{15}$ .

Variable A: Wechselt von 0 zu 1. (Verwerfen)
Variable B: Bleibt 1. (Beibehalten als $B$ )
Variable C: Wechselt von 0 zu 1. (Verwerfen)
Variable D: Bleibt 1. (Beibehalten als $D$ )
Ergebnis: $BD$

Alle Einsen sind abgedeckt. Unser endgültiger vereinfachter Ausdruck lautet:

F = \overline{B}\overline{D} + BD

Dies ist die boolesche Definition eines XNOR-Gatters – ein Wirrwarr aus acht 4-Eingang-AND-Gattern schmilzt auf ein einziges Bauteil zusammen.

Bauteildiagramm XNOR-Gatter

Die vereinfachte XNOR-Schaltung erkunden

Häufige Falle: Warum Gray-Code unverzichtbar ist

Ein häufiger Fehler ist, KV-Diagramme in der gewöhnlichen Binärreihenfolge zu zeichnen – 00, 01, 10, 11. Tun Sie das nicht.

Mit Standard-Binär brechen Sie das Prinzip der Nachbarschaft. Betrachten Sie den Sprung von 01 nach 10. Beide Bits wechseln ( $0 \to 1$ und $1 \to 0$ ). Liegen in diesen beiden benachbarten Zellen Einsen, lassen sie sich nicht vereinfachen, weil mehr als eine Variable wechselt. Die Gray-Code-Folge (00, 01, 11, 10) stellt sicher, dass jeder Schritt im Diagramm genau einer Variablenänderung entspricht. Das ist die „Magie”, die die visuelle Mathematik funktionieren lässt. Ohne Gray-Code ist das KV-Diagramm nur eine verwirrende Tabelle; mit Gray-Code ist es ein Rechenwerkzeug.

Verifikation mit dem OSCILLOSCOPE_8CH

Einer der befriedigendsten Momente im digitalen Entwurf ist der Nachweis, dass Ihre „kleine” Schaltung exakt dasselbe tut wie die „große”. In digisim.io lässt sich das in Echtzeit erleben.

Brute-Force bauen: Verwenden Sie acht AND-Gatter und ein großes OR-Gatter, um die ursprünglichen Minterme abzubilden.
Optimierte Variante bauen: Setzen Sie ein einzelnes XNOR-Gatter (oder das Äquivalent aus zwei ANDs und einem OR) darunter.
Eingänge synchronisieren: Verbinden Sie dieselben vier INPUT_SWITCH-Bauteile mit beiden Schaltungen.
Analyse: Verbinden Sie den Ausgang der Brute-Force-Schaltung mit Kanal 1 eines OSCILLOSCOPE_8CH und den optimierten Ausgang mit Kanal 2.

Während Sie die Schalter durch alle 16 Kombinationen schalten, sind die Wellenformen auf dem OSCILLOSCOPE_8CH identisch. Würden Sie jedoch die Laufzeitverzögerung ( $t_{pd}$ ) betrachten, sähen Sie, dass die optimierte Schaltung deutlich schneller reagiert. In einem Hochgeschwindigkeits-CPU-Projekt sind diese Nanosekunden der Unterschied zwischen einem 1-MHz- und einem 10-MHz-Takt.

Praxisanwendungen: Jenseits des Klassenraums

KV-Diagramme dienen nicht nur zum Bestehen von Klausuren; sie sind das Brot und Butter der Hardwarebeschreibung.

1. ALU-Steuerlogik

In einer typischen 8-Bit-CPU muss die ALU (Arithmetisch-Logische Einheit) anhand eines „Opcodes” wissen, ob sie addieren, subtrahieren oder eine bitweise AND-Operation ausführen soll. Dieser Opcode kann 4 Bit breit sein. Entwicklerinnen und Entwickler nutzen KV-Diagramme, um die Decoder-Logik zu entwerfen, die diesen 4-Bit-Opcode entgegennimmt und die bestimmten Steuerleitungen für den ADDER_8BIT oder den COMPARATOR_8BIT aktiviert. Durch Minimierung dieser Logik verringern sie die „Instruktionsdecodierzeit”, die einen entscheidenden Engpass für die CPU-Leistung darstellt.

2. Endliche Automaten (FSMs)

Ob Ampelsteuerung oder komplexer Protokoll-Handler – FSMs setzen auf „Folgezustandslogik”. Diese Logik betrachtet den aktuellen Zustand (in einem REGISTER abgelegt) und die aktuellen Eingaben, um über den nächsten Zustand zu entscheiden. Diese Wahrheitstabellen werden rasch riesig. KV-Diagramme erlauben es, die effizienteste Weiterleitung dieser Signale zu finden – häufig werden dabei Dutzende Gatter in der Endimplementierung eingespart.

Bauteildiagramm ALU

Häufige Fehler

Folgende Fehler gilt es zu vermeiden:

Offene Eingänge: Jeder Eingang jedes AND-Gatters muss verbunden sein. Ein offener Eingang verhält sich im Simulator vielleicht vorhersagbar, in echter Hardware fängt er Rauschen ein.
Den Umlauf vergessen: Prüfen Sie Ecken und Ränder. Einige der elegantesten Vereinfachungen entstehen aus dem Gruppieren der vier Ecken oder der obersten und untersten Zeile.
Überflüssige Gruppen: Sobald alle Einsen abgedeckt sind, hören Sie auf. Eine zusätzliche Gruppe „weil sie hübsch aussieht” bringt unnötige Gatter in die Schaltung und unterläuft den Zweck des KV-Diagramms.

Die Stärke der Don’t-Care-Bedingungen

In vielen realen Entwürfen können bestimmte Eingangskombinationen niemals auftreten. Ein BCD-System (Binary-Coded Decimal) etwa codiert die Ziffern 0–9 mit 4 Bit, sodass die Kombinationen 1010 bis 1111 nie vorkommen. Im KV-Diagramm markieren Sie diese unmöglichen Eingänge mit einem $X$ (don’t care) anstelle von 0 oder 1.

Der Kern: Sie dürfen jedes $X$ entweder als 0 oder als 1 behandeln – je nachdem, was Ihnen hilft, eine größere Gruppe zu bilden. Da diese Eingänge in der Praxis nie auftreten, spielt es keine Rolle, was die Schaltung dabei ausgibt.

Beispiel: Angenommen, eine 4-Variablen-Funktion hat Einsen in den Zellen 0, 2, 8, 10 und Don’t-Cares in den Zellen 1 und 3. Ohne die Don’t-Cares gruppieren sich die vier Einsen (Ecken) zu $\overline{B}\overline{D}$ . Behandeln Sie die Zellen 1 und 3 jedoch als Einsen, können Sie in der oberen Zeile eine größere Vierergruppe ( $\overline{A}\overline{B}$ ) bilden und zusätzlich die ursprüngliche Eckgruppe behalten – möglicherweise ergibt sich ein insgesamt einfacherer Ausdruck. Don’t-Care-Bedingungen reduzieren in realen Entwürfen die endgültige Gatterzahl häufig um 20–30 %.

Den nächsten Schritt gehen

Dieser Beitrag ist Teil der Reihe „Grundlagen der booleschen Algebra”. Verwandte Lektüre:

Boolesche Algebra meistern – die algebraischen Identitäten hinter der KV-Gruppierung.
Disjunktive Normalform (SOP) meistern – die kanonische Form, die KV-Diagramme erzeugen.
Jenseits der SOP: Konjunktive Normalform (POS) – die duale Minimierung.
Die Sätze von De Morgan – die Umformungsregeln zwischen den Formen.

Das Karnaugh-Diagramm verwandelt eine komplexe algebraische Aufgabe in ein visuelles Rätsel. Für Funktionen mit bis zu 4 Variablen liefert es zuverlässig minimale SOP- (oder POS-)Ausdrücke. Bei 5–6 Variablen sind KV-Diagramme noch nutzbar, aber unhandlich; algorithmische Verfahren wie Quine–McCluskey übernehmen dann.

Bauen Sie die Brute-Force- und die optimierte Schaltung aus dem Beispiel und beobachten Sie, wie sich die Wellenformen auf dem Oszilloskop decken. Starten Sie eine neue Schaltung zur Verifikation.