Eine boolesche Funktion in einen möglichst kurzen Schaltausdruck zu verwandeln, ist eine Kernaufgabe der Digitaltechnik – jedes eingesparte Gatter bedeutet weniger Chipfläche, weniger Stromverbrauch und kürzere Signalwege. Das Karnaugh-Veitch-Diagramm (kurz KV-Diagramm oder im Englischen Karnaugh-Map) ist die bekannteste grafische Methode, um genau das per Hand zu erreichen. Maurice Karnaugh stellte sie 1953 vor.
Von der Wahrheitstabelle zum Diagramm
Ausgangspunkt ist immer die Wahrheitstabelle: Sie listet für jede Kombination der Eingangsvariablen den gewünschten Ausgangswert (0 oder 1) auf. Bei n Variablen hat sie 2n Zeilen. Die Zeilen, in denen der Ausgang 1 ist, heißen Minterme.
Das KV-Diagramm ordnet dieselben 2n Felder in einem rechteckigen Raster an – aber mit einem entscheidenden Trick. Mit dem Karnaugh-Map-Tool gibst du einfach die Wahrheitstabelle ein, schaltest die Minterme an und siehst sofort, wie sich die Felder zu Blöcken zusammenfassen lassen.
Der Gray-Code: warum die Anordnung so wichtig ist
Die Zeilen und Spalten eines KV-Diagramms sind nicht binär aufsteigend beschriftet (00, 01, 10, 11), sondern im Gray-Code (00, 01, 11, 10). Beim Gray-Code unterscheiden sich zwei benachbarte Codes in genau einem Bit. Das ist der Schlüssel zur Methode:
Zwei benachbarte Felder unterscheiden sich dadurch in nur einer Variablen. Sind beide eine 1, kann diese eine Variable herausgekürzt werden – nach dem Gesetz A·B + A·B' = A. Genau diese Nachbarschaft macht die Vereinfachung visuell sichtbar, statt sie algebraisch durchrechnen zu müssen. Wichtig: Auch die Ränder sind benachbart – das Diagramm ist gedanklich zu einem Torus aufgerollt, links/rechts und oben/unten "wrappen" herum.
Blöcke bilden: die eigentliche Minimierung
Jetzt kommt der Kern. Du fasst benachbarte Einsen zu möglichst großen rechteckigen Blöcken zusammen. Dabei gelten feste Regeln:
- Ein Block darf nur Einsen enthalten (bei der disjunktiven Minimierung).
- Die Größe eines Blocks ist immer eine Zweierpotenz: 1, 2, 4, 8, 16 Felder.
- Blöcke sind so groß wie möglich zu wählen – je größer der Block, desto mehr Variablen fallen weg.
- Blöcke dürfen sich überlappen, wenn das einen Block vergrößert.
- Es müssen alle Einsen von mindestens einem Block abgedeckt sein.
Ein Block aus zwei Feldern eliminiert eine Variable, ein Block aus vier Feldern zwei Variablen, einer aus acht Feldern drei – jede Verdopplung der Blockgröße spart eine Variable. Aus jedem Block wird genau ein UND-Term gebildet, der nur die Variablen enthält, die innerhalb des Blocks konstant bleiben.
Das Ergebnis: minimale disjunktive Normalform
Verknüpfst du alle Blockterme mit ODER, erhältst du die minimale disjunktive Normalform (DNF) – eine Summe von Produkten (sum of products), die die Funktion mit möglichst wenigen Termen und Literalen beschreibt. Der Karnaugh-Map-Editor übernimmt das Blockbilden und die Minimierung für dich, sodass du das Ergebnis direkt mit deiner Handrechnung vergleichen kannst.
Don't-Cares: Freiheitsgrade clever nutzen
In der Praxis gibt es oft Eingabekombinationen, die nie auftreten – etwa bei einem BCD-Code die Werte 10 bis 15. Ihr Ausgangswert ist egal und wird als Don't-Care (X) markiert. Beim Blockbilden darfst du ein X frei als 0 oder 1 interpretieren – je nachdem, was die Blöcke größer macht. Don't-Cares sind ein mächtiges Werkzeug, um den Ausdruck noch weiter zu verkürzen.
Grenzen und Alternativen
So elegant das KV-Diagramm ist – ab etwa fünf bis sechs Variablen wird das zweidimensionale Raster unübersichtlich. Für größere Funktionen nutzt man das algorithmische Quine-McCluskey-Verfahren oder direkt computergestützte Logiksynthese, wie sie jeder moderne FPGA- und ASIC-Workflow einsetzt. Für den Lern- und Handbereich bis vier Variablen bleibt die Karnaugh-Map aber unschlagbar anschaulich.
Wofür du das brauchst
Karnaugh-Maps begegnen dir in der Digitaltechnik, beim Schaltungsentwurf, in Mikrocontroller-Logik und in jeder Prüfung zur technischen Informatik. Wer das Prinzip von Gray-Code und Blockbildung verstanden hat, minimiert Ausdrücke in Sekunden statt mit seitenlangen Algebra-Umformungen. Probier es mit deiner eigenen Wahrheitstabelle im Karnaugh-Map-Tool aus. Wer lieber mit Automaten und Mustern arbeitet, findet im Regex-Automat ein verwandtes Modellierungswerkzeug; weitere Helfer für Entwickler stehen unter kotsch.tech/webtools bereit.