Inhaltsverzeichnis

1  Projektvorstellung  4

1.1  Einleitung  4

1.2  Aufgabe  5

2  JGIFT Datenstruktur  6

2.1  XML  6

2.2  Umformung und Minimierung (Bäume)  8

2.2.1  Eingabeformat  8

2.2.2  Baumstruktur - Wie sieht eine eingelesene Gleichung  

aus  ?  9

2.2.3  DNF erzeugen  9

2.2.4  Reduzieren  10

2.2.5  Quine/McCluskey und die Modikation  12

2.2.6  Exkurs Doppeltes Produkt  15

3  Generierung der Ausgabe  16

3.1  Ausgabemöglichkeiten  16

3.2  User Interface  17

3.3  LOG/iC Codegenerierung  18

3.4  Ansi-C Codegenerierung  19

3.4.1  Erklärungen Ansi-C Dateien  20

3.4.2  Erklärungen Ansi-C Methoden  20

4  Demo am Beispiel Vorführung  21

4.1  Einführung des Beispiels  21

4.2  Minimieren ohne h  22

4.2.1  manuelles Nachvollziehen des Beispiels  22

4.2.2  Vergleich mit den Ergebnissen des JGIFT-Systems  23

4.3  Minimieren mit h  24

4.3.1  Überlegungen zu h  24

4.3.2  Ergebnis und Vergleich  25

5  Ausblick  28

2

A XML-Datei für die Pumpensteuerung 29

3

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 graschen und textuellen Spezikation

• einer eigenen Simulationsumgebung,

• Prüfalgorithmen zum erkennen und lokalisieren von Fehlern (zB. Verikation),

• Möglichkeiten der Codegenerierung für andere Hard- und Software-plattformen

• sowie Netzwerkunterstützung.

gelegt. Im Zuge dieser Anforderungen entstand unter andrem das Experimentalsystems GIFT (Graphical Interactive FSM-Tool) welches bis heute im Einsatz ist. Ein nicht zu unterschätzender Nachteil des bisherigen Entwurfsystems ist jedoch die Abhängigkeit vom Betriebsystem. Derzeit läuft GIFT lediglich auf Unix/Linux-Systemen, was Benutzern anderer Betriebsysteme (vor allem Windows aber auch MAC-OS, u.a.) den Umgang unmöglich 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 Experimentalsystems GIFT zum JGIFT (auf Java Virtual Machine aufsetzendes GIFT), welches dann Plattform unabhängig ist. Dabei ergibt sich die

4

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 geben diesen Automatengraphen via graschem Userinterface

• zu Minimieren (mit und ohne h*)

• in LogIC(Flow-Table oder Gleichungsdarstellung) oder C-Code zu konvertieren,

• die Output-Hardware für den erzeugten Code zu denieren 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ügigen Dokumentation des GIFT Systems, war es sehr wenig beziehungsweise gar nicht möglich auf GIFT-Quellcode zurückzugreifen. Desweiteren führte eine Internetrecherche hierzu ebenfalls nicht zum gewünschten Erfolg, was zur Folge hatte, dass wir mit unserer Implementierung bei Null beginnen 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 Compiler-Systeme lcc-win32 (für Ansi-C) und LOG/iC2 (für LOG/iC) benutzt.

5

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 korrekt 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 wohl-geformt 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 XML-Datei können alle möglichen Dinge stehen. Durch Tags wird festgelegt wie das, was in dem Tag steht zu interpretieren ist.

6

Zum Beispiel liegen im Tag alle Informationen zum Interface

des Automaten. Das sind vorhandene Zustände des Automaten, Eingangsvariablen und Ausgangsvariablen des Automaten. Jedes Tag kann Untertags

besitzen, um die Inhalte noch besser zu trennen. Unter interface zum Beispiel , , . So ist der komplette

Automat mit Zustandsübergängen eindeutig deniert. 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-Spezikation gibt auch syntaktisch einige Dinge vor:

• Bei allen Werten von Parametern und Dateninhalten von Tags, wird nicht zwischen Groÿ- und Kleinschreibung unterschieden.

• Für benutzerdenierte Variablennamen gelten folgende Einschränkungen 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
-Tags zu

realisieren.

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

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

7

• Jeder benutzerdenierte Variablenname darf nur einmal innerhalb eines Moduls auftauchen.

• Tags, die Listenelemente darstellen, werden durch einen Schlüssel spezialisiert. Dieser darf innerhalb der umgebenden Liste nur einmal auftauchen.

