Technische Informatik
Automaten
Thorsten Thormählen
10. Dezember 2023
Teil 7, Kapitel 4
Technische Informatik
- Ohne Rückkopplung (Schaltnetz)
- Werte an den Ausgängen sind nur abhängig von den Eingängen
- Solche Schaltungen verhalten sich immer gleich (sind zustandslos) und sind durch ihre Schaltfunktion eindeutig beschrieben
- Es ist jedoch nicht möglich, etwas zu speichern
- Mit Rückkopplung (Schaltwerk)
- Werte an den Ausgängen sind abhängig von den Eingängen und den vorherigen Ausgangswerten
- Das Zeitverhalten muss genau betrachtet werden
- Die vorherigen Ausgangswerte können als Zustand der Gatter interpretiert werden. Abhängig vom Zustand verhalten sich die Gatter anders (zustandsabhängige Schaltfunktion)
- Es wird möglich, Zustände zu speichern
- Im vorangegangenen Kapitel wurde gezeigt, dass durch Rückkopplung Speicherelemente (Flip-Flops, Register) realisiert werden können, die einen Zustand speichern
- Demnach kann ein Schaltwerk auch als eine Kombination aus einem Schaltnetz und einem Zustandsspeicher dargestellt werden
- Die Ausgabe eines Schaltwerks kann abhängig vom aktuellen Zustand sein
- Abhängig von den Eingangswerten kann sich der Zustand eines Schaltwerks ändern
- Zur Beschreibung der zustandsabhängigen Schaltfunktion können endliche Automaten verwendet werden
- In einem Zustandsübergangsgraphen wird jeder Zustand $s_i \in \mathcal{S}$ als ein Kreis dargestellt
- Die möglichen Zustandsübergänge werden mit Pfeilen gekennzeichnet
- Jeder Pfeil wird mit dem zugehörigen Eingabesymbol $a_m \in \mathcal{A}$ beschriftet, für das dieser Zustandsübergang auftritt
- Außerdem (abgetrennt durch einen "/") kann jeweils das Ausgabesymbol $b_n \in \mathcal{B}$ angegeben werden
- Beispiel: Ampelschaltung
- Menge der Eingabesymbole $\mathcal{A}=\{a_0, a_1\}$ binär kodiert mit $\{0, 1\}$
- Menge der Zustände $\mathcal{S}=\{s_0, s_1, s_2, s_3\}$
- Menge der Ausgabesymbole $\mathcal{B}= \{b_0, b_1, b_2, b_3\}$ binär kodiert mit $y_2 y_1 y_0$ zu $\{001, 010, 110, 100\}$
- Es gibt $|\mathcal{S}| \cdot |\mathcal{A}|= 4 \cdot 2 = 8$ mögliche Zustandsübergänge
- Finalzustände werden im Zustandsübergangsgraphen als doppelt gestrichene Kreise dargestellt
- Der Anfangszustand wird mit einem auf den Zustand zeigendem Dreieck gekennzeichnet
- Beispiel für einen Akzeptor:
- Ausgehend vom Anfangszustand $s_0$ würde der dargestellte Automat alle Eingabesequenzen akzeptieren, die eine ungerade Anzahl an Nullen enthalten
- Menge der Eingabewörter $\mathcal{A}= \{0, 1\}$
- Menge der Zustände $\mathcal{S}=\{s_0, s_1\}$
- Menge der Finalzustände $\mathcal{F}=\{s_1\}$
- Ausgehend vom Anfangszustand $s_0$ würde der dargestellte Automat alle Eingabesequenzen akzeptieren, die eine ungerade Anzahl an Nullen enthalten
- Beispiel 1: Der Zustandsübergangsgraph der Ampelschaltung soll in ein Schaltwerk umgesetzt werden
- Zur Erstellung des Schaltwerks kann die Ausgabefunktion, die Übergangsfunktion und der Zustandsspeicher separat betrachtet werden
- Für gewünschte Ausgabe- und Übergangsfunktion kann direkt aus dem Zustandsübergangsgraphen abgelesen und als Wahrheitstafel dargestellt werden
- Zur Minimierung können anschließend z.B. KV-Diagramme oder das Quine-McCluskey-Verfahren verwendet werden
- Handelt es sich um einen Moore- oder Mealy-Automaten?
| Zustand | $q_1$ | $q_0$ | $y_2$ | $y_1$ | $y_0$ |
| $s_0$ | 0 | 0 | 0 | 0 | 1 |
| $s_1$ | 0 | 1 | 0 | 1 | 0 |
| $s_2$ | 1 | 0 | 1 | 1 | 0 |
| $s_3$ | 1 | 1 | 1 | 0 | 0 |
- Antwort: Moore-Automat, da Ausgabefunktion nur abhängig vom aktuellen Zustand
- Ausgabefunktion:
- $y_2 = q_1$
- $y_1 = q_0 \nleftrightarrow q_1$
- $y_0 = \lnot q_0 \land \lnot q_1 = \lnot (q_0 \lor q_1)$
| Zustand | $q_1$ | $q_0$ | $x_0$ | $d_1$ | $d_0$ |
| $s_0$ | 0 | 0 | 0 | 0 | 0 |
| $s_0$ | 0 | 0 | 1 | 0 | 1 |
| $s_1$ | 0 | 1 | 0 | 1 | 1 |
| $s_1$ | 0 | 1 | 1 | 1 | 1 |
| $s_2$ | 1 | 0 | 0 | 0 | 0 |
| $s_2$ | 1 | 0 | 1 | 0 | 0 |
| $s_3$ | 1 | 1 | 0 | 1 | 0 |
| $s_3$ | 1 | 1 | 1 | 1 | 1 |
- Übergangsfunktion:
- $d_1 = q_0$
- Mittels KV-Diagramm oder Quine-McCluskey-Verfahren:
$d_0 = (\overline{q}_1 x_0) \lor (\overline{q}_1 q_0) \lor (q_0 x_0)$
- Beispiel 2: Dieser Zustandsübergangsgraph übersetzt einen 3-Bit Binär-Code in einen Gray-Code
- Menge der Eingabesymbole $\mathcal{A}=\{0, 1\}$
- Menge der Zustände $\mathcal{S}=\{s_0, s_1, s_2, s_3, s_4\}$
- Menge der Ausgabesymbole $\mathcal{B}= \{0, 1\}$
- Anfangszustand $s_0$
| Eingabe | Ausgabe |
| 000 | 000 |
| 001 | 001 |
| 010 | 011 |
| 011 | 010 |
| 100 | 110 |
| 101 | 111 |
| 110 | 101 |
| 111 | 100 |
Quelle: basierend auf: D. W. Hoffmann: Grundlagen der Technischen Informatik, 2. Auflage; Hanser 2009, Abb. 9.2, S. 298ff
- Aufgabe: Entwurf des entsprechenden Schaltwerks
- Handelt es sich um einen Moore- oder Mealy-Automaten?
| Eingabe | Ausgabe |
| 000 | 000 |
| 001 | 001 |
| 010 | 011 |
| 011 | 010 |
| 100 | 110 |
| 101 | 111 |
| 110 | 101 |
| 111 | 100 |
- Antwort: Mealy-Automat, da Ausgabefunktion abhängig vom aktuellen Zustand und der Eingabe
Quelle: basierend auf: D. W. Hoffmann: Grundlagen der Technischen Informatik, 2. Auflage; Hanser 2009, Abb. 9.2, S. 298ff
| $q_2$ | $q_1$ | $q_0$ | $x_0$ | $d_2$ | $d_1$ | $d_0$ | $y_0$ |
| 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
- Mittels KV-Diagramm oder durch Ablesen und Vereinfachen ergibt sich:
- $d_2 = \overline{q}_2 \overline{q}_1 \overline{q}_0 \overline{x}_0 \lor \overline{q}_2 \overline{q}_1 q_0 \lor q_2 q_1 \overline{q}_0$
- $d_1 = \overline{q}_2 \overline{q}_1 \overline{q}_0 \overline{x}_0$
- $d_0 = \overline{q}_2 \overline{q}_1 x_0 \lor q_2 q_1 \overline{q}_0 x_0$
- $y_0 = x_0 \nleftrightarrow q_0$
Anregungen oder Verbesserungsvorschläge können auch gerne per E-mail an mich gesendet werden: Kontakt