Karnaugh-Diagramm (K-Map) Löser

Der Karnaugh-Diagramm (K-Map) Löser minimiert jede boolesche Logikfunktion mit 2 bis 5 Variablen und visualisiert die Vereinfachung als klassisches K-Diagramm mit farbcodierten Gruppierungen. Geben Sie Ihre Minterme oder Maxterme ein oder nutzen Sie die interaktive Wahrheitstabelle — der Löser führt im Hintergrund den Quine-McCluskey-Algorithmus aus, findet jeden Primimplikanten, markiert die essentiellen und erstellt die minimale disjunktive (SOP) oder konjunktive (POS) Normalform mit einer Schritt-für-Schritt-Erklärung. Klicken Sie auf einen Primimplikanten-Chip, um die abgedeckten Zellen pulsieren zu lassen und zu sehen, wie die Gruppierung die Logik vereinfacht.

Was ist ein Karnaugh-Diagramm?

Ein Karnaugh-Diagramm (1953 von Maurice Karnaugh erfunden) ist eine grafische Darstellung einer Wahrheitstabelle, bei der die Zellen so angeordnet sind, dass sich benachbarte Zellen nur um eine Eingangsvariable unterscheiden. Der entscheidende Trick ist die Gray-Code-Sortierung von Zeilen und Spalten: aufeinanderfolgende Beschriftungen wie 00, 01, 11, 10 unterscheiden sich in genau einem Bit. Diese Nachbarschaft ermöglicht es, Gruppen von 1en (oder 0en) visuell zu erkennen, die zu einem einzigen vereinfachten Term kombiniert werden können.

Für n Eingangsvariablen hat die K-Map 2^n Zellen. Eine 4-Variablen-K-Map ist ein 4×4-Gitter mit 16 Zellen; eine 5-Variablen-Map wird als zwei benachbarte 4×4-Gitter dargestellt.

SOP vs. POS: Welche Form soll man wählen?

Sum of Products (SOP / DNF)

SOP gruppiert die 1-Zellen. Jede Gruppe wird zu einem Produkt (UND) von Literalen, und alle Gruppen werden ODER-verknüpft. Beispiel: AB'C + BD. SOP ist meist der Standard, da es direkt auf UND-ODER-Gatternetzwerke abgebildet werden kann.

Product of Sums (POS / KNF)

POS gruppiert die 0-Zellen. Jede Gruppe wird zu einer Summe (ODER) der komplementierten Literale, und alle Summen werden UND-verknüpft. Beispiel: (A + B')(C + D'). POS ist oft kürzer, wenn die Funktion mehr 1en als 0en enthält.

Das Tool berechnet beide Formen unabhängig voneinander — schalten Sie den Ausgabemodus um, um die Anzahl der Literale zu vergleichen und die einfachste Form für Ihre Implementierung zu wählen.

Gruppierungsregeln für Karnaugh-Diagramme

• Nur Zweierpotenz-Gruppen: Gruppen müssen 1, 2, 4, 8 oder 16 Zellen enthalten. Eine Gruppe von 3 oder 5 ist nicht zulässig.
• Rechteckige Form: Die Zellen in einer Gruppe bilden ein Rechteck (horizontal, vertikal oder über die Ränder umwickelt).
• Zyklische Nachbarschaft (Wrap-around): Die oberste Zeile ist benachbart zur untersten; die ganz linke Spalte ist benachbart zur ganz rechten. Deshalb ist die Gray-Code-Sortierung wichtig.
• Größtmögliche Gruppen zuerst: Größere Gruppen eliminieren mehr Variablen und erzeugen kürzere Terme. Eine 8-Zellen-Gruppe eliminiert 3 Variablen; eine 4-Zellen-Gruppe 2; eine 2-Zellen-Gruppe 1.
• Jede 1 muss abgedeckt sein: Mindestens eine Gruppe muss jede 1-Zelle (bei SOP) bzw. 0-Zelle (bei POS) abdecken.
• Überlappungen sind erlaubt: Dieselbe 1 kann von mehreren Gruppen abgedeckt werden, wenn dies zu größeren Gruppen führt.
• Don't-Cares sind flexibel: Sie können gruppiert werden, wenn dadurch größere Gruppen entstehen, müssen aber nicht abgedeckt werden.

Primimplikanten und essentielle Primimplikanten

