Endlicher Automat

(FSM Finite State Machine)

kner 2020

 

 

 

Inhalt

 

1 Grundlagen Kombinatorische Logik (KL)

1.1 Was ist KL

KL bildet Eingangssignale zeitunabhängig auf Ausgangssignale ab

Image1 Eingangsbitmuster erzeugen Ausgangsbitmuster

Image2 
ENCODER   z.B: einfache Datenverschlüsselung

DECODER   z.B: einfache Datenentschlüsselung

 

1.2 Wahrheitstafel WT  und deren Symbole

Wahrheitstafeln sind eine mögliche Beschreibungsform für KL

Verwendete Symbole:

'0' … LOW, '1' … HIGH, '-'  DON'T CARE

3 Eingänge benötigen 8 Zeilen in der WT

Image3

Wenn A=1 dann ist XY=10 unabhängig davon, welche Werte B oder C annehmen.

man sieht: mit Hilfe der DON'T CAREs kann die WT verkürzt geschrieben werden.

Regel: eine Zeile steht für 2N Zeilen, wenn N die Anzahl  der DON'T CARE ist;

 

Vorsicht bei der Minimierung:  als Entwickler kann man hier leicht Fehler machen, man überlässt daher besser der Software diese Aufgabe

 

1.3 Boolsche Algebra

Logikfunktionen lassen sich mit der Boolschen Algebra beschreiben.

Image4Verwendete Symbole:  

Ausgang Q ergibt sich als logische Verknüpfung der Eingänge:

Q= A+B … A OR B (Oder Verknüpfung = Disjunktion)

Q= A*B … A AND B (Und Verknüpfung = Konjunktion)

Q = A … NOT A

 

 

 

1.4 Normalformen

Eine Wahrheitstafel kann in einer von zwei Normalformen angeschrieben werden. Wenn die Ausgangsfunktion Q weniger '1' enthält verwendet man DNF, bei weniger '0' verwendet man KNF  

1.4.1 DNF

Image5

Beachte: für die Realisierung der wird in der letzten Zeile C nicht berücksichtigt.  

A, B, C werden AND verknüpft (Minterm) und im nächsten Schritt OR verknüpft; drei '1' bedeuten drei Minterme.  Für eine 0 in der Wahrheitstafel wird der Eingang im letzten Schritt negiert.

 

 

 

 

1.4.2 KNF

Diese wird verwendet, wenn der Ausgang Q weniger '0' enthält. Sie verhält sich komplementär zur DNF
( 0→1, AND → OR, OR → AND, Programmierung der '1')  

 

Image6

 

1.5 Realisierung der DNF und KNF durch Logikgatter

Image7

Beispiel: Realisierung der folgenden Wahrheitstafel durch Logikgatter

1. KNF für X

2. DNF für Y

3. Schaltung

 

Image8Image9

 

 

2 Grundlagen Sequenzielle Logik (SL)

2.1 Was ist (SL)

Sequenzielle Maschinen durchlaufen nacheinander verschiedene Zustände; Eingangsbitmuster erzeugen unterschiedliche Ausgangs-Bitmuster, je nachdem wann die Eingänge angelegt werden.

(z.B: Computer = SL weil: Taste ‚B‘ hat in einem Computerspiel eine andere Bedeutung als in einer Textverarbeitung)

 

Sequenzielle Logik = Kombinatorische Logik + Speicher

Speicher für Bitmuster: D-Flipflop/Register

Synchrone Sequenzielle Logik: alle Flipflops schalten gleichzeitig (z.B.: mit einer steigenden Taktflanke)

 

2.2 Blockschaltbild Sequenzielle Logik

Image10Die Ausgänge ergeben sich aus den Eingängen E und dem Inhalt des Speichers PS. Das Bitmuster in den Speichern heißt "Gegenwärtiger System-Zustand   (present state PS)".

Am Eingang der Speicher liegt ein Bitmuster an (next state NS), das wie die Ausgänge aus dem present state (PS) und den Eingängen berechnet wird.

Sobald ein Taktsignal an die Speicherzellen gelegt wird, wird dieses Bitmuster abgespeichert. Der Speicher enthält damit den neuen Zustand, das System hat in einen neuen PS geschaltet und bleibt in diesem Zustand bis zum nächsten Takt.

synchrones System = Änderungen nur mit dem Taktschlag

 

