Online Tutorial für das
Karnaugh-Veitch-Diagramm Applet
zur Logikminimierung von Funktionen.
Studienarbeit
am Fachbereich Informatik
der Universität Hamburg
vorgelegt von
Matthias Meyer 1998
Inhalt
Zusammenfassung
Die vorliegende Arbeit befaßt sich mit der Visualisierung der Logikminimierung von Funktionen durch
Karnaugh-Veitch-Diagramme ("KV-Diagramme"), um ein besseres Verständnis für den Prozeß der graphischen
Minimierung zu ermöglichen. Aufbauend auf den theoretischen Grundlagen wurde ein Java-Applet für KV-Diagramme
("KVD-Applet") entwickelt. Das Applet stellt beliebige Funktionen mit bis zu sechs Variablen in Form eines
KV-Diagrammes dar, das interaktiv durch den Benutzer bearbeitet werden kann. Eine Minimierung dieser
Schaltungsfunktion wird in disjunktiver und konjunktiver Normalform unterstützt. Um den Vorgang der
Minimierung didaktisch anschaulicher zu gestalten, wurde ein zweistufiges Verfahren implementiert. Ebenfalls
wurde die Bündelminimierung mehrerer Funktionen gleichzeitig in der disjunktiven Normalform ermöglicht.
Ein Exportieren der Schaltungsfunktion in textueller Form im PLA-Format [Espresso] wird unterstützt.
Abstract
This paper deals with the visualization of Boolean functions minimization with Karnaugh-Veitch diagrams
("KV diagrams"). It presents a Java applet that was developed to ease the understanding of graphical
minimization. The applet is able to represent any function with up to six inputs in a KV diagram which can
be modified interactively by the user. The minimization of the switching function is possible in both
disjunctive and conjunctive normal form. Also, the applet supports minimization of multiple-output functions
with up to eight outputs. A two-step visualization further helps to understand the graphical minimization
process. Export of the switching function is possible in PLA format [Espresso] .
Motivation
Zur Begleitung der Grundvorlesung zur technischen Informatik ("B-Zyklus") enstand dieses Applet zur
Visualisierung der Logikminimierung mit Karnaugh-Veitch-Diagrammen. Es richtet sich hauptsächlich an
Informatik-Studenten, die sich im Grundstudium befinden. Aber auch Fortgeschrittenen soll es als Werkzeug
im HADES-Projekt der Universität Hamburg dienen. Mit ihm sollen die Studenten ein besseres Verständnis für
die Methode der graphischen Logikminimierung bekommen. Dazu soll das Programm von Studenten als interaktives
Lernmittel eingesetzt werden. In den entsprechenden Übungen können sie dann direkt den Zusammenhang zwischen
Funktion, KV-Diagramm und der Schaltungsskizze erforschen und ein verbessertes Verständnis für den Prozeß des
Schaltnetzentwurfs bekommen. Durch die verbesserte Visualisierung und Interaktion soll den Studenten
insbesondere geholfen werden, zu verstehen, wie die graphische Zusammenfassung die Kosten einer
Hardwarerealisierung minimieren kann.
Übersicht
Das in dieser Arbeit erstellte KV-Diagramm-Applet verwendet eine graphische Benutzeroberfläche, die in zwei
Fenster aufgeteilt ist. Das Hauptfenster beinhaltet die eigentliche Oberfläche für die Interaktion mit dem
Benutzer und das KV-Diagramm ( s. Das KV-Diagramm Applet ). Das zweite Fenster beinhaltet die
graphische Anzeige der Gatterschaltung ( s. Die Schaltungsskizze ).
Das KVD-Applet besitzt folgende Funktionalität:
- Eine korrekte, einheitliche Darstellung von beliebigen KV-Diagrammen verschiedener Größe.
Die maximale Größe eines KV-Diagrammes liegt bei 6 Eingangsvariablen.
- Zur Veranschaulichung von Bündelminimierung können bis zu 8 KV-Diagramme gleichzeitig dargestellt
und verändert werden.
- Die Funktion wird sowohl in disjunktiver als auch in konjunktiver Normalform als Schaltungsskizze
anzeigt. Eine Funktionsminimierung ist in beiden Darstellungen möglich.
- Die Logikminimierung ist durch einen zusätzlichen Modus besonders anschaulich, Terme werden
dazu erst auf Anforderung zusammengefaßt.
- Der Benutzer kann interaktiv im KV-Diagramm die einzelnen Schleifen ziehen. In der
Schaltungsskizze wird gleichzeitig verdeutlicht, welche Gatter durch eine Schleife zusammengefaßt
wurden.
- Die Schaltungsfunktion ist in textueller Form exportierbar. Dabei wird das Berkley
PLA-Format [Espresso] verwendet.
- Die Fedlindizes im KV-Diagramm können zu jeder Zeit angezeigt werden, ohne das bestehende Schleife
gelöscht werden.
Das KVD-Applet ermöglicht eine graphische interaktive Minimierung von Schaltfunktionen. Die Eingabe der Funktion
erfolgt durch die direkte Modifikation eines bestehenden KV-Diagrammes. Hierzu stehen mehrere Beispiele, in
verschiedenen Größen, sowie ein Eingabe-Dialog zur Verfügung, mit dem beliebige Schaltfunktionen mit bis zu 6
Eingängen und 8 Ausgängen realisiert werden können. Die Anwendung verhält sich je nach eingestelltem Modi anders;
diese Hauptmodi schließen sich gegenseitig aus. Z.B. ist es nicht möglich, die Funktion im KV-Diagramm zu ändern,
und sich parallel dazu die Feldindices anzeigen zu lassen. Ein KV-Diagramm kann zunächst mittels des
Edit Function-Mode verändert werden. Dabei ist die Funktion ist in disjunktiver Normalform
Add Loop 1 DNF-Mode oder in konjunktiver Normalform Add Loop 0 KNF-Mode als Schaltungs-Skizze darstellbar.
Das Zusammenfassen und somit die Minimierung einzelner Terme erfolgt interaktiv durch eine Maus/Tasten-Steuerung.
Diese Minimierung wird durch den Student Mode besonders ausführlich veranschaulicht. Die Schaltungsfunktion
kann zusätzlich mit dem Menüpunkt PLA Text auch als Text, in Form einer PLA-Tabelle angezeigt und exportiert
werden.
Das KV-Diagramm-Applet
In diesem Hauptfenster des KVD-Applets wird die Funktion in einem KV-Diagramm dargestellt.Es enthält die gesamte
Oberfläche für die Interaktion mit dem Benutzer. Es gibt vier verschiedene Modi, die sich gegenseitig
ausschließen:
- Edit Funktion:
Die im KV-Diagramm dargestellte Funktion ist nun direkt mit der Maus editierbar,
durch einfaches anklicken wird aus einer 1 eine 0, aus einer 0 ein *(don´t care) und
aus einem * wieder eine 1.
- Show Indices:
Die im KV-Diagramm angezeigte Funktion wird durch die Anzeige der Indizes des KV-
Diagramms ersetzt. Vorhandene Schleifen bleiben vorhanden.
- Add Loop 1 DNF:
Das KV-Diagramm wird nun als DNF (disjunktive Normalform) in der Schaltungsskizze dargestellt.
Im KV-Diagramm sind die Minterme, die Einsen, durch Schleifen zusammenfaßbar.
- Add Loop 0 KNF:
Das KVD wird in der KNF (konjunktive Normalform) dargestellt und es sind somit die Maxterme, die
Nullen, die zusammengefaßt werden können.
Über die Menüleiste sind folgende Punkte erreichbar:
Menü: File
- Examples:
Hier befinden sich in Untermenüs angeordnet, alle Beispiel KV-Diagramme und der Eingabedialog.
- Export/PLA TEXT:
textuelle Ausgabe der Schaltfunktion.
- EXIT
Menü: Optionen
- Beginner Mode:
Das zweistufige Verfahren der Funktionsminimierung
wird aktiviert/deaktiviert.
- Zoom 50%:
Die Gatter in der Schaltungs-Skizze werden auf 50% verkleinert.
Im unterem Teil des Hauptfensters befindet sich ein Textfeld. In ihm werden abhängig von Modus
verschiedene Hinweise für die Bediehnung des Applets eingeblendet.
3. Die Schaltungs-Skizze
Ein Schaltnetz ist die Realisierung einer Schaltfunktion, in disjunktiver Normalform wird die
Schaltfunktion als zweistufiges Schaltnetz verwirklicht.
- Die Inverter sorgen für die Negierung der Eingangsvariablen. Wie üblich werden die Inverter nicht als
eigene Stufe angesehen.
- Die erste Stufe besteht aus UND-Verknüpfungen zur Bildung der Minterme aus den negierten
oder nicht negierten Eingangsvariablen.
- Die zweite und letzte Stufe besteht aus einer ODER-Verknüpfungen zur disjunktiven Verknüpfung
der Minterme.
In der folgenden Abbildung ist eine Schaltfunktion in disjunktiver Normalform dargestellt,
dies ist die Ausgangssituation in der für alle Minterme ein UND-Gatter dargestellt wird und diese
UND-Gatter in der zweiten Stufe an ein ODER-Gatter angeschlossen werden. Diese graphische Ausgabe ist
die der PLA (Programmable Logic Array) Architektur. In der ersten Zeile des Schaltungsfensters sind
die Kosten der Schaltung angegeben, Anzahl der Gatter und der Eingänge.
Die Schleifen
Ein zentraler Punkt bei der Minimierung mit KV-Diagrammen ist die menschliche Fähigkeit, zusammenhängende
Formen zu erkennen. Bei den KV-Diagrammen sind es die benachbarten Terme. Sie lassen
sich mit Hilfe von Schleifen zu einem Term zusammenfassen. Im Applet wird einfach ein Term durch
Anklicken mit der Maus direkt im KV-Diagramm selektiert. Man erhält eine neue Schleife, die genau diesen
Term abdeckt. Zur aktuellen Schleife wird ein gültiger Term addiert, indem die SHIFT-Taste
und die Maustaste gedrückt wird. Soll eine bestehende Schleife gelöscht werden, so muß die
CTRL-Taste gehalten und mit der Maus in die zu löschende Schleife geklickt werden.
- eine neue Schleife anlegen: einfacher Mausklick
- eine Schleife erweitern: SHIFT-Taste halten und durch einen einfachen Mausklick die aktuelle
Schleife erweitern.
- eine Schleife löschen: CRTL-Taste halten und einen Mausklick in die entsprechende Schleife.
5. Der Beginner Mode
Der Beginner Mode veranschaulicht, welche Gatter von einer Schleife zusammengefaßt werden, dies wird
durch eine Zweiteilung erreicht. Im ersten Schritt wird die Schleife im KV-Diagramm gezogen und die
betroffenen Gatter in der Schleifenfarbe hervorgehoben. Im zweiten Schritt wird die Schleife durch den Build
Loop Button bestätigt und die markierten Gatter werden zu einem minimiert.
Ohne diesen Zusatzmodus werden die betroffenen Gatter sofort durch die Schleife minimiert.
Man sieht also die Minimierung nicht so deutlich wie mit dem Beginner Mode.
- Ein Beispiel für den Beginner-Mode (Mertsching B1-Skript Seite 94)
In der nachfolgden Grafik ist nun eine Schleife im Beginner Mode gezogen worden und die überdeckten
Gatter der Schaltungsskizze wurden in der Schleifenfarbe hervorgehoben:
Im zweiten Schritt wurde die Schleife durch Betätigen des Build Loop Buttons bestätigt
und die hervorgehobenen Gatter wurden zu einem minimierten Gatter zusammengefaßt:
 |
 |
