Lernen › Thema 11

Zustandsautomaten nach Moore und Mealy: vollständiger Entwurf

7 Min. Lesezeit · bitGateLab-Team

Ein endlicher Zustandsautomat (FSM) ist eine sequenzielle Schaltung, die sich „merkt“, bei welchem Schritt eines Ablaufs sie gerade steht. Ampeln, Codeschlösser, Aufzugsteuerungen und Empfänger für serielle Kommunikation sind Zustandsautomaten. Hier lernst du die beiden klassischen Modelle kennen, Moore und Mealy, und verfolgst einen vollständigen Entwurf von der Beschreibung in Worten bis zu den Gleichungen der Flipflops, am Beispiel eines Detektors für die Folge 101.

Bestandteile eines Zustandsautomaten

Jeder synchrone Automat hat drei Blöcke:

Zustandsregister: n Flipflops (fast immer vom Typ D), die den aktuellen Zustand speichern; sie reichen für bis zu 2ⁿ Zustände.
Übergangslogik: kombinatorisch; berechnet den Folgezustand aus dem aktuellen Zustand und den Eingängen.
Ausgangslogik: kombinatorisch; berechnet die Ausgänge.

Der Unterschied zwischen den beiden Modellen liegt im letzten Block:

Moore: Die Ausgänge hängen nur vom aktuellen Zustand ab. Man schreibt sie in den Kreis des jeweiligen Zustands (zum Beispiel S3/1).
Mealy: Die Ausgänge hängen vom Zustand und von den Eingängen ab. Man schreibt sie an die Pfeile (Eingang/Ausgang, zum Beispiel 1/1).

Ein Mealy-Automat braucht meist weniger Zustände und reagiert im selben Zyklus, in dem der Eingangswert eintrifft, aber sein Ausgang kann sich jederzeit ändern, wenn sich der Eingang ändert. Ein Moore-Automat reagiert einen Zyklus später, und sein Ausgang ändert sich nur unmittelbar nach der Taktflanke, was ihn sauberer macht.

Die Aufgabe: Detektor für die Folge 101

Ein serieller Eingang X trifft synchron zum Takt ein, ein Bit pro Zyklus. Der Ausgang Z soll jedes Mal 1 sein, wenn die letzten drei empfangenen Bits 1, 0, 1 waren. Überlappung ist erlaubt: In der Bitfolge 10101 gibt es zwei Erkennungen, weil die letzte 1 der ersten Folge zugleich die erste der nächsten ist.

Der erste Schritt ist die Entscheidung, was sich der Automat merken muss. Jeder Zustand steht für „wie viel von der Folge ich schon habe“:

S0: Ich habe noch nichts Brauchbares.
S1: Das letzte Bit war 1.
S2: Die letzten Bits waren 1, 0.
S3: Ich habe gerade 1, 0, 1 empfangen (Z = 1).

Zustandsdiagramm und Zustandstabelle (Moore)

Frage dich für jeden Zustand und jeden Wert von X: Welches ist mit diesem neuen Bit das längste Suffix, das mit dem Anfang von 101 übereinstimmt? Dieses Suffix legt den Folgezustand fest.

Moore-Detektor für 101 mit Überlappung. Die Zahlen an den Pfeilen sind der Wert von X; der Ausgang steht im jeweiligen Zustand.

Aktueller Zustand	X = 0	X = 1	Z
S0	S0	S1	0
S1	S2	S1	0
S2	S0	S3	0
S3	S2	S1	1

Achte auf zwei Übergänge, bei denen häufig Fehler passieren. In S1 trifft eine weitere 1 ein: Die Bitfolge endet auf 11, und die letzte 1 taugt weiterhin als Anfang, also bleibt der Automat in S1. In S3 trifft eine 0 ein: Die Bitfolge endet auf 1010, deren Suffix 10 mit dem Anfang von 101 übereinstimmt, also geht er nach S2 und nicht nach S0. Genau das ermöglicht die Überlappung.

Zustandscodierung und Gleichungen

Für 4 Zustände genügen 2 D-Flipflops (Q1 Q0). Die naheliegendste Codierung ist die binäre: S0 = 00, S1 = 01, S2 = 10, S3 = 11. Mit D-Flipflops ist die Anregungstabelle trivial, weil D = Q⁺ gilt.

Q1	Q0	X	Q1⁺ = D1	Q0⁺ = D0
0	0	0	0	0
0	0	1	0	1
0	1	0	1	0
0	1	1	0	1
1	0	0	0	0
1	0	1	1	1
1	1	0	1	0
1	1	1	0	1

Vereinfachung:

