Ein Muster in einem Bitstrom erkennen

Das Beispiel der Ampel läuft vollständig von selbst ab; ein Sequenzdetektor reagiert stattdessen auf einen externen Bitstrom, ein Bit pro Takt, und muss genau den Moment erkennen, in dem ein Zielmuster — sagen wir die 3-Bit-Folge 1-0-1 — gerade eingetroffen ist, egal wie es mit anderen Bits davor und danach durchmischt ist.

Ein Zustand pro „wie viel Fortschritt bisher"

Jeder Zustand repräsentiert, wie viel der Zielsequenz bisher übereinstimmt: S0 (kein Fortschritt), S1 (eine führende 1 gefunden), S2 (1-0 gefunden), wonach die Übereinstimmung abgeschlossen wird und je nachdem, was als Nächstes eintrifft, zurück nach S0 oder S1 gewechselt wird. Eine 0 in S1 führt nach S2; eine 1 in S2 schließt die Übereinstimmung ab. Entscheidend ist, dass sich Treffer überlappen dürfen: Der Abschluss von 1-0-1 aus S2 landet zurück in S1, nicht in S0, da genau diese letzte 1 auch der Beginn des nächsten Treffers sein könnte.

Warum das ein Mealy-Automat sein muss, kein Moore-Automat

Der ganze Sinn liegt darin, den Treffer genau in dem Moment zu melden, in dem das entscheidende Bit eintrifft, im selben Takt — genau die Reaktion im selben Takt, die einen Mealy-Automaten definiert: Ausgang = f(Zustand, Eingang), nicht nur Ausgang = f(Zustand). Eine Moore-Version könnte ihren Ausgang erst einen vollen Takt anheben, nachdem das Muster bereits abgeschlossen war.

Probieren Sie es selbst

Bauen Sie im Schaltungseditor das 2-Bit-Zustandsregister und die Folgezustands-/Ausgangslogik für den 1-0-1-Detektor — drei Zustände passen bequem in 2 Bit —, steuern Sie einen Bitstrom über einen INPUT-Schalter jeweils eine CLOCK-Flanke zur Zeit ein, und bestätigen Sie, dass der Ausgang genau in dem Moment hochgeht, in dem das dritte Bit eines 1-0-1-Musters eintrifft, einschließlich überlappender Treffer wie 1-0-1-0-1.