Karnaugh-Diagramm — Anleitung zur K-Map-Vereinfachung

Ein Karnaugh-Diagramm oder eine K-Map ist ein Raster, mit dem man einen booleschen Ausdruck vereinfachen kann, ohne so viel Algebra von Hand zu machen. Man trägt die Ausgabewerte aus einer Wahrheitstabelle in das Raster ein, gruppiert benachbarte $1$en und schreibt dann für jede Gruppe einen einfacheren Term.

Die Bedingung ist wichtig: K-Maps sind vor allem für kleine Funktionen praktisch, meist mit zwei, drei oder vier Variablen. Mit wachsender Variablenzahl wird das Diagramm schwerer lesbar, und andere Methoden sind meist besser.

Was ein Karnaugh-Diagramm zeigt

Eine K-Map enthält dieselben Informationen wie eine Wahrheitstabelle, ordnet die Zellen aber in Gray-Code-Reihenfolge statt in normaler Binärreihenfolge an. Diese Anordnung sorgt dafür, dass sich benachbarte Zellen in genau einer Variablen unterscheiden.

Genau dieser Unterschied in einer Variablen ist der entscheidende Punkt. Wenn zwei benachbarte Zellen beide $1$ sind, kann die sich ändernde Variable aus dem vereinfachten Term wegfallen.

Wie Gruppierung Variablen entfernt

Die visuelle Regel folgt aus booleschen Identitäten wie

$$XY + X\overline{Y} = X$$

Die beiden Terme unterscheiden sich nur in $Y$, also fällt $Y$ weg und der gemeinsame Teil $X$ bleibt übrig. Mit einer K-Map kann man dieses Kürzungsmuster direkt im Raster erkennen.

Karnaugh-Diagramm-Beispiel

Angenommen,

$$F(A,B,C) = \sum m(1,3,4,5,7)$$

Das bedeutet, dass $F=1$ für die Minterme $1$, $3$, $4$, $5$ und $7$ gilt.

Für eine K-Map mit $3$ Variablen verwendet man $A$ für die Zeilen und $BC$ für die Spalten in Gray-Code-Reihenfolge $00$, $01$, $11$, $10$:

$$\begin{array}{c|cccc} A \backslash BC & 00 & 01 & 11 & 10 \\ \hline 0 & 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 0 \end{array}$$

Beginne mit der größten gültigen Gruppe. Die vier $1$en in den beiden mittleren Spalten bilden eine Gruppe. In diesen vier Zellen bleibt $C=1$ konstant, während sich $A$ und $B$ ändern, also vereinfacht sich diese Gruppe zu

$$C$$

Eine $1$ ist noch nicht abgedeckt: Minterm $4$, also $(A,B,C)=(1,0,0)$. Paare ihn mit dem benachbarten Minterm $5$, also $(1,0,1)$.

In diesem Paar bleiben $A=1$ und $B=0$ konstant, während sich $C$ ändert, also vereinfacht sich das Paar zu

$$A\overline{B}$$

Damit lautet der vereinfachte Ausdruck

$$F(A,B,C) = C + A\overline{B}$$

Dieser kürzere Ausdruck ist äquivalent zur ursprünglichen Liste von Mintermen.

Regeln für gültige K-Map-Gruppen

Verwende Gruppen, deren Größen Zweierpotenzen sind: $1$, $2$, $4$, $8$ und so weiter.

Verwende die größten gültigen Gruppen, die möglich sind. Größere Gruppen entfernen meist mehr Variablen.

Denke daran, dass das Diagramm umläuft. Die linke und rechte Kante sind benachbart, und die obere und untere Kante sind ebenfalls benachbart.

Diagonal liegende Zellen sind nicht benachbart.

Überlappungen sind erlaubt, wenn sie helfen, eine größere oder einfachere Gruppierung zu bilden.

Häufige Fehler bei Karnaugh-Diagrammen

Normale Binärreihenfolge verwenden

Wenn du Zeilen oder Spalten mit $00$, $01$, $10$, $11$ beschriftest, ist die Nachbarschaft falsch. K-Maps müssen die Gray-Code-Reihenfolge verwenden, damit sich benachbarte Zellen nur in einem Bit unterscheiden.

Gruppen aus drei Zellen bilden

Eine Gruppe aus drei Zellen ist nie gültig. Die Gruppengröße muss eine Zweierpotenz sein.

Umlaufende Nachbarschaft übersehen

Einige der besten Vereinfachungen nutzen Zellen an gegenüberliegenden Rändern des Diagramms. Wenn du die Umlaufregel vergisst, ist deine Antwort oft länger als nötig.

Jede $1$ genau in eine Gruppe zwingen

Das ist keine Regel. Eine Zelle mehrfach zu verwenden, kann der beste Weg sein, eine größere Gruppe und einen kürzeren Endausdruck zu erhalten.

Wann ein Karnaugh-Diagramm verwendet wird

K-Maps sind in der Digitaltechnik und in einführenden Veranstaltungen zur Computertechnik verbreitet, weil sie die boolesche Vereinfachung zu einem visuellen Prozess machen. Sie sind besonders nützlich, wenn man vor dem Zeichnen oder Umsetzen einer Logikschaltung einen einfacheren Ausdruck in Sum-of-Products-Form haben möchte.

Sie sind auch gut für die Intuition. Selbst wenn Software größere Entwürfe übernimmt, hilft das Lernen von K-Maps dabei zu verstehen, warum sich bestimmte boolesche Terme zusammenfassen lassen und andere nicht.

Probiere eine ähnliche Aufgabe

Versuche, $F(A,B,C)=\sum m(0,2,4,6,7)$ selbst zu vereinfachen. Zeichne die K-Map, bilde zuerst die größten gültigen Gruppen und behalte dann nur die Variablen, die in jeder Gruppe konstant bleiben.

Wenn du noch einen Schritt weitergehen willst, probiere eine Version mit Don't-Care-Werten aus und verwende sie nur dann, wenn sie dir helfen, eine größere gültige Gruppe zu bilden.