Moore und mehlige Maschinen

Endliche Automaten können Ausgaben haben, die jedem Übergang entsprechen. Es gibt zwei Arten von Finite-State-Maschinen, die Ausgabe generieren:

  • Mehlige Maschine
  • Moore Maschine

Mehlige Maschine

Eine mehlige Maschine ist ein FSM, dessen Ausgabe sowohl vom aktuellen Zustand als auch von der aktuellen Eingabe abhängt.

Es kann durch ein 6-Tupel (Q, ∑, O, δ, X, q 0 ) beschrieben werden, wobei -

  • Q ist eine endliche Menge von Zuständen.

  • ist eine endliche Menge von Symbolen, die als Eingabealphabet bezeichnet wird.

  • O ist eine endliche Menge von Symbolen, die als Ausgabealphabet bezeichnet wird.

  • δ ist die Eingangsübergangsfunktion, wobei δ: Q × ∑ → Q.

  • X ist die Ausgangsübergangsfunktion, wobei X: Q × ∑ → O.

  • q0ist der Anfangszustand, von dem aus eine Eingabe verarbeitet wird (q 0 ∈ Q).

Die Statustabelle einer mehligen Maschine ist unten dargestellt -

Derzeitiger Zustand Nächster Zustand
Eingabe = 0 Eingabe = 1
Zustand Ausgabe Zustand Ausgabe
→ a b x 1 c x 1
b b x 2 d x 3
c d x 3 c x 1
d d x 3 d x 2

Das Zustandsdiagramm der obigen Mealy Machine ist -

Moore Machine

Die Moore-Maschine ist eine FSM, deren Ausgänge nur vom aktuellen Zustand abhängen.

Eine Moore-Maschine kann durch ein 6-Tupel (Q, ∑, O, δ, X, q 0 ) beschrieben werden, wobei -

  • Q ist eine endliche Menge von Zuständen.

  • ist eine endliche Menge von Symbolen, die als Eingabealphabet bezeichnet wird.

  • O ist eine endliche Menge von Symbolen, die als Ausgabealphabet bezeichnet wird.

  • δ ist die Eingangsübergangsfunktion, wobei δ: Q × ∑ → Q.

  • X ist die Ausgangsübergangsfunktion, wobei X: Q → O.

  • q0ist der Anfangszustand, von dem aus eine Eingabe verarbeitet wird (q 0 ∈ Q).

Die Statustabelle einer Moore-Maschine ist unten dargestellt -

Derzeitiger Zustand Nächster Zustand Ausgabe
Eingabe = 0 Eingabe = 1
→ a b c x 2
b b d x 1
c c d x 2
d d d x 3

Das Zustandsdiagramm der obigen Moore-Maschine lautet -

Mehlige Maschine gegen Moore-Maschine

In der folgenden Tabelle sind die Punkte aufgeführt, die eine mehlige Maschine von einer Moore-Maschine unterscheiden.

Mehlige Maschine Moore Machine
Die Ausgabe hängt sowohl vom aktuellen Zustand als auch von der aktuellen Eingabe ab Die Ausgabe hängt nur vom aktuellen Zustand ab.
Im Allgemeinen hat es weniger Zustände als Moore Machine. Im Allgemeinen hat es mehr Zustände als Mealy Machine.
Der Wert der Ausgangsfunktion ist eine Funktion der Übergänge und der Änderungen, wenn die Eingangslogik für den aktuellen Zustand abgeschlossen ist. Der Wert der Ausgangsfunktion ist eine Funktion des aktuellen Zustands und der Änderungen an den Taktflanken, wenn Zustandsänderungen auftreten.
Mehlige Maschinen reagieren schneller auf Eingaben. Sie reagieren im Allgemeinen im gleichen Taktzyklus. In Moore-Maschinen ist mehr Logik erforderlich, um die Ausgänge zu decodieren, was zu mehr Schaltungsverzögerungen führt. Sie reagieren in der Regel einen Taktzyklus später.

Moore Machine zu Mealy Machine

Algorithmus 4

Input - Moore Machine

Output - Mehlige Maschine

Step 1 - Nehmen Sie ein leeres Mealy Machine-Übergangstabellenformat.

Step 2 - Kopieren Sie alle Moore Machine-Übergangszustände in dieses Tabellenformat.

Step 3- Überprüfen Sie den aktuellen Status und die entsprechenden Ausgänge in der Moore Machine-Statustabelle. Wenn für einen Zustand Q i die Ausgabe m ist, kopieren Sie ihn in die Ausgabespalten der Mealy Machine-Statustabelle, wo immer Q i im nächsten Zustand erscheint.

Beispiel

Betrachten wir die folgende Moore-Maschine -

Derzeitiger Zustand Nächster Zustand Ausgabe
a = 0 a = 1
→ a d b 1
b ein d 0
c c c 0
d b ein 1

Jetzt wenden wir Algorithmus 4 an, um ihn in Mealy Machine zu konvertieren.

Step 1 & 2 - -

Derzeitiger Zustand Nächster Zustand
a = 0 a = 1
Zustand Ausgabe Zustand Ausgabe
→ a d b
b ein d
c c c
d b ein

Step 3 - -

Derzeitiger Zustand Nächster Zustand
a = 0 a = 1
Zustand Ausgabe Zustand Ausgabe
=> a d 1 b 0
b ein 1 d 1
c c 0 c 0
d b 0 ein 1

Mehlige Maschine zu Moore Maschine

Algorithmus 5

Input - Mehlige Maschine

Output - Moore Machine

Step 1- Berechnen Sie die Anzahl der verschiedenen Ausgänge für jeden Zustand (Q i ), die in der Zustandstabelle der Mealy-Maschine verfügbar sind.

Step 2- Wenn alle Ausgänge von Qi gleich sind, kopieren Sie den Status Q i . Wenn es n verschiedene Ausgänge hat, teilen Sie Q i in n Zustände als Q in won = 0, 1, 2 .......

Step 3 - Wenn der Ausgang des Ausgangszustands 1 ist, fügen Sie am Anfang einen neuen Ausgangszustand ein, der den Ausgang 0 ergibt.

Beispiel

Betrachten wir die folgende mehlige Maschine -

Derzeitiger Zustand Nächster Zustand
a = 0 a = 1
Nächster Zustand Ausgabe Nächster Zustand Ausgabe
→ a d 0 b 1
b ein 1 d 0
c c 1 c 0
d b 0 ein 1

Hier geben die Zustände 'a' und 'd' nur 1 bzw. 0 Ausgänge, so dass wir die Zustände 'a' und 'd' beibehalten. Die Zustände 'b' und 'c' erzeugen jedoch unterschiedliche Ausgaben (1 und 0). Also teilen wir unsb in b0, b1 und c in c0, c1.

Derzeitiger Zustand Nächster Zustand Ausgabe
a = 0 a = 1
→ a d b 1 1
b 0 ein d 0
b 1 ein d 1
c 0 c 1 C 0 0
c 1 c 1 C 0 1
d b 0 ein 0