• 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 Um-formen 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 modizierte Algorithmus berechnet aus einer beliebigen Gleichung eine Teilmenge der Primimplikanten. Ein optimal minimiertes Polynom besteht aus einer Teilmenge aller Primimplikanten einer Gleichung, diese Teilmenge wird mittels 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 Gleichung als String übergeben. Das Eingabeformat richtet sich nach der XML Spezikation für Automatengraphen. Es ist eigenständig und unabhängig von der XML Spezikation 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 Spezikation für Automatengraphen erfüllt

8

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 linken 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 Teilbaum bleibt leer (null). Beispiel: (a ∧ ¬(b ∧ ¬c ∨ d)) ∨ ¬(a ∧ ¬d)

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

9

folgende zwei Schritte notwendig.

Im ersten Schritt werden alle Negatoren an die Variablen gebunden. Dafür wird jeder einzelne Negator (¬) entfernt und der rechte Teilbaum um eine Ebene nach oben verschoben. Zusätzlich werden alle Operatoren im Unterbaum vertauscht. Aus UND (∧) wird ODER (∨) und aus ODER (∨) wird UND (∧). Alle nicht negierten Variablen werden negiert und andersrum. Diese Prozedure entspricht der maximalen Anwendung des DeMorgan Gesetzes. Beispiel: Aus (a ∧ (b ∧ c ∨ d)) ∨ (a ∧ d) wird (a ∧ ((b ∨ c) ∧ d)) ∨ (a ∨ d).

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.