D0 ist genau in den Zeilen mit X = 1 gleich 1, also D0 = X. Das leuchtet ein: In dieser Codierung bedeutet Q0 = 1 „das letzte Bit war 1“.
D1 = Σm(2, 5, 6) mit den Variablen in der Reihenfolge Q1 Q0 X. Die Minterme 2 (010) und 6 (110) sind benachbart und bilden Q0·X. Die 5 (101) hat keine Nachbarn mit 1 und bleibt allein: Q1·Q0·X. D1 = Q0·X + Q1·Q0·X.
Der Moore-Ausgang hängt nur vom Zustand ab: Z = Q1·Q0.

Die Schaltung besteht aus 2 D-Flipflops, einem AND mit 2 Eingängen für Z und für D1 aus einem AND mit 2, einem AND mit 3 und einem OR mit 2 Eingängen (dazu die Inverter für Q0 und X).

Überprüfung mit einer Testfolge

Eingang X = 1 0 1 0 1 1 0 1, ausgehend von S0. Zustand nach jeder Flanke:

Flanke	1	2	3	4	5	6	7	8
X	1	0	1	0	1	1	0	1
Zustand	S1	S2	S3	S2	S3	S1	S2	S3
Z	0	0	1	0	1	0	0	1

Es gibt drei Erkennungen: bei den Bits 1 bis 3, 3 bis 5 (Überlappung) und 6 bis 8. Prüfe Flanke 4 mit den Gleichungen: Zustand S3 = 11 und X = 0, D1 = 1·1 + 1·0·0 = 1 und D0 = 0, Folgezustand 10 = S2. Es stimmt.

Die Mealy-Version

Bei Mealy steht der Ausgang am Übergang, der Zustand S3 ist also überflüssig: Die Erkennung erfolgt, „wenn im Zustand S2 die 1 eintrifft“. Mit drei Zuständen A (nichts), B (letztes Bit 1) und C (letzte Bits 1, 0):

Zustand	X = 0	X = 1
A	A / 0	B / 0
B	C / 0	B / 0
C	A / 0	B / 1

Es werden weiterhin 2 Flipflops benötigt, aber der Ausgang Z = 1 erscheint im selben Zyklus, in dem die letzte 1 eintrifft, einen Zyklus früher als in der Moore-Version.

Häufige Fehler

Alle Übergänge, die „fehlschlagen“, nach S0 zu führen, ohne zu prüfen, welcher Teil der Folge noch brauchbar ist; so gehen Erkennungen mit Überlappung verloren.
Bei einem Moore-Automaten die Ausgänge an die Pfeile oder bei einem Mealy-Automaten in die Zustände zu schreiben.
Die unbenutzten Flipflop-Kombinationen zu vergessen (zum Beispiel den Code 11 in der Mealy-Version): Man muss festlegen, wohin sie führen, oder sie als X markieren und prüfen, dass der Automat in die Folge zurückkehrt.
Den Ausgang eines Mealy-Automaten zu einem beliebigen Zeitpunkt abzulesen: Er muss kurz vor der Flanke abgetastet werden, wenn der Eingang bereits stabil ist.
Beim Testen des Automaten den Eingang X genau an der Taktflanke zu ändern.

Probiere es im Simulator aus

Sobald du die Gleichungen hast, ist der Detektor in wenigen Minuten aufgebaut, und im Zeitdiagramm kannst du jeden Übergang überprüfen.

Platziere zwei D-Flipflops mit demselben Takt; benenne ihre Ausgänge Q1 und Q0.
Verbinde den Eingang X direkt mit D0.
Baue D1 = Q0·X + Q1·Q0·X aus zwei Invertern, zwei AND und einem OR auf und schließe es an D1 an.
Verbinde ein AND von Q1 und Q0 mit einer LED-Anzeige für Z.
Ändere X vor jeder Flanke gemäß der Folge 1 0 1 0 1 1 0 1 und beobachte im Zeitdiagramm, dass Z nach den Flanken 3, 5 und 8 aufleuchtet.

Übungen

Wie oft erkennt der Automat mit Überlappung die Folge 101 in der Bitfolge 1010101?
Lösung
Dreimal: bei den Bits 1 bis 3, 3 bis 5 und 5 bis 7.
Stelle die Moore-Tabelle des Detektors für 101 ohne Überlappung neu auf (nach einer Erkennung beginnt man wieder bei null).
Lösung
Es ändert sich nur die Zeile S3: Mit X = 0 geht es nach S0 und mit X = 1 nach S1. Die übrigen Zeilen bleiben gleich.
Bestimme Z mit der Codierung der Mealy-Version A = 00, B = 01, C = 10.
Lösung
Z = 1 nur im Zustand C mit X = 1: Z = Q1·Q0·X. Tritt der Code 11 nie auf, kann man ihn als X markieren, und es bleibt Z = Q1·X.
Wie viele Flipflops braucht ein Automat mit 9 Zuständen mindestens?
Lösung
4, denn 2³ = 8 reicht nicht, 2⁴ = 16 dagegen schon.

Um die Flipflops zu wiederholen, aus denen das Zustandsregister besteht, lies das Thema Latches und Flipflops.