Softwarerealisierung für Finite State Machines (FSM) im Projekt JGIFT - Werkzeug zur Generierung, Editierung und Simulation von Finite State Machines

Inhaltsverzeichnis

1 Projektvorstellung
1.1 Einleitung
1.2 Aufgabe

2 JGIFT Datenstruktur
2.1 XML
2.2 Umformung und Minimierung (Bäume)
2.2.1 Eingabeformat
2.2.2 Baumstruktur - Wie sieht eine eingelesene Gleichung aus?
2.2.3 DNF erzeugen
2.2.4 Reduzieren
2.2.5 Quine/McCluskey und die Modi kation
2.2.6 Exkurs Doppeltes Produkt

3 Generierung der Ausgabe
3.1 Ausgabemöglichkeiten
3.2 User Interface
3.3 LOG/iC Codegenerierung
3.4 Ansi-C Codegenerierung
3.4.1 Erklärungen Ansi-C Dateien
3.4.2 Erklärungen Ansi-C Methoden

4 Demo am Beispiel + Vorführung
4.1 Einführung des Beispiels
4.2 Minimieren ohne h*
4.2.1 manuelles Nachvollziehen des Beispiels . .
4.2.2 Vergleich mit den Ergebnissen des JGIFT-Systems
4.3 Minimieren mit h*
4.3.1 Überlegungen zu h*
4.3.2 Ergebnis und Vergleich

5 Ausblick

A XML-Datei für die Pumpensteuerung

Abstract

Ziel dieser Arbeit ist die Realisierung einer automatischen Code- generierung für das Experimentalsystem JGIFT. JGIFT (Java-based Graphical Interactive FSM-Tool) ist ein Werkzeug zur Generierung, Editierung und Simulation von Finite State Machines. Über ein grafisches Userinterface wird angeboten bestehende FSMs zu minimieren, sowie Quellcode für verschiedene Hardware (Microchips und Programmable Logic Devices) zu generieren.

Goal of this work is to realize an automatic code generator for the experimental system JGIFT. JGIFT (Java-based Graphical Interactive FSM Tool) is a tool for the generation, editing and simulation of Finite State Machines. A graphical user interface provides the possibility to minimize existing FSMs and to generate source code for different hardware (Microchips and Programmable Logic Devices).

Kapitel 1 Projektvorstellung

1.1 Einleitung

Das Fachgebiet IHS der TU Ilmenau beschäftigt sich seit einigen Jahren mit der Erstellung und Implementierung von FSM-(Finite State Machine)Tools. Besonderes Augenmerk wird hierbei auf

- Transparenz der Entwurfsschritte,
- einen hoher Grad an Interaktivität,
- Editoren zur gra schen und textuellen Spezi kation
- einer eigenen Simulationsumgebung,
- Prüfalgorithmen zum erkennen und lokalisieren von Fehlern (zB. Veri- kation),
- Möglichkeiten der Codegenerierung für andere Hard- und Software- plattformen
- sowie Netzwerkunterstützung.

gelegt. Im Zuge dieser Anforderungen entstand unter andrem das Experi- mentalsystems GIFT (Graphical Interactive FSM-Tool) welches bis heute im Einsatz ist. Ein nicht zu unterschätzender Nachteil des bisherigen Ent- wurfsystems ist jedoch die Abhängigkeit vom Betriebsystem. Derzeit läuft GIFT lediglich auf Unix/Linux-Systemen, was Benutzern anderer Betrieb- systeme (vor allem Windows aber auch MAC-OS, u.a.) den Umgang unmög- lich macht. Dies ist mit Sicherheit ein Grund, dass es noch kein webbasiertes Praktikum mit dem GIFT-System im Fachgebiet gibt und sicherlich auch nicht geben wird.

Aktuelle Projekte beschäftigen sich nun mit der Weiterentwicklung des Ex- perimentalsystems GIFT zum JGIFT (auf Java Virtual Machine aufsetzen- des GIFT), welches dann Plattform unabhängig ist. Dabei ergibt sich die Notwendigkeit zur Änderung, Erweiterung und auch Verbesserung der bestehenden Implementierung.

1.2 Aufgabe

Unsere Aufgabe besteht darin eine im XML Format gegebene JGIFT-Datenstruktur eines Automatengraphen einzulesen und dem Nutzer die Möglichkeit zu ge- ben diesen Automatengraphen via gra schem Userinterface

- zu Minimieren (mit und ohne h*)
- in LogIC(Flow-Table oder Gleichungsdarstellung) oder C-Code zu kon- vertieren,
- die Output-Hardware für den erzeugten Code zu de nieren und
- den erzeugten Output-Code zu speichern.

