2.4 Kommunizierende endliche Automaten
53
2.4 Kommunizierende endliche Automaten
In den nachfolgenden Abschnitten werden wir nur digitale Systeme betrachten. Verglichen mit den frühen Entwurfsphasen benötigen wir genauere Modelle unseres zu
entwerfenden Systems. Auf den Seiten 18 und 34 haben wir bereits erwähnt, dass wir
zustandsorientiertes Verhalten beschreiben müssen. Klassisch werden dazu endliche
Automaten (kurz Automaten, engl. Finite State Machines (FSMs)) verwendet, die
über eine Zustandsmenge, ein Eingabealphabet, Ausgaben sowie die Berechnung
des Folgezustands modelliert werden. Abb. 2.10 (identisch zu Abb. 2.1) zeigt eine
graphische Darstellung als klassisches Zustandsdiagramm.
Abb. 2.10 Zustandsdiagramm
eines Automaten
m
k
Z
k k
k
D
i
j
E
f
A
B
C
h
g
k
Zustände werden durch Kreise gekennzeichnet. Wir betrachten hier nur Automaten, die sich jederzeit in genau einem der möglichen Zustände befinden. Solche
Automaten werden deterministisch genannt. Die Kantenbeschriftung stellt Ereignisse dar. Angenommen, ein Automat befindet sich in einem bestimmten Zustand
und es tritt ein Ereignis ein, das einer der von diesem Zustand ausgehenden Kanten entspricht. Dann geht der Automat über in den Zustand, der sich am Ende der
Kante befindet. Automaten können implizit getaktet sein. Solche Automaten werden
synchrone Automaten genannt. Bei diesen finden Zustandsübergänge nur bei Taktübergängen statt. Automaten können auch Ausgaben erzeugen (in Abb. 2.10 nicht
dargestellt). Weitere Informationen über klassische Automaten finden sich z.B. bei
Kohavi [302].
2.4.1 Zeitgesteuerte Automaten
Klassische Automaten verfügen über keinerlei Möglichkeiten, Zeit zu modellieren. Sie wurden daher um eine Möglichkeit ergänzt, Zeitinformationen darzustellen.
Zeitgesteuerte Automaten (engl. timed automata) sind Automaten, die durch reelle
Variablen erweitert werden. „Die Variablen modellieren die logischen Uhren des
Systems. Diese werden beim Systemstart mit Null initialisiert und laufen dann synchron. An den Kanten angegebene Zeitbeschränkungen schränken das Verhalten des
Automaten ein. Ein Übergang über eine Kante kann stattfinden, wenn der aktuelle
Zeitwert der Uhr dem an der Kante angegebenen entspricht. Uhren können bei einer
Transition auf Null zurückgesetzt werden” [44].
53
2.4 Kommunizierende endliche Automaten
In den nachfolgenden Abschnitten werden wir nur digitale Systeme betrachten. Verglichen mit den frühen Entwurfsphasen benötigen wir genauere Modelle unseres zu
entwerfenden Systems. Auf den Seiten 18 und 34 haben wir bereits erwähnt, dass wir
zustandsorientiertes Verhalten beschreiben müssen. Klassisch werden dazu endliche
Automaten (kurz Automaten, engl. Finite State Machines (FSMs)) verwendet, die
über eine Zustandsmenge, ein Eingabealphabet, Ausgaben sowie die Berechnung
des Folgezustands modelliert werden. Abb. 2.10 (identisch zu Abb. 2.1) zeigt eine
graphische Darstellung als klassisches Zustandsdiagramm.
Abb. 2.10 Zustandsdiagramm
eines Automaten
m
k
Z
k k
k
D
i
j
E
f
A
B
C
h
g
k
Zustände werden durch Kreise gekennzeichnet. Wir betrachten hier nur Automaten, die sich jederzeit in genau einem der möglichen Zustände befinden. Solche
Automaten werden deterministisch genannt. Die Kantenbeschriftung stellt Ereignisse dar. Angenommen, ein Automat befindet sich in einem bestimmten Zustand
und es tritt ein Ereignis ein, das einer der von diesem Zustand ausgehenden Kanten entspricht. Dann geht der Automat über in den Zustand, der sich am Ende der
Kante befindet. Automaten können implizit getaktet sein. Solche Automaten werden
synchrone Automaten genannt. Bei diesen finden Zustandsübergänge nur bei Taktübergängen statt. Automaten können auch Ausgaben erzeugen (in Abb. 2.10 nicht
dargestellt). Weitere Informationen über klassische Automaten finden sich z.B. bei
Kohavi [302].
2.4.1 Zeitgesteuerte Automaten
Klassische Automaten verfügen über keinerlei Möglichkeiten, Zeit zu modellieren. Sie wurden daher um eine Möglichkeit ergänzt, Zeitinformationen darzustellen.
Zeitgesteuerte Automaten (engl. timed automata) sind Automaten, die durch reelle
Variablen erweitert werden. „Die Variablen modellieren die logischen Uhren des
Systems. Diese werden beim Systemstart mit Null initialisiert und laufen dann synchron. An den Kanten angegebene Zeitbeschränkungen schränken das Verhalten des
Automaten ein. Ein Übergang über eine Kante kann stattfinden, wenn der aktuelle
Zeitwert der Uhr dem an der Kante angegebenen entspricht. Uhren können bei einer
Transition auf Null zurückgesetzt werden” [44].