Beispiel: Aus (a ∧ ((b ∨ c) ∧ d)) ∨ (a ∨ d) wird (a ∧ (b ∧ d) ∨ (a ∧ (c ∧ d)) ∨ (a ∨ d)

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:

10

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

Abbildung  2.4: Baum nach DNF-Bildung  

11

• 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 Gleichung 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 Modikation

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 zusammengekü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ätzliche 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 modizierte Algorithmus gibt statt des Minimalpolynoms nun eine Primimplikantenteilmenge zurückgibt und bevorzugt die Primimplikanten, die bereits in der Eingabemenge vorhanden waren. Dadurch kann es vorkommen, das der modizierte Algorithmus ein Minimalpolynom berechnet, während der

12

Quine/McCluskey Algorithmus mit der Ausgabe aller Primimplikanten kein Minimalpolynom ausgibt.

Der modizierte Algorithmus nutzt, dass die Eingabe durch den Menschen schon voroptimiert sein kann. Ist die Eingabe schlecht gewählt oder entspricht der KDNF, so berechnet der modizierte Algorithmus auch die komplette Primimplikantenmenge. Im Falle der Eingabe einer DNF gibt der modizierte Algorithmus alle Primimplikanten oder eine suboptimale Teilmenge aller Primimplikanten oder das Minimalpolynom (optimale Teilmenge) aus.

13

Die folgenden Kanaugh-Pläne sollen die Modikation verdeutlichen. Eine normale Eingabe in KDNF entspricht abc ∨ abc ∨ abc ∨ abc. Hier werden alle Belegungen einzeln aufgeführt.

Bei dieser Eingabe gibt sowohl der Quine/McCluskey Algorithmus als auch der modizierte Algorithmus alle Primimplikanten bc ∨ ac ∨ ab aus.

Wie vom Benutzer direkt das Minimalpolynom bc∨ab eingegeben, so gibt der modizierte 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.

Gibt der Benutzer jedoch ein Polynom abc ∨ ac ∨ abc ein, das ein unnötig aus Literalen zusammengefasstes Monom enthält, so gibt der modizierte Algorithmus ein suboptimale Lösung und im schlechtesten Fall alle Primimplikanten aus.

Übersicht über die Unterschiede:

2.2.6 Exkurs Doppeltes Produkt

Für die Berechnung der Primimplikantenmenge existieren mehrere Algorithmen. Ein sehr einfacher, wenn auch schwer nachvollziehbarer, ist der Doppeltes Produkt Algorithmus. Auf eine beliebige DNF werden folgende Schritte angewendet. dnfBerechnen(); reduzieren(); dualieren(); dnfBerechnen(); reduzieren(); dualieren(); dnfBerechnen(); reduzieren();

Die duale Funktion f d von f ist f d = ¬f (¬x). Falls f eine DNF ist, so hat die duale Funktion von f das Aussehen einer KNF. Die duale Funktion von f d 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.

15

Kapitel 3

Generierung der Ausgabe

3.1 Ausgabemöglichkeiten

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

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.

16

3.2 User Interface

In der Gesamtheit betrachtet stellt sich das graphische User Interface folgendermaÿen dar. Zu erkennen sind hier die vier zu denierenden Kernattribute.

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 minimiert werden soll und ob bei einer eventuellen Minimierung die don't care Bedingungen in h* dazu mitbenutzt werden sollen. Unter Typ/Prozessor bendet 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 Grak dargestellt, lässt sich im Textfeld Dateiname der Präx für die zu erzeugenden Dateien benennen, der jeweilige Sux 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.

17

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 erklä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 Datei. Unter PLD ist der PLD Typ deniert, der durch das User Interface deniert wird. Unter dem Schlüssel PINS ndet sich die Pinbelegung der Logikeinheit. An dieser Stelle ist zu bemerken das der Pin1 nicht deniert wird (meist für Taktgeber vorgesehen) und dadurch für unseren GAL16V8 aus dem Beispiel die Pins 2-17 deniert werden können. Die Eingänge werden von zwei aufwärts deniert, während die Ausgänge von 17 abwärts deniert werden. Es ist darauf zu achten das die Anzahl der Eingangsvariablen und die Anzahl der Ausgangsvariablen nicht die Gesamtanzahl der Pins des Logikelementes übersteigt. Das Ende der Datei wird mit dem Schlüssel END gezeigt.

18

subsection*.dcb Datei Eine *.dcb-Datei ist grundsätzlich in zwei Bereiche gegliedert, einen Deklarationsbereich und einen Logikbereich. Es ist weiterhin 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 Automaten 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 Grak soll die Struktur einer Mealy-Beispieldatei aufzeigen und gleichzeitig erklären. Schlüsselattribute sind wieder mit vorangestelltem * deniert.

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 Templates benutzt, die um jeweilige automatenabhängige variable Informationen ergänzt wurden. Grundsätzlich werden zwei Header Dateien (eine für Hardware und eine für Automaten Spezikation) 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 Hardwarespezik erfolgt, dass eine einheitliche Kommentarsprache verwendet wird, dass selbsterklärender Variablen und Methodennamen benutzt werden, dass keine globalen Variablen benutzt werden und eine Übergabe von Variablen als Parameter von Methode zu Methode erfolgt. Es wurde auch auf Besonderheiten der Ansi-C Compiler geachtet, da es zum Beispiel keinen eigenen Boolean-Datentyp im lcc gibt.

19

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 Hardwareoutputs 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 - deniert Hardware Input-/Output-Ports

• *_fsm.h - spezielle automatenabhängige Denitionen (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 HW-Outputs aus den Outputvektoren

• *_hw.c - enthält eigentlichen Programmablauf inklusive Endlosschleife

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ührungsfunktion, aus gegebenem Inputvektor und aktuellem Zustand berechnet sich neuer Zustand

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

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

20

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 Pumpensystem besteht aus zwei Pumpen und einem Wasserbehälter. Der Wasserbehälter besitzt noch ein Ventil, durch das Wasser abieÿ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 Wasserspiegel 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, sollen sich die Pumpen untereinander abwechseln. Das heiÿt: solange sich der Pegel im mittleren Bereich bendet, pumpt dieselbe Pumpe. Sobald aber beide Pumpen gleichzeitig laufen, und dann der Pegel wieder in den mittleren 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. x 0 ist der unterste Sensor, x 1 und x 2 die beiden mittleren Sensoren und x 3 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 bendet sich über dem Soll-Wasserspiegel (welcher zwischen den Sensoren x 1 und x 2 liegt). Also pumpen

21

die Pumpen kein zusätzliches Wasser dazu und der Wasserspiegel sinkt. Solange Sensor x 2 noch mit Wasser bedeckt ist, ändert sich nichts. Sobald aber das Wasser unter x 2 sinkt, springt die erste Pumpe an und pumpt Wasser in den Behälter. Sinkt das Wasser dann noch weiter, bis Sensor x 0 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 x 1 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 z 2 , z 1 , z 0 , das heiÿt im Zustand 100 ist z 2 = 1, z 1 = 0, z 0 = 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:

z 2 = z 2 z 1 z 0 x 2 ∨ z 2 z 1 z 0 x 3 ∨ z 2 z 1 z 0 x 2 ∨ z 2 z 1 z 0 x 1 ∨ z 2 z 1 z 0 x 3 x 0 ∨ z 2 z 1 z 0 x 0 ∨ z 2 z 1 z 0 x 1

22

Abbildung 4.2: Automatengraph der Pumpensteuerung

z 1 = z 2 z 1 z 0 x 0 ∨ z 2 z 1 z 0 x 1 ∨ z 2 z 1 z 0 x 1 ∨ z 2 z 1 z 0 x 0

z 0 = z 2 z 1 z 0 x 2 ∨ z 2 z 1 z 0 x 1 ∨ z 2 z 1 z 0 x 2 ∨ z 2 z 1 z 0 x 3 x 0 ∨ z 2 z 1 z 0 x 1 ∨ z 2 z 1 z 0 x 0 ∨ z 2 z 1 z 0 x 1 ∨z 2 z 1 z 0 x 3 x 0 y 1 = z 2 z 1 z 0 ∨ z 2 z 1 z 0 ∨ z 2 z 1 z 0 y 0 = z 2 z 1 z 0 ∨ z 2 z 1 z 0 ∨ z 2 z 1 z 0

Das ergibt minimiert:

z 2 = z 2 z 1 z 0 x 3 ∨ z 2 z 1 z 0 ∨ z 2 z 1 z 0 x 1 ∨ z 2 z 1 z 0 x 0 ∨ z 2 z 1 z 0 x 1 ∨ z 2 z 1 x 3 z 1 = z 2 z 1 z 0 x 1 ∨ z 2 z 1 z 0 x 1 ∨ z 1 z 0 x 0

z 0 = z 1 z 0 x 2 ∨ z 1 z 0 x 3 x 0 ∨ z 2 z 0 x 3 ∨ z 2 z 1 z 0 x 1 ∨ z 2 z 1 z 0 x 0 ∨ z 2 z 1 z 0 y 1 = z 2 z 0 ∨ z 2 z 1 z 0 y 0 = z 2 z 1 z 0 ∨ z 2 z 1 z 0 ∨ z 2 z 1 z 0

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:

23

*BOOLEAN-EQUATIONS

s_k0_1 := reset & (/s_k0_1 & /s_k0_2 & s_k0_3 & x_sen_3 + /s_k0_1 & s_k0_2 & /s_k0_3 & x_sen_1 + s_k0_1 & /s_k0_2 & s_k0_3 & /x_sen_0 + s_k0_1 & s_k0_2 & s_k0_3 & /x_sen_1 + s_k0_1 & /s_k0_2 & /s_k0_3 + s_k0_1 & /s_k0_2 & /x_sen_3); s_k0_2 := reset & (/s_k0_1 & s_k0_2 & /s_k0_3 & /x_sen_1 + s_k0_1 & s_k0_2 & s_k0_3 & /x_sen_1 + /s_k0_2 & s_k0_3 & /x_sen_0); s_k0_3 := reset & (/s_k0_1 & s_k0_2 & /s_k0_3 & x_sen_1 + s_k0_1 & /s_k0_2 & s_k0_3 & /x_sen_0 + /s_k0_2 & /s_k0_3 & /x_sen_2 + /s_k0_2 & s_k0_3 & /x_sen_3 & x_sen_0 + s_k0_1 & s_k0_2 & s_k0_3 + s_k0_1 & s_k0_3 & /x_sen_3); y_pump_0 = /s_k0_1 & /s_k0_2 & s_k0_3 + /s_k0_1 & s_k0_2 & /s_k0_3 + s_k0_1 & s_k0_2 & s_k0_3; y_pump_1 = /s_k0_1 & s_k0_2 & /s_k0_3 + s_k0_1 & s_k0_3;

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: z = xyz ∨ xyz

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

24

kürzen. Dann kann man in die z-Gleichung noch xyz mit hineinnehmen. Da

es zu dieser Belegung niemals kommen wird, ändert dass nichts am Verhalten des Automaten. Dann ergibt sich:

z = yz ∨ xyz

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 Belegungen 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:

Das erönet viele Möglichkeiten, die anderen sinnlosen Belegungen einzubeziehen.

4.3.2 Ergebnis und Vergleich

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

25

*BOOLEAN-EQUATIONS

s_k0_1 := reset & (/s_k0_1 & /s_k0_2 & s_k0_3 & x_sen_3 + /s_k0_1 & s_k0_2 & /s_k0_3 & x_sen_1 + s_k0_1 & /s_k0_2 & /x_sen_3 + s_k0_1 & /s_k0_2 & /s_k0_3 + s_k0_1 & s_k0_3 & /x_sen_1); s_k0_2 := reset & (/s_k0_2 & s_k0_3 & /x_sen_0 + /s_k0_1 & s_k0_2 & /s_k0_3 & /x_sen_1 + s_k0_1 & s_k0_3 & /x_sen_0 + s_k0_1 & s_k0_2 & s_k0_3 & /x_sen_1); s_k0_3 := reset & (/s_k0_2 & /s_k0_3 & /x_sen_2 + /s_k0_2 & /x_sen_2 & x_sen_0 + /s_k0_2 & s_k0_3 & /x_sen_3 & x_sen_0 + /s_k0_1 & s_k0_2 & /s_k0_3 & x_sen_1 + s_k0_1 & s_k0_3 & /x_sen_3 + s_k0_1 & s_k0_2 & s_k0_3); y_pump_0 = /s_k0_1 & /s_k0_2 & s_k0_3 + /s_k0_1 & s_k0_2 & /s_k0_3 + s_k0_1 & s_k0_2 & s_k0_3; y_pump_1 = /s_k0_1 & s_k0_2 & /s_k0_3 + s_k0_1 & s_k0_3;

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. Bendet man sich im Zustand 101 und hätte eine der folgenden Belegungen: x_sen_3x_sen_2x_sen_1/x_sen_0 x_sen_3x_sen_2/x_sen_1/x_sen_0 x_sen_3/x_sen_2x_sen_1/x_sen_0 x_sen_3/x_sen_2/x_sen_1/x_sen_0

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 Betrachtungen ergeben sich bei den anderen Gleichungen. Also repräsentieren

26

diese Gleichungen einen Automaten, der auf real vorkommenden Eingaben das gleiche Verhalten zeigt, wie der ursprüngliche Graph, obgleich es kein identischer Graph ist.

27

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

28

Anhang A

XML-Datei für die Pumpensteuerung

none none Pumpensteuerung
Ansteuerung der Pumpen
Entspricht dem Teilautomaten A0 Wasserstandssensor
mitte, unten

Wasserstandssensor
mitte, oben

Wasserstandssensor
oben Pumpe 0

29

Pumpe 1

Zustand 1 dieses Automaten Zustand 2 dieses Automaten Zustand 3 dieses Automaten

x_sen_3 &amp; x_sen_2 &amp; x_sen_1 &amp; !x_sen_0 #x_sen_3 &amp; x_sen_2 &amp; !x_sen_1 &amp; x_sen_0 #x_sen_3 &amp; !x_sen_2 &amp; x_sen_1 &amp; x_sen_0 #x_sen_3 &amp; x_sen_2 &amp; !x_sen_1 &amp; !x_sen_0 #x_sen_3 &amp; !x_sen_2 &amp; x_sen_1 &amp; !x_sen_0 #x_sen_3 &amp; !x_sen_2 &amp; !x_sen_1 &amp; x_sen_0 #x_sen_3 &amp; !x_sen_2 &amp; !x_sen_1 &amp; !x_sen_0 #!x_sen_3 &amp; x_sen_2 &amp; x_sen_1 &amp; !x_sen_0 #!x_sen_3 &amp; x_sen_2 &amp; !x_sen_1 &amp; x_sen_0 #!x_sen_3 &amp; x_sen_2 &amp; !x_sen_1 &amp; !x_sen_0 #!x_sen_3 &amp; !x_sen_2 &amp; x_sen_1 &amp; !x_sen_0 keine Pumpe aktiv 0

0

eine Pumpe aktiv 0 30

beide Pumpen aktiv 0

keine Pumpe aktiv 1

eine Pumpe aktiv 1

beide Pumpen aktiv 1

32

Abbildungsverzeichnis

2.1 Baumstruktur der Gleichung . . . . . . . . . . . . . . . . . . . 9 2.2 Baum nach Negatoren-Bindung . . . . . . . . . . . . . . . . . 10 2.3 Schema des Umhängens zur Bildung der DNF . . . . . . . . . 11 2.4 Baum nach DNF-Bildung . . . . . . . . . . . . . . . . . . . . 11

3.1 Code Generierung Überblick . . . . . . . . . . . . . . . . . . . 16 3.2 User Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

4.1 Aufbau der Pumpensteuerung . . . . . . . . . . . . . . . . . . 22 4.2 Automatengraph der Pumpensteuerung . . . . . . . . . . . . 23 4.3 Beispielgraph für h* . . . . . . . . . . . . . . . . . . . . . . . 25

33

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. Dateiformatsspezikationen JGift-XML-Module. TU Ilmenau

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

34