Der Vorteil dieser automatischen Codegenerierung ist, neben der auf der Hand liegenden Zeitersparnis gegenüber der händischen Codegenerierung, für die man sich unter Umständen erst einlesen muss, vor allem das erreichen eines hohen Grades an Korrektheit (nicht nur in der Syntax sondern auch in der Funktion), die ein solches automatisches Werkzeug mit sich bringt.

Aufgrund der neu entworfenen JGIFT-Datenstruktur und der geringfügi- gen Dokumentation des GIFT Systems, war es sehr wenig beziehungsweise gar nicht möglich auf GIFT-Quellcode zurückzugreifen. Desweiteren führ- te eine Internetrecherche hierzu ebenfalls nicht zum gewünschten Erfolg, was zur Folge hatte, dass wir mit unserer Implementierung bei Null begin- nen mussten. Zur Realisierung stand uns das Entwicklungswerkzeug Eclipse (http://www.eclipse.org) und die Programmiersprache Java (http://java.sun.com) zur Verfügung. Zur Überprüfung des erzeugten Quellcodes wurden die CompilerSysteme lcc-win32 (für Ansi-C) und LOG/iC2 (für LOG/iC) benutzt.

Kapitel 2 JGIFT Datenstruktur

2.1 XML

Ein wohlgeformtes XML-Dokument befolgt die Regeln des Standards, also beispielsweise < und > werden richtig benutzt und die Elemente sind kor- rekt geschachtelt. Korrekte Schachtelung bedeutet, dass, wenn das Start-Tag innerhalb eines Elements ist, auch das End-Tag in diesem Element enthalten sein muss.

Ein wohlgeformtes XML-Dokument wird als gültig oder valide bezeichnet, wenn es den Regeln einer DTD folgt. Ein Dokument kann also wohlgeformt und nicht gültig sein, aber niemals gültig und nicht wohlgeformt. Auÿerdem ergibt sich, dass ein Dokument immer nur bezüglich einer DTD, und nicht von sich aus gültig sein kann.

Der Automatengraph wird in einer XML-Datei vorgegeben. In einer XMLDatei können alle möglichen Dinge stehen. Durch Tags wird festgelegt wie das, was in dem Tag steht zu interpretieren ist.

Abbildung in dieser Leseprobe nicht enthalten

Zum Beispiel liegen im Tag <interface> alle Informationen zum Interface des Automaten. Das sind vorhandene Zustände des Automaten, Eingangs- variablen und Ausgangsvariablen des Automaten. Jedes Tag kann Untertags besitzen, um die Inhalte noch besser zu trennen. Unter interface zum Bei- spiel <invarlist>, <outvarlist>, <statevarlist>. So ist der komplette Automat mit Zustandsübergängen eindeutig de niert. Ein Parser liest dann alle Informattionen in ein Java-Objekt ein, das dann genauso aufgebaut ist, wie die ursprüngliche XML-Datei. Durch get-Methoden sind dann die benö- tigten Informationen abrufbar.

Die XML-Spezi kation gibt auch syntaktisch einige Dinge vor:

- Bei allen Werten von Parametern und Dateninhalten von Tags, wird nicht zwischen Groÿ- und Kleinschreibung unterschieden.
- Für benutzerde nierte Variablennamen gelten folgende Einschränkun- gen für die verwendeten Zeichen:

_Zugelassen sind die Zeichen A bis Z , a bis z , 0 bis 9 , sowie _

_Das erste Zeichen des Variablennamens ist ein Buchstabe.

_Umlaute, Sonderzeichen, Klammern, ... sind nicht erlaubt.

- Für Beschreibungen sind keine Steuerzeichen mit einem ASCII-Wert kleiner als 32 erlaubt. Zeilenumbrüche sind mittels des <br/>-Tags zu realisieren.

- Statusvariablen dürfen nicht Modul-Ausgängen zugewiesen werden.

- Ausgangsvariablen dürfen nicht als Eingänge verwendet werden.

- Jeder benutzerde nierte Variablenname darf nur einmal innerhalb ei- nes Moduls auftauchen.

- Tags, die Listenelemente darstellen, werden durch einen Schlüssel spe- zialisiert. Dieser darf innerhalb der umgebenden Liste nur einmal auf- tauchen.

- Parameter, die nicht zwingend erforderlich, also optional sind, sind von dieser Einschränkung ausgenommen.

- Operatoren müssen drei verschiedene Zeichen sein. Möglich sind: !, Ÿ, $, %, &, /, *, +, # und -.

2.2 Umformung und Minimierung (Bäume)

Nachdem eine anfänglichen Recherche keine passende Lösung für das Umformen und Minimieren von Gleichungen brachte, wurde für dieses Projekt eine eigene Lösung implementiert.

Der Algorithmus von Quine/McCluskey wurde dabei den Bedürfnissen, einer möglichst schnellen Berechnung, dieses Projektes angepasst. Der modi- zierte Algorithmus berechnet aus einer beliebigen Gleichung eine Teilmen- ge der Primimplikanten. Ein optimal minimiertes Polynom besteht aus einer Teilmenge aller Primimplikanten einer Gleichung, diese Teilmenge wird mit- tels des Branch&Bound Algorithmus gefunden. Sowohl der Quine/McCluskey als auch der Branch&Bound Algorithmus haben eine exponentielle Laufzeit.

2.2.1 Eingabeformat

Über den Konstruktor GleichungsBerechnung wird die zu minimierende Glei- chung als String übergeben. Das Eingabeformat richtet sich nach der XML Spezi kation für Automatengraphen. Es ist eigenständig und unabhängig von der XML Spezi kation implementiert, so dass es in anderen Projekten wiederverwendet werden kann. Folgende Zeichen dürfen verwendet werden:

- ö nende und schlieÿende Klammern: (,)
- Leerzeichen für die Übersichtlichkeit
- logisches UND: &
- logisches ODER: #
- Verneinung: !
- Variablen: eine beliebige Zeichenkette, die die Anforderungen der XML Spezi kation für Automatengraphen erfüllt

Beispiele:

- a&!(b&!c#d)#!(a&!d)

- (((!s_k0_1&(!s_k0_2&!x_sen_2)) #((!s_k0_1&(s_k0_2&(!x_sen_3&x_sen_0))) #(s_k0_1&(!s_k0_2&x_sen_1))))#!x_sen_2)

2.2.2 Baumstruktur - Wie sieht eine eingelesene Gleichung aus?

Das interne Format der Gleichung ist eine Baumstruktur. In der Klasse Baum ist ein klassischer Binärbaum implementiert. Dieser Baum besitzt einen lin- ken und rechten Teilbaum und einen Wert. Bei dem Wert kann es sich um einen Operator ∧, ∨, ¬, um eine Variable oder um eine negierte Variable handeln. Handelt es sich bei dem Wert um einen Negator (¬), so wird die zu negierende Teilgleichung im rechten Teilbaum gespeichert, der linke Teil- baum bleibt leer (null).

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.1: Baumstruktur der Gleichung

2.2.3 DNF erzeugen

Um den Quine/McCluskey Algorithmus nutzen zu können, muss die beliebig aussehende Eingabegleichung in eine DNF umgewandelt werden. Dabei sind folgende zwei Schritte notwendig.

Im ersten Schritt werden alle Negatoren an die Variablen gebunden. Da- für wird jeder einzelne Negator (¬) entfernt und der rechte Teilbaum um eine Ebene nach oben verschoben. Zusätzlich werden alle Operatoren im Unter- baum vertauscht. Aus UND (∧) wird ODER (∨) und aus ODER (∨) wird UND (∧). Alle nicht negierten Variablen werden negiert und andersrum. Die- se Prozedure entspricht der maximalen Anwendung des DeMorgan Gesetzes.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.2: Baum nach Negatoren-Bindung

Im zweiten Schritt wird die DNF erzeugt. In der Baumstruktur lässt sich dabei erkennen, das eine DNF genau dann vorliegt, wenn ab dem ersten Vorkommen eines UND-Operators (∧) im Baum kein tieferliegender ODER- Operator (∨) mehr in dessen Teilbäumen vorhanden ist. Um dies zu erreichen wird jeder Teilbaum, der in der Wurzel ein UND (∧) und in einem seiner Kinder ein ODER (∨) hat, umgehangen. Das Umhängen entspricht dem Distributivgesetz.

Abbildung in dieser Leseprobe nicht enthalten

2.2.4 Reduzieren

Der Quine/McCluskey Algorithmus hat eine exponentielle Laufzeit. Um die Laufzeit zu reduzieren ist es sinnvoll aus einer erzeugten DNF alle unnötigen Teilterme und Literale zu löschen um die Gleichungsgröÿe zu reduzieren. Vier Kürzungsregeln werden angewendet:

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.3: Schema des Umhängens zur Bildung der DNF

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.4: Baum nach DNF-Bildung

- Kürzungsregel 1:

-in jedem Monom kommt jedes Literal nur einmal vor
-Bsp: x ∧ y ∧ x ⇒ x ∧ y

- Kürzungsregel 2:

-wenn in einem Monom widersprüchliche Literale vorkommen, dann kann das Monom gestrichen werden
-Bsp: xx∨ a ∨ b ⇒ a ∨ b

- Kürzungsregel 3:

-wenn ein Monom nur aus einem Literal besteht und es gibt ein zweites Monom was entgegengesetzt ist, dann ist die ganze Glei- chung 1
-Bsp: x ∨ yz ∨x⇒ 1

- Kürzungsregel 4:

-wenn zwei Monome gefunden werden, wo eines die Verkürzung des anderen ist, dann kann das längere gelöscht werden
-Bsp: wxyz ∨ xy ⇒ xy, vw ∨ vw ⇒ vw

2.2.5 Quine/McCluskey und die Modi kation

Der Quine/McCluskey Algorithmus erwartet eine KDNF als Eingabe und berechnet alle Primimplikanten. Dazu werden alle Monome sukzessiv mitein- ander verglichen. Falls sich zwei Monome gleicher Länge nur um die Negation eines Literals unterscheiden, werden beide zu einem Monom zusammenge- kürzt. Gibt es kein zweites Monom zum kürzen, so wurde ein Primimplikant gefunden.

Sind alle Primimplikanten gefunden, ist es Aufgabe des Branch&Bound Algorithmus das Minimalpolynom, dass ist eine minimale Teilmenge der Primimplikanten, zu nden. Die Anzahl der Primimplikanten kann exponentiell sein. Die Berechnung des Minimalpolynoms hat, genauso wie der Quine/McCluskey Algorithmus, eine exponentielle Laufzeit.

Für dieses Projekt wurde darauf verzichtet die Laufzeit durch das zusätz- liche Berechnen des Minimalpolynoms zu erhöhen. Der Quine/McCluskey Algorithmus wurde dahingehend verändert, das dieser als Eingabe keine KDNF mehr erwartet, sondern eine beliebige DNF akzeptiert. Dieser mo- di zierte Algorithmus gibt statt des Minimalpolynoms nun eine Primimpli- kantenteilmenge zurückgibt und bevorzugt die Primimplikanten, die bereits in der Eingabemenge vorhanden waren. Dadurch kann es vorkommen, das der modi zierte Algorithmus ein Minimalpolynom berechnet, während der Quine/McCluskey Algorithmus mit der Ausgabe aller Primimplikanten kein Minimalpolynom ausgibt.

Der modi zierte Algorithmus nutzt, dass die Eingabe durch den Men- schen schon voroptimiert sein kann. Ist die Eingabe schlecht gewählt oder entspricht der KDNF, so berechnet der modi zierte Algorithmus auch die komplette Primimplikantenmenge. Im Falle der Eingabe einer DNF gibt der modi zierte Algorithmus alle Primimplikanten oder eine suboptimale Teil- menge aller Primimplikanten oder das Minimalpolynom (optimale Teilmen- ge) aus.

Die folgenden Kanaugh-Pläne sollen die Modi kation verdeutlichen. Eine normale Eingabe in KDNF entspricht[Abbildung in dieser Leseprobe nicht enthalten]. Hier werden alle Belegungen einzeln aufgeführt.

Abbildung in dieser Leseprobe nicht enthalten

Bei dieser Eingabe gibt sowohl der Quine/McCluskey Algorithmus als auch der modi zierte Algorithmus alle Primimplikanten [Abbildung in dieser Leseprobe nicht enthalten] aus.

Abbildung in dieser Leseprobe nicht enthalten

Wie vom Benutzer direkt das Minimalpolynom [Abbildung in dieser Leseprobe nicht enthalten]ab eingegeben, so gibt der modi zierte Algorithmus auch dieses aus. Während der Quine/McCluskey Algorithmus die Eingabe nicht akzeptiert und auf eine KDNF besteht und so alle Primimplikanten ausgeben würde.

Abbildung in dieser Leseprobe nicht enthalten

Gibt der Benutzer jedoch ein Polynomabc [Abbildung in dieser Leseprobe nicht enthalten] ein, das ein unnötig aus Literalen zusammengefasstes Monom enthält, so gibt der modi zierte Algorithmus ein suboptimale Lösung und im schlechtesten Fall alle Primim- plikanten aus.

Abbildung in dieser Leseprobe nicht enthalten

Übersicht über die Unterschiede:

Abbildung in dieser Leseprobe nicht enthalten

2.2.6 Exkurs Doppeltes Produkt

Für die Berechnung der Primimplikantenmenge existieren mehrere Algorith- men. Ein sehr einfacher, wenn auch schwer nachvollziehbarer, ist der Doppel- tes Produkt Algorithmus. Auf eine beliebige DNF werden folgende Schritte angewendet.

dnfBerechnen();

reduzieren();

dualieren();

dnfBerechnen();

reduzieren();

dualieren();

dnfBerechnen();

reduzieren();

Die duale Funktion [Abbildung in dieser Leseprobe nicht enthalten]. Falls f eine DNF ist, so hat die duale Funktion von f das Aussehen einer KNF. Die duale Funktion von fd ergibt wieder f selbst. Der Algorithmus besteht nur aus wenigen Schritten, er besitzt aber trotzdem eine exponentielle Laufzeit, da das ausmultiplizieren einer Funktion in KNF zu einer DNF mit hohem Aufwand verbunden ist. Dieser Algorithmus ist durch seine strikte Abarbeitung langsamer als der Quine/McCluskey und sollte nur zu Anschauungszwecken gewählt werden.

Kapitel 3 Generierung der Ausgabe

3.1 Ausgabemöglichkeiten

Die Möglichkeiten der Ausgabe sollen kurz durch folgendes Schema verdeut- licht werden. Durch die Auswahl einer gegebenen JGIFT Datenstruktur er-

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.1: Code Generierung Überblick

folgt die Umwandlung dieser in ein spezielles Java Objekt. Gleichzeitig ö net sich ein graphisches User Interface, welches neben der Auswahl ob LOG/iC oder Ansi-C Code generiert werden soll noch weitere Auswahlmöglichkeiten an den Nutzer stellt.

3.2 User Interface

In der Gesamtheit betrachtet stellt sich das graphische User Interface folgen- dermaÿen dar. Zu erkennen sind hier die vier zu de nierenden Kernattribute.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.2: User Interface

Unter Ausgabeformat lässt sich auswählen, ob man Ansi-C oder LOG/iC Code, als Float Table oder als Gleichungsdarstellung, generieren will. Unter Minimierung wird eine Auswahl geboten, ob der zu erzeugende Code mini- miert werden soll und ob bei einer eventuellen Minimierung die don't care Be- dingungen in h* dazu mitbenutzt werden sollen. Unter Typ/Prozessor be-ndet sich die Auswahl des PLD-Typ (Programmable Logic Device - Typ) für LOG/iC (DCB FlowTable / Equations) beziehungsweise des Prozessors für den zu erzeugenden Ansi-C Code. Hier wurden bisher nur das GAL16V8 - PLD und der 486 -Microprozessor initialisiert. Wie bereits in der Gra k dar- gestellt, lässt sich im Textfeld Dateiname der Prä x für die zu erzeugenden Dateien benennen, der jeweilige Su x wird automatisch erzeugt. Mit OK bestätigt man die Auswahl und beginnt den Codegenerierungsprozess. Eine kleine Bemerkung an dieser Stelle: Der erzeugte Output wird in das selbe Verzeichnis gespeichert, in der auch die JGIFT-Datenstruktur zu nden ist.

3.3 LOG/iC Codegenerierung

Bei der Erzeugung der LOG/iC Dateien wurden spezielle Templates benutzt, die um jeweilige automatenabhängige variable Informationen ergänzt wurden. Grundsätzlich werden immer zwei Dateien erzeugt, wobei diese lediglich aus ASCII-Zeichen aufgebaut sind.

subsection*.ddv Datei Als erste Datei soll hier die *.ddv erklärt werden, welche die logikbausteinabhängigen Informationen enthält.

Beispiel: (beispiel.ddv)

*IDENTIFICATION

automatisch generiertes File aus /ModView/test.jgiftxmlstatesmodule

*PLD

TYPE=GAL16V8;

*PINS

reset = 2;

x0 = 3;

x1 = 4;

x2 = 5;

x3 = 6;

y0 = 15;

y1 = 16;

z = 17;

*END

Anhand dieses Beispieles lässt sich die Struktur der *.ddv -Dateien gut er- klären. Schlüsselattribute innerhalb der Datei werden mit vorangestelltem

* dargestellt. Innerhalb des Schlüssels IDENTIFICATION ist Platz für Kommentare vorgesehen, wie zum Beispiel Author oder Herkunft der Da- tei. Unter PLD ist der PLD Typ de niert, der durch das User Interface de niert wird. Unter dem Schlüssel PINS ndet sich die Pinbelegung der Logikeinheit. An dieser Stelle ist zu bemerken das der Pin1 nicht de niert wird (meist für Taktgeber vorgesehen) und dadurch für unseren GAL16V8 aus dem Beispiel die Pins 2-17 de niert werden können. Die Eingänge werden von zwei aufwärts de niert, während die Ausgänge von 17 abwärts de niert werden. Es ist darauf zu achten das die Anzahl der Eingangsvariablen und die Anzahl der Ausgangsvariablen nicht die Gesamtanzahl der Pins des Lo- gikelementes übersteigt. Das Ende der Datei wird mit dem Schlüssel END gezeigt.

subsection*.dcb Datei Eine *.dcb -Datei ist grundsätzlich in zwei Bereiche gegliedert, einen Deklarationsbereich und einen Logikbereich. Es ist wei- terhin möglich die Datei auf zwei verschiedene Arten zu generieren. Zum einen als FLOW-TABLE und zum anderen als BOOLEAN-EQUATIONS (Bool'sche Gleichungen). Eine Überprüfung ob es sich bei dem Automa- ten um einen Mealy- oder Moore-Automaten handelt erfolgt selbstständig, dementsprechend wird jeweils ein unterschiedlicher Output erzeugt, der das Moore- bzw. Mealyverhalten des Automaten berücksichtigt. Folgende Gra-fik soll die Struktur einer Mealy-Beispieldatei aufzeigen und gleichzeitig erklären. Schlüsselattribute sind wieder mit vorangestelltem * de niert.

Abbildung in dieser Leseprobe nicht enthalten

Für nähere Erklärungen zu dieser Thematik sei an [Spez06] verwiesen.

3.4 Ansi-C Codegenerierung

Bei der Erzeugung der Ansi-C Dateien wurden ebenfalls spezielle Templa- tes benutzt, die um jeweilige automatenabhängige variable Informationen ergänzt wurden. Grundsätzlich werden zwei Header Dateien (eine für Hard- ware und eine für Automaten Spezi kation) und drei Code Dateien (für Input/Output, für eigentliche Zustandsmaschine und für Programmablauf ) erzeugt. Besonderes Augenmerk wurde darauf gelegt, dass eine Trennung von Automaten- und Hardwarespezi k erfolgt, dass eine einheitliche Kommen- tarsprache verwendet wird, dass selbsterklärender Variablen und Methoden- namen benutzt werden, dass keine globalen Variablen benutzt werden und eine Übergabe von Variablen als Parameter von Methode zu Methode er- folgt. Es wurde auch auf Besonderheiten der Ansi-C Compiler geachtet, da es zum Beispiel keinen eigenen Boolean-Datentyp im lcc gibt.

Ein ganz wichtiger Punkt, der noch erwähnt werden sollte ist, dass man sich Gedanken um die Vermeidung von Inkonsistenzen gemacht hat, indem man alle Hardware-Inputbelegungen erst in einen Vektor einliest, bevor man mit diesen weiterarbeitet. Auch die Outputvariablen werden erst komplett fertig berechnet und in einem Vektor gespeichert, bevor sie an die Hard- wareoutputs angelegt werden. Hiermit ist es unmöglich, dass sich während einer Zustands- oder Ausgabeberechnung, sich ein ändernder Input auf die aktuelle Berechnung negativ auswirkt.

3.4.1 Erklärungen Ansi-C Dateien

Nachfolgend eine kurze Erklärung der einzelnen Dateien:

- *.h - de niert Hardware Input-/Output-Ports

- *_fsm.h - spezielle automatenabhängige De nitionen (zB. Anzahl

Inputs / Anzahl Outputs)

- *_fsm.c - enthält Ausgabe- und Zustandsüberführungsfunktion

- *_io.c - enthält In/Output-Vektor Deklaration, sowie die Methoden einlesen der HW-Inputs in die Inputvektoren und erzeugen der HWOutputs aus den Outputvektoren

- *_hw.c - enthält eigentlichen Programmablauf inklusive Endlosschlei- fe

3.4.2 Erklärungen Ansi-C Methoden Einige wichtige Methoden:

- hw_get_input(pInput); - Hardware Input-Port Belegungen in Input- vektor schreiben

- state = get_next_state(pInput, state); - Zustandsüberführungsfunk- tion, aus gegebenem Inputvektor und aktuellem Zustand berechnet sich neuer Zustand

- set_output(pInput, pOutput, state); - Ausgabefunktion, aus aktuel- lem Zustand (und ggf. aktuellem Inputvektor - Mealy) berechnet sich der Outputvektor.

- hw_set_output(pOutput); - setzt Outputvektorbelegungen an die Hardware Output-Ports

Kapitel 4 Demo am Beispiel + Vorführung

Sehen wir uns nun ein Beispiel an. Dazu werden wir die Pumpensteuerung aus dem Schaltsysteme-Praktikum benutzen.

4.1 Einführung des Beispiels

In diesem Beispiel geht es darum ein Pumpensystem zu steuern. Dieses Pum- pensystem besteht aus zwei Pumpen und einem Wasserbehälter. Der Was- serbehälter besitzt noch ein Ventil, durch das Wasser ab ieÿt, so dass der Wasserspiegel sinkt, wenn die Pumpen nicht arbeiten. Die Pumpen sollen den Wasserpegel möglichst konstant halten. Das heiÿt sinkt der Wasserspie- gel zu stark, pumpen beide Pumpen gleichzeitig Wasser in den Behälter. Ist er zu hoch, pumpt keine der Pumpen. Im mittleren Bereich läuft jeweils eine Pumpe. Damit nicht eine Pumpe mehr beansprucht wird als die andere, sol- len sich die Pumpen untereinander abwechseln. Das heiÿt: solange sich der Pegel im mittleren Bereich be ndet, pumpt dieselbe Pumpe. Sobald aber beide Pumpen gleichzeitig laufen, und dann der Pegel wieder in den mitt- leren Bereich steigt, soll die andere Pumpe allein pumpen. Dasselbe gilt für den Fall, dass zwischendurch beide Pumpen aus sind.

Dazu verfügt das System über 4 Sensoren in verschiedenen Höhen, die messen, ob das Wasser bis zu ihnen hochreicht. x0 ist der unterste Sensor, x1 und x2 die beiden mittleren Sensoren und x3 der oberste Sensor, der nur aktiviert wird, wenn das Gefäÿ voller Wasser ist.

Die genaue Arbeitsweise des Systems sieht wie folgt aus: Wie nehmen der Einfachheit halber an, der Behälter anfangs vollständig mit Wasser gefüllt ist. Das System könnte aber auch in jedem anderen Zustand starten. Nur für unsere Betrachtungen ist das unser Ausgangspunkt. In diesem Zustand sind beide Pumpen aus, denn der Wasserspiegel be ndet sich über dem Soll- Wasserspiegel (welcher zwischen den Sensoren x1 und x2 liegt). Also pumpen

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4.1: Aufbau der Pumpensteuerung

die Pumpen kein zusätzliches Wasser dazu und der Wasserspiegel sinkt. So- lange Sensor x2 noch mit Wasser bedeckt ist, ändert sich nichts. Sobald aber das Wasser unter x2 sinkt, springt die erste Pumpe an und pumpt Wasser in den Behälter. Sinkt das Wasser dann noch weiter, bis Sensor x0 auch nicht mehr vom Wasser bedeckt wird, dann schaltet sich auch die zweite Pumpe ein. Nun laufen beide Pumpen solange bis der Wasserspiegel wieder über x1 steigt. Dann schaltet sich eine Pumpe ab und es läuft wieder nur eine Pumpe. Hierbei ist wichtig, dass nun die andere Pumpe läuft, als die die als letztes allein lief.

Der vollständige Automatengraph sieht wie folgt aus:

Die Kodierung der Zustände geschieht in der Reihenfolge z2, z1, z0, das heiÿt im Zustand 100 ist z2 = 1, z1 = 0, z0 = 0. Die dazugehörige XML-Datei ist im Anhang zu nden.

4.2 Minimieren ohne h*

4.2.1 manuelles Nachvollziehen des Beispiels

Nun lesen wir per Hand die z und y-Gleichnungen aus dem Automatengraphen aus. Das ergibt folgenden Gleichungen:

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4.2: Automatengraph der Pumpensteuerung

Abbildung in dieser Leseprobe nicht enthalten

Das ergibt minimiert:

Abbildung in dieser Leseprobe nicht enthalten

Das Minimieren geschieht hier einfach durch jeweiliges Kürzen zweier Monome, die sich nur an einer Stelle unterscheiden. So funkioniert auch der QuineMcCluskey-Algorithmus.

4.2.2 Vergleich mit den Ergebnissen des JGIFT-Systems

Das ist das Ergebnis, welches das JGIFT-System erzeugt, wenn ohne h* minimiert werden soll:

*BOOLEAN-EQUATIONS

Abbildung in dieser Leseprobe nicht enthalten

Bei Überprüfung dieser Zeilen, sieht man, dass das Ergebnis mit dem per Hand berechnteten Ergebnis übereinstimmt.

4.3 Minimieren mit h*

4.3.1 Überlegungen zu h*

Bei der Minimierung mit h* kann man zusätzliche Informationen hinzuziehen. Belegungen von Eingangsvariablen, die nicht vorkommen können, dürfen zur Minimierung beliebig herangezogen werden. Zum Beispiel sehen wir uns folgenden kleinen Automaten an.

Dort ergibt sich für z:

Abbildung in dieser Leseprobe nicht enthalten

Das lässt sich dies nicht weiter kürzen. Wenn man aber nun weiÿ, dass die Belegung xy nicht vorkommen kann, lässt sich doch noch eine Kleinigkeit

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4.3: Beispielgraph für h*

kürzen. Dann kann man in die z-Gleichung nochxyz mit hineinnehmen. Da es zu dieser Belegung niemals kommen wird, ändert dass nichts am Verhalten des Automaten. Dann ergibt sich:

Abbildung in dieser Leseprobe nicht enthalten

Das sieht vieleicht nicht nach einer so starken Verbesserung aus, das ist aber auch nur ein kleines Beispiel. Bei der Pumpensterung ist h* (die Menge der nicht vorkommenden Belegung) groÿ. Es gibt insgesamt 16 mögliche Belegun- gen für die 4 Eingangsvariablen. Davon sind aber nur 5 in unserem System wirklich möglich, da das Wasser nur stetig von unten nach oben steigt. Es müssen also auch die Sensoren von unten nach oben durchgängig von Wasser bedeckt sein. Es kann nicht vorkommen, das über einem trockenen Sensor wieder ein nasser Sensor kommt. Es ergeben sich als sinnvolle Belegungen nur:

Abbildung in dieser Leseprobe nicht enthalten

Das erö net viele Möglichkeiten, die anderen sinnlosen Belegungen einzu- beziehen.

4.3.2 Ergebnis und Vergleich

Das ist das Ergebnis, welches das JGIFT-System erzeugt, wenn mit h* minimiert werden soll:

*BOOLEAN-EQUATIONS

Abbildung in dieser Leseprobe nicht enthalten

Nun übeprüfen wir, ob diese Gleichung ein äquivalentes Verhalten des Automaten beschreiben. Wir betrachten beispielhaft den Term für s_k0_1. Die ersten vier Summanden sind gleich wie bei der Minimierung ohne h*. Der letzte Term ist neu: s_k0_1 & s_k0_3 & /x_sen_1. Sieht man sich nun den Automatengraph an, stellt man fest, dass es Belegungen gibt, bei denen dieser Term in einen Zusatnd führt in dem s_k0_1=0 ist. Be ndet man sich im Zustand 101 und hätte eine der folgenden Belegungen:

Abbildung in dieser Leseprobe nicht enthalten

Dann würde man laut Automatengraph in den Zustand 000 wechseln, was mit unserer Gleichung nicht übereinstimmt. Sieht mansich aber die fraglichen 4 Belegungen an, stellt man fest, dass diese alle in h* liegen. Somit ndet ein Zustandswechsel in einen falschen Zustand nicht statt. Ähnliche Be- trachtungen ergeben sich bei den anderen Gleichungen. Also repräsentieren diese Gleichungen einen Automaten, der auf real vorkommenden Eingaben das gleiche Verhalten zeigt, wie der ursprüngliche Graph, obgleich es kein identischer Graph ist.

Kapitel 5 Ausblick

Das JGIFT-System ist ein sehr komplexes Werkzeug zur Manipulation und Simulation von endlichen Automaten. Unser Beitrag war es die Ausgabe der Automaten in verschiedenen Formaten zu realisieren. Einerseits soll die Möglichkeit bestehen Mikrocontroller mittels LogIC so zu programmieren, dass sie sich wie die vorgegebenen Automaten verhalten. Andererseits soll es möglich sein C-Code automatisch zu generieren, der ebenfalls das Verhalten des Automaten abbildet.

Es gibt allerdings noch viel zu tun in diesem Projekt. Die Eingabe der Automaten soll intuitiv möglich sein. Bis jetzt müssen die Automaten im spezi zierten XML-Format vorliegen. Später sollen die Automaten einfach zusammen-klick -bar sein. Das beinhaltet dann auch die Möglichkeit diese Automaten leicht zu manipulieren. Zudem soll man die Automaten simulieren können. Es werden noch Analyse- und Testverfahren integriert werden.Mit all diesen Aufgabenstellungen befassen sich andere Haupt- und Projektseminare, die zur Zeit im Fachgebiet IHS laufen.

Später soll dann auch die Möglichkeit zu einem Online-Praktikum bestehen. Es gibt also noch zahlreiche Herausforderungen bei der Vervollkommnung des JGIFT-Systems.

Anhang A

XML-Datei für die Pumpensteuerung

Abbildung in dieser Leseprobe nicht enthalten

Abbildungsverzeichnis

2.1 Baumstruktur der Gleichung

2.2 Baum nach Negatoren-Bindung

2.3 Schema des Umhängens zur Bildung der DNF

2.4 Baum nach DNF-Bildung

3.1 Code Generierung Überblick

3.2 User Interface

4.1 Aufbau der Pumpensteuerung

4.2 Automatengraph der Pumpensteuerung

4.3 Beispielgraph für h*

Literaturverzeichnis

[Zufall05] Erik Zufall 2005. Untersuchungen zu Realisierungsmöglichkeiten von ferngesteuerten Praktika über das Internet. TU Ilmenau

[Blo06] Maik Bloÿ 2006. Automatennetzentwurf im Team mit JGIFT. TU Ilmenau

[SV2] Fachgebiet IHS. Ergänzung zur Praktikumsanleitung - Schaltsysteme Versuch 2. TU Ilmenau

[Spez06] Fachgebiet IHS 2006. Dateiformatsspezi kationen JGift-XML- Module . TU Ilmenau

[Ecl06] http://www.eclipse.org/ Eclipse - an open development platform.