DE

Zustandsautomaten (Moore und Mealy)

Vom Zustandsdiagramm zur Tabelle und zu den Flipflop-Gleichungen, am Beispiel eines Sequenzdetektors

Entwurf eines Sequenzdetektors

Automat

Zustandsdiagramm

Jeder Pfeil trägt den Wert des Eingangs x, der ihn auslöst; bei Mealy auch den erzeugten Ausgang („Eingang/Ausgang“). Bei Moore steht der Ausgang im Zustand, und die Zustände mit Doppelkreis sind die, die z = 1 liefern.

Zustandstabelle

Gleichungen mit D-Flipflops

Simulation

Eingang

Was ein Zustandsautomat ist

Ein endlicher Automat ist eine sequentielle Schaltung, die sich zu jedem Zeitpunkt in einem von endlich vielen Zuständen befindet. Der Zustand fasst alles zusammen, was von der Vergangenheit wichtig ist. Mit jeder Taktflanke wechselt er in einen neuen Zustand, der vom aktuellen Zustand und von den Eingängen abhängt. Er besteht aus einem Register aus Flipflops, das den Zustand speichert, und zwei Blöcken kombinatorischer Logik: einer berechnet den Folgezustand, der andere die Ausgänge.

So entwirft man geordnet jede Ablaufsteuerung: eine Ampel, die Steuerung einer automatischen Tür, einen Verkaufsautomaten, das Protokoll einer seriellen Schnittstelle oder die Schritte eines Waschprogramms. In einer SPS programmiert man ihn genauso mit GRAFCET oder mit Schritten in KOP, in einem Mikrocontroller mit einem switch über eine Zustandsvariable.

Moore und Mealy

MooreMealy
Der Ausgang hängt ab vonNur dem ZustandZustand und Eingängen
Wo der Ausgang gezeichnet wirdIn jedem ZustandAn jedem Pfeil, „Eingang/Ausgang“
Anzahl der ZuständeMeist ein paar mehrMeist weniger
ReaktionDer Ausgang ändert sich mit der nächsten TaktflankeDer Ausgang ändert sich, sobald sich der Eingang ändert
AusgangÜber den ganzen Zyklus stabil, ohne GlitchesKann Glitches haben, wenn der Eingang welche hat

Vergleichen Sie beide Typen im Simulator mit derselben Folge: Der Mealy-Detektor liefert z = 1 im selben Zyklus, in dem das letzte Bit ankommt, der Moore-Detektor einen Zyklus später, wenn er in den Endzustand gewechselt ist. Führt man den Ausgang eines Mealy-Automaten in eine andere synchrone Schaltung, tritt diese Verzögerung beim Einlesen ohnehin auf.

Entwurfsschritte

  1. Zustandsdiagramm. Man beschreibt das Verhalten: welche Zustände es gibt, in welchen man bei jedem Eingang wechselt und welcher Ausgang entsteht. Bei einem Sequenzdetektor bedeutet jeder Zustand „ich habe die ersten k Bits der Folge empfangen“.
  2. Zustandstabelle. Dasselbe wie das Diagramm als Tabelle: aktueller Zustand und Eingang links, Folgezustand und Ausgang rechts.
  3. Codierung. Jedem Zustand wird ein Binärcode zugeordnet. Bei S Zuständen braucht man ⌈log₂ S⌉ Flipflops. Die Binärcodierung braucht die wenigsten Flipflops; die One-Hot-Codierung (ein Flipflop pro Zustand) braucht mehr, vereinfacht aber die Gleichungen stark und ist in FPGAs üblich.
  4. Gleichungen. Bei D-Flipflops ist der D-Eingang jedes Flipflops direkt das entsprechende Bit des Folgezustands. Unbenutzte Codes sind Don't-Cares und helfen beim Vereinfachen im KV-Diagramm. Bei JK-Flipflops verwendet man die Ansteuertabelle, statt den Folgezustand zu übernehmen.
  5. Unbenutzte Zustände. Man prüft, wohin der Automat läuft, wenn er durch Störungen oder beim Einschalten in einem unbenutzten Code startet, und sieht einen Reset vor, der ihn in den Anfangszustand bringt.

Überlappung

Mit Überlappung können die letzten Bits einer erkannten Folge der Anfang der nächsten sein: Sucht man 1011 in 1011011, wird sie zweimal erkannt. Ohne Überlappung beginnt der Automat nach jeder Erkennung von vorn und findet nur eine. Um zu entscheiden, in welchen Zustand er zurückkehrt, wenn ein Bit nicht passt, sucht man den längsten Teil des Empfangenen, der mit dem Anfang der Folge übereinstimmt; das ist dieselbe Idee wie beim Textsuchalgorithmus KMP.

Beispiel: eine Ampel

Eine Fahrzeugampel mit Fußgängertaster ist ein Moore-Automat: Die Lichter hängen nur vom Zustand ab. Ein Zeitglied liefert das Signal „Zeit abgelaufen“, und der Tastendruck wird gespeichert, bis er bedient ist.

ZustandFahrzeugampelFußgängerampelWechselt weiter, wenn
S0 GrünGrünRotEin Fußgänger gedrückt hat und die Mindestgrünzeit abgelaufen ist
S1 GelbGelbRotGelbzeit abgelaufen
S2 RotRotGrünFußgängerzeit abgelaufen
S3 RäumenRotGrün blinkendRäumzeit abgelaufen; zurück zu S0

Vier Zustände werden mit zwei Flipflops codiert. Die Ausgänge sind Funktionen von Q1 und Q0, zum Beispiel Fahrzeuggrün = Q1'·Q0' und Fußgängerrot = Q1'.

Siehe auch: Latches und Flipflops, KV-Diagramm, Logikgatter-Simulator und KOP-Simulator.