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: 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:
Über die Menüleiste sind folgende Punkte erreichbar:
Menü: File Menü: Optionen 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.


Das KVD mit dem Beispiel: Mertsching B1 s.94





3. Die Schaltungs-Skizze

Ein Schaltnetz ist die Realisierung einer Schaltfunktion, in disjunktiver Normalform wird die Schaltfunktion als zweistufiges Schaltnetz verwirklicht. 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 Schaltungs-Skizze in DNF





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.





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:
KVD+Loop PLA+Loop

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:
KVD+Loop PLA+Loop


Ein einfaches Beispiel für die Benutzung des KV-Diagramm Applets

  1. 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.

    Ein KV-Diagramm auswählen



  2. 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.

    DNFKV-DiagrammKNF
    DNF Entscheidung ob DNF oder KNF KNF




  3. 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 Schleife Eine Schleife



  4. Eine bestehende Schleife kann durch Halten der SHIFT-Taste und Mausklick um korrekte Terme erweitert werden:

    die Schleife wird erweitert die Schleife wird erweitert



  5. Durch die Wiederholung der Schritte 3 und 4 erhält man ein Ergebnis der Minimierung:

    Ergebnis PLA Ergebnis KVD



  6. Das Ergebnis der Funktionsminimierung kann ebenfalls in einer Textform ausgegeben werde. Auf diese Weise können die Minimierungen in anderen Programmen eingesetzt werden:

    Ergebnis als Text