Ein Primimplikant ist eine Gruppe, die nicht weiter vergrößert werden kann — eine Vergrößerung würde eine 0-Zelle (bei SOP) einschließen. Der Löser listet jeden gefundenen Primimplikanten auf. Dann wählt er eine minimale Überdeckung: den kleinsten Satz von Primimplikanten, der jeden erforderlichen Minterm abdeckt.

Ein essentieller Primimplikant wird als ESSENTIELL markiert, wenn er der einzige Primimplikant ist, der einen bestimmten Minterm abdeckt. Jeder minimale Ausdruck muss alle essentiellen Primimplikanten enthalten. Danach werden die verbleibenden ungedeckten Minterme durch die „günstigsten“ zusätzlichen Primimplikanten abgedeckt.

Don't-Care-Bedingungen

Ein Don't-Care (markiert als X im K-Diagramm) ist eine Eingangskombination, deren Ausgang irrelevant ist — entweder tritt sie in der realen Schaltung nie auf oder ihr Wert spielt keine Rolle. Der Algorithmus kann jedes X entweder als 0 oder 1 behandeln, je nachdem, was den einfacheren Ausdruck ergibt. In der Praxis reduzieren Don't-Cares die Anzahl der Literale oft um 30–60%. Ein typisches Beispiel aus der Praxis: Dezimalziffer-Decoder, die nur 10 der 16 möglichen 4-Bit-Eingangskombinationen nutzen, wodurch die Kombinationen 10–15 als Don't-Cares verbleiben.

Der Quine-McCluskey-Algorithmus

Das K-Diagramm ist eine visuelle Methode, wird aber bei mehr als 4–5 Variablen unpraktisch. Der Quine-McCluskey (QM)-Algorithmus ist das tabellarische Äquivalent — mathematisch präzise und skalierbar. Dieser Löser nutzt QM intern:

1. Minterme binär auflisten und nach der Anzahl der 1-Bits gruppieren.
2. Paare kombinieren aus benachbarten Gruppen (Unterschied in genau einem Bit), wobei das unterschiedliche Bit durch einen Bindestrich ersetzt wird. Beispiel: 0011 + 0111 → 0-11.
3. Wiederholen, bis keine weiteren Kombinationen möglich sind. Terme, die nicht weiter kombiniert werden können, sind Primimplikanten.
4. Primimplikantentafel erstellen — Zeilen sind Primes, Spalten sind erforderliche Minterme. Essentielle Primes identifizieren (Spalten mit nur einem Häkchen).
5. Petrick-Verfahren / Erschöpfende Suche: Für die restlichen Minterme den kleinsten Satz zusätzlicher Primes finden.

So verwenden Sie diesen Rechner

1. Anzahl der Variablen wählen: 2, 3, 4 oder 5. Das Gitter passt sich automatisch an.
2. Eingabemethode wählen:
   • Minterme: Geben Sie Indizes ein, bei denen F = 1 ist (z. B. 1, 3, 5, 7) sowie etwaige Don't-Cares.
   • Maxterme: Geben Sie Indizes ein, bei denen F = 0 ist. Der Löser berechnet die restlichen als 1en.
   • Wahrheitstabelle: Klicken Sie auf jede Zeile, um den Ausgang zwischen 0, 1 und X umzuschalten. Ideal für manuell entworfene Logik.
3. SOP- oder POS-Ausgabe wählen. Vergleichen Sie beide Formen durch Umschalten — eine ist oft kürzer als die andere.
4. Auf „Lösen“ klicken. Die K-Map erscheint mit jedem Primimplikanten in einer eigenen Farbe. Klicken Sie auf einen Chip, um die abgedeckten Zellen hervorzuheben.
5. Schritte prüfen: Die Quine-McCluskey-Aufschlüsselung zeigt, wie jeder Primimplikant hergeleitet wurde und welche essentiell sind.

Anwendungsbeispiel: 4-Variablen-Funktion mit Don't-Cares

Betrachten Sie F(A,B,C,D) = Σm(1, 3, 7, 11, 15) + d(0, 2, 5).

Ohne Don't-Cares bräuchte die minimale SOP mehrere Terme. Wenn {0, 2} als 1en behandelt werden, kann der Löser die 4-Zellen-Gruppe A'B' bilden (die 0, 1, 2, 3 abdeckt). Wenn 5 als 1 behandelt wird, erweitert dies die Abdeckung von CD. Die resultierende Vereinfachung ist:

Nur 4 Literale — statt über 10 ohne den Don't-Care-Trick. Sie können genau dieses Beispiel mit dem Schnellbeispiel „4-Var mit Don't-Cares“ oben laden.

Warum boolesche Funktionen minimieren?

• Weniger Gatter = geringere Hardwarekosten, kleinere Chipfläche, niedrigerer Stromverbrauch.
• Schnellere Schaltungen: Weniger Gatterlaufzeiten im kritischen Pfad.
• Saubere Dokumentation: Ein prägnanter Ausdruck ist einfacher zu verifizieren und zu warten.
• Grundlage des digitalen Designs: Jedes FPGA-Synthese-Tool nutzt einen Nachfahren von Quine-McCluskey (wie Espresso-II).

Einschränkungen und alternative Tools

• 5+ Variablen: K-Diagramme werden visuell unübersichtlich. Dieses Tool unterstützt bis zu 5 Variablen durch Aufteilung in zwei 4×4-Diagramme. Nutzen Sie darüber hinaus die Quine-McCluskey-Schritte oder Synthese-Tools wie ABC / Espresso.
• Hazards und Glitches: Eine minimale Überdeckung kann statische Hazards enthalten. Für ein hazard-freies Design müssen redundante Primimplikanten einbezogen werden — dieses Tool markiert sie, fügt sie aber nicht automatisch als Hazard-Cover hinzu.
• Minimierung mehrerer Ausgänge: Wenn mehrere Funktionen Variablen teilen, ergibt eine gemeinsame Minimierung (Gatter-Sharing) effizientere Hardware. Dieses Tool minimiert jeweils nur eine Funktion.

Häufig gestellte Fragen (FAQ)

Was ist ein Karnaugh-Diagramm?

Ein Karnaugh-Diagramm (K-Map) ist eine visuelle Methode zur Minimierung boolescher Ausdrücke. Die Zellen sind so angeordnet, dass sich benachbarte Zellen nur um eine Variable unterscheiden (Gray-Code-Sortierung). Die Gruppierung von 1ern in Rechtecken der Größe 1, 2, 4, 8 oder 16 ergibt den minimalen disjunktiven Ausdruck.

Was ist der Unterschied zwischen SOP und POS?

SOP (Sum of Products) gruppiert die 1-Zellen und verknüpft die Produktterme mit ODER, z. B. A'B + CD. POS (Product of Sums) gruppiert die 0-Zellen und verknüpft die Summenterme mit UND, z. B. (A + B')(C' + D). Beide beschreiben dieselbe Funktion, aber eine Form ist meist kompakter.

Was sind Don't-Cares und warum werden sie verwendet?

Don't-Care-Terme (markiert mit X) sind Eingabekombinationen, deren Ausgabewert irrelevant ist — sie treten nie auf oder ihr Wert spielt keine Rolle. Der Löser kann sie entweder als 0 oder 1 behandeln, je nachdem, was zu einem einfacheren Ausdruck führt. Don't-Cares reduzieren oft drastisch die Anzahl der Literale.

Was ist ein Primimplikant?

Ein Primimplikant ist die größtmögliche Gruppe benachbarter 1-Zellen (Zweierpotenz-Größe), die nicht weiter vergrößert werden kann. Ein essentieller Primimplikant ist einer, der mindestens einen Minterm allein abdeckt und in jedem minimalen Ausdruck enthalten sein muss.

Wie funktioniert der Quine-McCluskey-Algorithmus?

Quine-McCluskey ist das tabellarische Äquivalent zu einem K-Diagramm, geeignet für viele Variablen. Er listet Minterme binär auf, gruppiert sie nach der Anzahl der 1en und kombiniert iterativ Paare, die sich in genau einem Bit unterscheiden. Terme, die nicht weiter kombiniert werden können, sind Primimplikanten. Eine Primimplikantentafel wählt dann die minimale Überdeckung.

Wie viele Variablen unterstützt dieser K-Map-Löser?

Dieses Tool unterstützt 2 bis 5 Variablen. Eine 5-Variablen-K-Map wird als zwei benachbarte 4×4-Diagramme angezeigt (eines für A=0, eines für A=1). Für mehr als 5 Variablen werden K-Maps unpraktisch; nutzen Sie dann die Quine-McCluskey-Schritte.

Weiterführende Informationen

• Karnaugh-Diagramm — Wikipedia
• Quine-McCluskey-Verfahren — Wikipedia
• Petrick-Methode — Wikipedia (Englisch)