Karnaugh-Map Rechner (KV-Diagramm)

Boolesche Funktionen mit einem KV-Diagramm vereinfachen

Ein KV-Diagramm beziehungsweise eine Karnaugh-Map ordnet die Werte einer booleschen Funktion so an, dass benachbarte Kombinationen nur in einer Variablen unterschiedlich sind.

Der Rechner unterstützt 2 bis 5 Variablen. Die Funktion kann über das KV-Diagramm, eine Wahrheitstabelle, einen booleschen Ausdruck, Minterme oder Maxterme eingegeben werden.

Alle Eingabeformen beschreiben dieselbe Funktion und bleiben miteinander synchronisiert.

0, 1 und Don't-Care

Jede Zelle kann einen der folgenden Zustände haben:

• 1 für eine wahre Ausgabe;
• 0 für eine falsche Ausgabe;
• X für einen Don't-Care-Zustand.

Ein X darf in eine Gruppe aufgenommen werden, wenn dadurch eine einfachere Lösung entsteht. Es muss aber nicht verwendet werden.

Von der Wahrheitstabelle zum KV-Diagramm

Eine Wahrheitstabelle enthält jede mögliche Eingangskombination einer Funktion.

Das KV-Diagramm verwendet dieselben Kombinationen, ordnet sie aber nach dem Gray-Code an.

Dadurch unterscheiden sich benachbarte Zellen nur in einer Variablen.

Beispiel:

A'B'

A'B

Hier ändert sich nur B.

Die beiden Terme lassen sich daher zu:

A'

zusammenfassen.

Genau dieses Prinzip wird bei größeren Gruppen wiederholt.

Minterme, Maxterme und boolesche Ausdrücke

Wenn die Aufgabe bereits Minterme enthält, können diese direkt eingegeben werden.

Zum Beispiel:

Σm(1,3,5,7)

beschreibt die Eingangskombinationen mit Ausgabe 1.

Mit:

ΠM(0,2,4,6)

werden dagegen die Maxterme beziehungsweise die Kombinationen mit Ausgabe 0 angegeben.

Auch ein boolescher Ausdruck kann direkt eingegeben werden. Daraus erzeugt das Tool die entsprechende Wahrheitstabelle und Karnaugh-Map.

So lassen sich verschiedene Darstellungen derselben Funktion direkt miteinander vergleichen.

Gruppen im KV-Diagramm

Gültige Gruppen enthalten eine Zweierpotenz an Zellen:

1, 2, 4, 8, 16

Je größer eine gültige Gruppe ist, desto mehr veränderliche Literale können aus dem entsprechenden Term verschwinden.

Wichtig ist auch die Randnachbarschaft.

Die linke und rechte Seite eines KV-Diagramms sind logisch benachbart. Dasselbe gilt für den oberen und unteren Rand.

Deshalb können auch die vier Eckzellen gemeinsam eine gültige Gruppe bilden.

Überlappende Gruppen sind ebenfalls erlaubt, wenn sie zu einer einfacheren Abdeckung führen.

SOP und POS vergleichen

Bei SOP (Sum of Products) werden hauptsächlich die Zellen mit Ausgabe 1 betrachtet.

Ein Ergebnis könnte so aussehen:

A'B + BC

Bei POS (Product of Sums) werden die 0-Ausgaben gruppiert.

Zum Beispiel:

(A + B')(B + C)

Keine der beiden Formen ist grundsätzlich immer kürzer.

Bei manchen Funktionen ist SOP einfacher, bei anderen POS.

Wenn eine Aufgabe keine bestimmte Form verlangt, kann es sinnvoll sein, beide Ergebnisse zu vergleichen.

Quine-McCluskey und Petrick's Method

Bei kleinen KV-Diagrammen lassen sich sinnvolle Gruppen oft sofort erkennen.

Bei 4 oder 5 Variablen kann es jedoch mehrere mögliche Überdeckungen geben.

Der Solver verwendet Quine-McCluskey, um die Primimplikanten der Funktion systematisch zu bestimmen.

Ein Primimplikant kann nicht weiter vergrößert werden, ohne ungültige Kombinationen einzuschließen.

Ein wesentlicher Primimplikant deckt mindestens eine erforderliche Kombination ab, die kein anderer Primimplikant abdeckt.

Bleiben anschließend mehrere mögliche Überdeckungen übrig, kann Petrick's Method zur Auswahl der verbleibenden Kombinationen verwendet werden.

So lässt sich auch bei komplizierteren Funktionen nachvollziehen, wie das vereinfachte Ergebnis entsteht.

KV-Diagramme mit 2 bis 5 Variablen

Ein 2-Variablen-KV-Diagramm enthält 4 Zellen.

Bei 3 Variablen gibt es 8 Zellen und die Randnachbarschaft spielt bereits eine wichtige Rolle.

Ein 4-Variablen-KV-Diagramm besitzt 16 Zellen und ist in Aufgaben zur Digitaltechnik besonders verbreitet.

Mit 5 Variablen entstehen 32 Eingangskombinationen. Dadurch nimmt die Zahl möglicher Gruppen deutlich zu.

Das Tool hält KV-Diagramm, Wahrheitstabelle, Ausdruck, Minterme und Maxterme bei jeder unterstützten Größe synchron.

Logikschaltung und PDF

Nach der Vereinfachung kann der Ausdruck als Logikschaltung dargestellt werden.

Dadurch wird sichtbar, wie ein SOP- oder POS-Ausdruck mit AND-, OR- und NOT-Gattern umgesetzt werden kann.

Zusätzlich lassen sich Anzahl der Terme, Literale und Gatter betrachten.

Für eine spätere Kontrolle kann die Lösung als PDF mit Diagramm, Gruppen, Herleitung und Schaltung exportiert werden.