Wenn der Speicher an die Versorgungsspannung angeschlossen wird, ist der Inhalt undefiniert. Das System muss daher am Anfang zurückgesetzt werden (RESET).

Asynchrones Reset:  das RESET Signal wirkt sofort, unabhängig vom CLK

Synchrones Reset:  wenn RESET aktiviert wird, muss auf den nächsten Takt gewartet werden, bevor es aktiv wird.

 

 

Image11Die Sequenzielle Logik hat in diesem Beispiel einen Eingangsbus (2 Leiterbahnen), einen Ausgangsbus (5 Leiterbahnen), Next State und Present State Bus (je 3 Leiterbahnen).

 

Im Speicher können daher 23 = 8 verschiedene Bitmuster abgelegt werde = 8 verschiedene States. In jedem der 8 Zustände wirken 2 Eingangssignale und können daher in jedem Zustand 22 = 4 unterschiedliche Bitmuster am Ausgang A erzeugen. Es sind daher 8x4=32 unterschiedliche BItmuster an A möglich.

 

 

 

 

Beispiele für sequenzielle Logik: Zähler, Schieberegister, Steuerungen (Garagentor, Lift, uC)

 

Begriffe für Sequenzielle Logik:

 

2.3 FSM

Man kann sequenzielle Systeme gut durch Zustandsdiagramme (state diagram) beschreiben. Die dadurch beschiebenen Steuerungen werden dann als FSM (finite state machine) bezeichnet.  

2.3.1 Moore Automat

Blockschaltbild und State-Diagramm (Bubble Diagram)

Image12Image13Die Ausgangsbitmuster hängen nur davon ab, in welchem Zustand das System gerade ist (von PS).  

Die Ausgangsbitmuster werden daher in den State-Bubble eingetragen.

 

Die Pfeile beschreiben die Übergänge zwischen den Zuständen (Transition), den Pfeilen gefolgt, wenn ein Taktschlag erfolgt. Die Beschriftung der Pfeile ist die Bedingung  (Condition), unter der dem Pfeil gefolgt wird.

 

Achtung! Die Bedingungen dürfen sich nicht widersprechen, bei einem Taktschlag kann nur einem Pfeil gefolgt werden. Wenn keine Beschriftung existiert heißt das: dem Pfeil wird jedenfalls gefolgt.

 

 

 

Image14 Interpretation

Es gibt 4 Zustände d.h. es werden zwei Speicherzellen (D-Flipflops) benötigt.

Es gibt drei Ausgangssignale, eingetragen in den Bubbles unterhalb der State-Namen

Es gibt zwei Eingangssignale UP und M3, die diese Maschine steuern.

 

Das System ist im Zustand Start (z.B: nach Reset), am Ausgang liegt A="000".  Wenn jetzt M3=UP=1, dann wechselt das System mit dem nächsten Taktschlag nach Z1, wenn M3=0, dann wechselt das System mit dem Takt unabhängig von UP nach Z3 usw.

 

Das System zählt daher bei M3=0 im Takt: 0 – 7 – 0 – 7 -  usw.

Wenn M3=1 und UP=1 ist die Zählfolge: 0 – 2 – 5 – 0 – 2 – 5  usw.

Wenn M3=1 und UP=0 ist die Zählfolge: 0 – 5 – 2 – 5 – 2 – 5  usw.

 

Es handelt sich also um einen umschaltbaren Zähler, der in zwei verschiedenen Modi auf- und abwärts zählen kann.

2.3.2 Mealy Automat

Image16

Image15Bei der Mealy-Maschine hängt das Steuerwort A nicht nur vom aktuellen Systemzustand PS ab, sondern auch von den Eingangssignalen. Wenn das System im Zustand "Start" ist, ist nicht klar, welches Ausgangsbitmuster erzeugt wird, dies hängt zusätzlich von den Eingängen ab. Man schreibt daher die Ausgänge zu den Bedingungen der Transitions.

 

Vorteil der Mealy-Maschine: sie ist der allgemeine Fall, die Moore-Machine ist ein Sonderfall. Meist ist die Moore-Maschine übersichtlicher, benötigt aber mehr Zustände für die gleiche Aufgabe.

3 Beispiele in Hardware

3.1 UP/DOWN Counter (Moore mit 2 Wahrheitstafeln KL1 und KL2)