Ein einfaches Beispiel für die Benutzung des KV-Diagramm Applets
- Als erster Schritt wird, vom Benutzer ein geeignet großes Beispiel ausgewählt. Die Beispiele sind
über das entsprechende Menü ereichbar. Ein Dialog zur spezifikation von KV-Diagrammen steht ebenfalls
zur Verfügung.
- Jetzt kann das KV-Diagramm mittels des Edit Funktion Modus solange manipuliert
werden, bis die richtige Funktion dargestellt wird. Dieser Punkt wurde im Beispiel nicht
dargestellt. Als nächstes wird entschieden ob die Minimierung in DNF oder KNF vorgenommen
werden soll. Als Standard ist der disjunktive Modus eingestellt.
- Nachdem die Funktion eingegeben und der richtige Modus eingestellt wurde, kann jetzt
die erste Schleife mittels Mausklick im KV-Diagamm gezogen werden. Das entsprechende Gatter wird
in der Schaltungsskizze in der Schleifenfarbe hervor gehoben:
- Eine bestehende Schleife kann durch Halten der SHIFT-Taste und Mausklick um korrekte
Terme erweitert werden:
- Durch die Wiederholung der Schritte 3 und 4 erhält man ein Ergebnis der
Minimierung:
- Das Ergebnis der Funktionsminimierung kann ebenfalls in einer Textform ausgegeben werde.
Auf diese Weise können die Minimierungen in anderen Programmen eingesetzt werden:
