Hardware Reference
In-Depth Information
symbolischen Namen. Der Startzustand wird mit einem kleinen Dreieck ge-
kennzeichnet. Die Kanten sind gerichtet und mit den Übergangsbedingungen
beschriftet. In der Grundform ist die Übergangsbedingung die Menge der Ein-
gabewerte, bei denen der Übergang erfolgen soll. Keine Angabe bedeutet, dass
der Übergang bei jeder Eingabe erfolgen soll. In erweiterten Modellen kann
die Übergangsbedingung ein beliebiger logischer Ausdruck sein. Die Ausgabe-
werte werden entweder den Knoten oder den Kanten zugeordnet. Die Ausgabe
in einem Knoten gilt für alle Kanten, die den Knoten verlassen. Wenn einem
Knoten eine Ausgabe zugeordnet ist, dann darf den abgehenden Kanten keine
Ausgabe zugeordnet sein.
Endliche Automaten werden unterteilt in Mealy-Automaten, Moore-Au-
tomaten und autonome Automaten. Ein Mealy-Automat ist ein allgemeiner
Automat mit mehreren abgehenden Kanten je Zustand, denen zumindest zum
Teil unterschiedliche Ausgabewerte zugeordnet sind. Die Ausgabe ist damit
von der Eingabe abhängig. Abbildung 1.65 a zeigt als Beispiel den Zustands-
graphen für einen Vorwärts-Rückwärts-Zähler, der bei der Eingabe »V« zy-
klisch die Zustandsfolge »A-B-C-D« und bei der Eingabe »R« die umgekehrte
Zustandsfolge »A-D-C-B« durchläuft. Bei dem dritten Wert aus der Einga-
bemenge »H« behält der Automat seinen aktuellen Zustand bei. Jedem Zu-
standsübergang ist ein Ausgabewert zugeordnet.
H/K
H/L
a)
s
Zustand
V/L
Eingabewert
Ausgabewert
A B
x/y
R/K
V/K
R/N
R/L
V/M
Σ=
{
H,V,R
}
Eingabemenge
Zustandsmenge
Ausgabemenge
R/M
S=
{
A,B,C,D
}
D
C
Π=
{
K,L,M,N
}
V/N
Anfangszustand
H/N
H/M
b)s
+
=f
s
(x,s)
sx:
s
+
=f
s
(x,s)
y=f
a
(x,s)
c) d)
y=f
a
(x,s)
C
D
10
11
V
B
C
D
A
H
R
VHR
K
L
M
N
V
H
R
0
01
10
0
sx:
000110
000110
A
A
D
L
M
N
N
00
1
00
01
10
11
00
01
10
11
11
01
10
11
00
01
10
11
11
K
L
M
N
B
B
A
K
L
M
01
00
01
10
00
01
10
0
10
11
C
D
C
D
B
10
11
A
B
00
1
C
K
00
00
0
Abb. 1.65. Vorwärts-Rückwärts-Zähler als Mealy-Automat a) Zustandsgraph b)
tabellarische Übergangs- und Ausgabefunktion mit symbolischen Werten c) Codie-
rung d) bitorientierte Übergangs- und Ausgabefunktion
Die Übergangsfunktion und die Ausgabefunktion lassen sich als Tabellen
darstellen. Die Zeilen repräsentieren die Ist-Zustände, die Spalten die Einga-
bewerte und die Einträge die zugeordneten Folgezustände und Ausgabewerte
(Abb. 1.65 b). Die Werte sind wie im Zustandsgraph Symbole, die im nächs-