Image17

 

 

 

 

 

Image18

Image19

 

 

3.2 UP/DOWN Counter (Moore mit 1 Wahrheitstafel)

Image22

Image20Image21

3.3 UP/DOWN Counter (Mealy mit 1 Wahrheitstafel)

Image24
Image25

Image23

3.4 Flanken-Erkennung

Bei der steigenden Flanke des Eingangssignals soll ein Puls ausgegeben werden:

Image26

 

 

 

 

Image27

Aus diesem Timing-Diagramm kann man das State-Diagramm herleiten ...

 

… und dieses in eine Wahrheitstafel übersetzen:

Image28

DNF und KNF:

Image29

Daraus ergibt sich die Gesamtschaltung:

Image30

4 Grundlagen AVR C Programmierung

4.1  Realisierung einer Wahrheitstafel in C

 

Die Wahrheitstafel ist ein Array  (Lookup Table LUT) :

X = Wt[ 3 ]

Dieser Ausdruck liefert ein Bitmuster, das dem Eintrag in die WT an der Position 3 (Bitmuster der Eingangssignale) entspricht.

 

 

 

Beispiel

/* Wahrheitstafel in C

Beachte: Methode 2 benötigt als Datenspeicher für die LUT nur 2 Byte

 

 

ABC|XY          verkürzte Schreibweise  ausführlich:    ABC|XY    ABC|XY

000|11                                                 000|11     0 |3

001|10                                                 001|10     1 |2

01-|01                                                 010|01     2 |1

1-0|10                                                 011|01     3 |1

1-1|00                                                 100|10     4 |2

                                                       101|01     5 |0

                                                       110|10     6 |2

                                                       111|11     7 |0

*/

#include <avr/io.h>

#include <stdbool.h>

int main(void){

 

   // Methode 1: Lookup Table LUT

 

   uint8_t Lut [] = {3,2,1,1,2,0,2,0};

   uint8_t abc = 0b011;

   uint8_t xy = Lut[abc];

   bool x = xy & 0b10;

   bool y = xy & 0b01;

 

 

   //Methode 2: Lut komprimiert (es werden nur 2 Bit je Eintrag benötigt, 16 Bit verfügbar)

 

   uint16_t Lut1 = 0b1110010110001000; //Einträge 3,2,1,1,2,0,2,0

   // der Eintrag 0 für x steht in der LUT auf Bit Position 15, y steht auf 14

   // daher Bit 15 herausschneiden, wenn Eintrag abc=0 gesucht wird

   //       Bit 13                           bei abc = 1

   x = Lut1&(1<<(15-abc*2));

   y = Lut1&(1<<(14-abc*2));

   //oder

   x = Lut1 & (1<<(abc+1));

   y = Lut1 & (1<<(abc));

 

 

 

 

  // Methode 3: KNF für x = (a+!b)*(!a+!c) und DNF für y = (!a*!b*!c)+(!a*b)

 

  bool a,b,c;  

  a=abc&(1<<2); b=abc&(1<<1); c=abc&(1<<0);  

  x = (a | !b) & (!a | !c);

  y = (!a*!b*!c) | (!a*b);

 

 

}

 

4.2 Realisierung einer FSM in C

Auto Radio. Endlosschleife liest EVENTS von von einer Message-Queue (zwei Tasten für die Mode-Wahl und für das Weiterschalten). Diese FSM hat nur  2 Zustände: Radio Mode oder CD Mode. Im Mode wird weitergeschaltet, bei Taste "Mode-Wahl" wird der Zustand gewechselt

typedef enum {ST_RADIO,ST_CD} STATES;

typedef enum {EVT_MODE,EVT_NEXT} EVENTS;

 

EVENTS readEvents(void); // not implemented

 

int main(void){

 

  STATES state = ST_RADIO;  

  int stationNumber = 0;  

  int trackNumber = 0;

  while (1) {

    EVENTS event = readEvents();

    switch (state){

      case ST_RADIO:

        switch (event)

        {

          case EVT_MODE:

            state = ST_CD;

            break;

          case EVT_NEXT:

            stationNumber++;

            break;

        }

        break;

 

 case ST_CD:

        switch (event)

        {

          case EVT_MODE:

            state = ST_RADIO;

            break;

          case EVT_NEXT:

            trackNumber++;

            break;

        }

        break;

    }

  }

}