T08-Sequentielle-Schaltkreise-und-Mealy-Automat

Sequentielle Schaltkreise & Mealy-Automat

Zusammenfassung

Sequentielle Schaltkreise (Schaltwerke) bestehen aus einem Register (Flipflops) und einem kombinatorischen Kern. Sie entsprechen endlichen Zustandsautomaten (FSM). Die Klausur (A6, 16P) verlangt den vollständigen Entwurf eines Mealy-Automaten: Zustandsdiagramm zeichnen, äquivalente Zustände erklären, Automat minimieren, Zustandskodierung wählen und Übergangstafel aufstellen.

RISIKO: Nur ein einziges Übungsblatt (Blatt10) behandelt dieses Thema. Die Klausur enthält es aber als vollwertige 16-Punkte-Aufgabe. Besonders intensiv üben!

Exam-Relevanz

Aufgabe 6 — Mealy-Automat (4 + 4 + 2 + 6 = 16 Punkte)

Teilaufgabe Punkte Inhalt
a) 4P Zustandsdiagramm aus Zustandstafel zeichnen
b) 4P Hinreichende Äquivalenzbedingung erklären — warum hier keine Zustände die Bedingung erfüllen
c) 2P Automat auf 3 Zustände minimieren ( löschbar), reduziertes Diagramm zeichnen
d) 6P Zustandskodierung wählen + neue Zustands- und Ausgangstafel mit Kodierung

Die Aufgabe erscheint identisch in Klausur und Probeklausur. Der Automat hat 6 Zustände , Startzustand .

RISIKO: Nur Blatt10 (Aufgaben 2 und 3) als Übungsmaterial. Keine weitere Übung zu diesem Thema. Unbedingt mehrfach durchrechnen!

Endliche Automaten (FSM)

Ein deterministischer endlicher Halbautomat ist ein Quadrupel:

  • : endliche Menge von Eingabesymbolen (Eingabealphabet)
  • : endliche Menge von Zuständen
  • : Menge der Anfangszustände
  • : Übergangsfunktion

Ein Mealy-Automat erweitert um Ausgabe:

  • : endliche Menge von Ausgabesymbolen (Ausgabealphabet)
  • : Ausgabefunktion (abhängig von Zustand und Eingabe)

Ein Moore-Automat hat dagegen:

Die Ausgabe hängt nur vom Zustand ab.

Schaltwerk-Struktur:

 x₁ᵗ ... xₖᵗ                              y₁ᵗ ... yₘᵗ
  │        │                                ↑        ↑
  ↓        ↓     ┌─────┐                   ┌─────┐   │
  ┌──────────────────┐    s₁ᵗ⁺¹ ... sₚᵗ⁺¹ │       │  │
  │       δ          │──→ │   Register    │       │──┘
  └──────────────────┘    │               │       │
  ┌──────────────────┐    │               │       │
  │       λ          │←───│ s₁ᵗ ... sₚᵗ  │       │
  └──────────────────┘    └───────────────┘       │
                          ↑        │              │
                          └────────┘              │
                               ck ──→
  • Übergangsfunktion:
  • Ausgabefunktion (Mealy):
  • Ausgabefunktion (Moore):

Der Zustand ist die Belegung der Flipflops im Register zum Zeitpunkt .

Der kombinatorische Kern hat vier Arten von Ein-/Ausgängen:

  • Primäre Eingänge : von außen
  • Primäre Ausgänge : nach außen
  • Sekundäre Eingänge : Datenausgänge der Flipflops (aktueller Zustand)
  • Sekundäre Ausgänge : Dateneingänge der Flipflops (Folgezustand)

Mealy vs Moore

Mealy-Automat Moore-Automat
Ausgabe — abhängig von Zustand und Eingabe — abhängig nur vom Zustand
Folgezustand
Beziehung — spezieller Mealy-Automat
Reaktion sofort bei Eingabe erst nach Zustandswechsel

Moore- und Mealy-Automaten können ineinander überführt werden.

Die Klausur verwendet ausschließlich Mealy-Automaten.

Zustandsdiagramm

Konventionen:

  • Knoten (Kreise) = Zustände
  • Kanten (Pfeile) = Übergänge, beschriftet mit Eingabe/Ausgabe ()
  • Startzustand durch Pfeil gekennzeichnet (oft mit "Start" beschriftet)
  • Selbstschleife = Zustand bleibt bei dieser Eingabe unverändert

Lesen: Bei Zustand und Eingabe : folge der mit beschrifteten Kante. Die Ausgabe steht nach dem Schrägstrich, der Folgezustand ist der Zielknoten.

Beispiel (aus Vorlesung k420):

  ┌─────────┐       ┌─────────┐
  │   s₁    │──1/0─→│   s₂    │
  │         │←─0/1──│         │
  └─────────┘       └─────────┘

Bedeutung: Im Zustand mit Eingabe : Ausgabe , Übergang nach . Im Zustand mit Eingabe : Ausgabe , Übergang nach .

Zustandsübergangstabelle

Aus dem Zustandsdiagramm wird die Zustands- und Ausgangstafel aufgestellt. Für jeden Zustand und jede mögliche Eingabe: Folgezustand und Ausgabe eintragen.

Beispiel (Modulo-4 Vorwärts/Rückwärtszähler, Moore):
1 0 0 0 1 0 0 Vorwärts
1 0 1 1 0 0 1
1 1 0 1 1 1 0
1 1 1 0 0 1 1
0 1 1 1 0 1 1 Rückwärts
0 1 0 0 1 1 0
0 0 1 0 0 0 1
0 0 0 1 1 0 0

Bei einem Mealy-Automaten hat jeder Tabelleneintrag eine eigene Ausgabe (da von abhängt). Bei einem Moore-Automaten ist pro Zustand konstant.

Zustandsäquivalenz & Minimierung

Definition: Zwei Zustände heißen äquivalent, wenn der Automat von beiden Zuständen aus bei gleichen Eingabefolgen stets die gleichen Ausgabefolgen produziert.

Hinreichende Bedingung (Vorlesungsverfahren):

  1. Wenn zwei Zustände bei der gleichen Eingabe die gleiche Ausgabe erzeugen und den gleichen Folgezustand annehmen äquivalent.
  2. Wenn zwei Zustände bei der gleichen Eingabe gleiche Ausgaben erzeugen und äquivalente Folgezustände annehmen ebenfalls äquivalent. Wiederhole, bis keine weiteren Äquivalenzen.

Verfahren (Partition Refinement):

  1. Vergleiche alle Zustandspaare: gleiche Ausgabe für alle Eingaben?
  2. Wenn ja und gleicher Folgezustand direkt äquivalent (Schritt 1).
  3. Wenn ja und äquivalente Folgezustände äquivalent (Schritt 2, iterativ).
  4. Verschmelze äquivalente Zustände zu einem.

Beispiel (Vorlesung k430): Zustände und äquivalent eliminiert. Dann und äquivalent eliminiert. Kette: wird zu .

Zustandskodierung

Nach der Minimierung werden den verbleibenden Zuständen binäre Codes zugewiesen.

  • Bei Zuständen benötigt man Flipflops.
  • One-hot-Kodierung: Flipflops, jeder Zustand hat genau eine 1. Einfachere Logik, mehr Flipflops.
  • Binäre Kodierung: Flipflops, natürliche Binärcodes. Weniger Flipflops, potenziell komplexere Logik.
  • Gray-Code-Kodierung: Übergänge ändern nur 1 Bit oft einfachere Logik.

Die Wahl der Kodierung beeinflusst die Komplexität der kombinatorischen Logik!

Beispiel aus Vorlesung (k430):

  • Kodierung : 4 Monome, 9 Literale
  • Kodierung : 6 Monome, 11 Literale

Ziel: Wähle Kodierung, die nachfolgende kombinatorische Synthese erleichtert (heuristische Verfahren).

Startzustand: Der Startzustand sollte vorzugsweise auf kodiert werden, damit die Flipflops beim Reset automatisch im Startzustand sind.

Synthese: Diagramm → Schaltkreis

Vollständiger Entwurfsweg (Vorlesung k430):

  1. Textspezifikation Zustandsdiagramm
  2. Zustandsminimierung — äquivalente Zustände verschmelzen
  3. Zustandskodierung wählen Anzahl Flipflops festlegen
  4. Zustands- und Ausgangstafel mit Kodierung aufstellen
  5. Übergangsfunktion und Ausgabefunktion als Boolesche Funktionen aufstellen
  6. Logikminimierung (KV-Diagramm, Quine-McCluskey)
  7. Schaltkreis zeichnen: kombinatorischer Kern + Register aus D-FFs

Vollständiges Worked Example: Mealy-Automat aus Klausur A6

Ausgangslage

Mealy-Automat mit Zustandstafel:
0 0
1 0
0 1
1 1
0 1
1 1
0 0
1 0
0 1
1 1
0 1
1 1

Startzustand: .

Schritt 1: Zustandsdiagramm (Teilaufgabe a)

              Start
               ↓
         ┌─────────┐  0/0   ┌─────────┐  0/1   ┌─────────┐  0/1   ┌─────────┐
         │   s₁    │────────│   s₂    │────────│   s₃    │────────│   s₄    │
         │         │←───────│         │←───────│         │←───────│         │
         └─────────┘  1/0   └─────────┘  1/1   └─────────┘  1/1   └─────────┘
              ↑                                          0/0   ┌─────────┐  0/1   ┌─────────┐
              │  1/1                                    ──────│   s₅    │────────│   s₆    │
              │                                               │         │←───────│         │
              └───────────────────────────────────────────────└─────────┘  1/1   └─────────┘
                                                              1/0                0/1

Lesart: Jeder Zustand hat zwei ausgehende Kanten (für und ), jeweils beschriftet mit :

  • : (Selbstschleife),
  • : (Selbstschleife),
  • : (Selbstschleife),
  • : (Selbstschleife),
  • : (Selbstschleife),
  • : (Selbstschleife),

Schritt 2: Äquivalenzbedingung prüfen (Teilaufgabe b)

Hinreichende Bedingung: Zwei Zustände sind äquivalent, wenn sie bei jeder Eingabe die gleiche Ausgabe liefern und den gleichen Folgezustand annehmen.

Betrachte die Ausgabemuster pro Zustand:

Zustand bei bei
0 0
1 1
1 1
0 0
1 1
1 1

Gruppen mit gleichem Ausgabemuster:

  • Gruppe A ():
  • Gruppe B ():

Prüfe Gruppe A ():

: Folgezustand : Folgezustand

Folgezustände sind verschieden ( und ). Die hinreichende Bedingung ist nicht erfüllt.

Prüfe Gruppe B ():

: Folgezustand : Folgezustand

Alle Folgezustände sind verschieden. Die hinreichende Bedingung ist nicht erfüllt.

Antwort b): Es gibt keine zwei Zustände, die bei jeder Eingabe sowohl die gleiche Ausgabe als auch denselben Folgezustand haben. Die hinreichende Bedingung ist für kein Paar erfüllt. Dennoch kann der Automat durch die erweiterte Äquivalenzbedingung (Schritt 2: äquivalente Folgezustände) minimiert werden.

Schritt 3: Minimierung auf 3 Zustände (Teilaufgabe c)

Die Klausur gibt vor: können gelöscht werden. Wir zeigen warum:

Beobachtung der Struktur: Die Zustände – und – haben identische Ausgabemuster ( bzw. ) und identische Übergangsstruktur (Selbstschleife bei , Weiter bei ). Der einzige Unterschied ist, dass die –-Kette nach zurückkehrt.

Erweiterte Äquivalenz (Schritt 2): Wenn zwei Zustände gleiche Ausgaben erzeugen und ihre Folgezustände äquivalent sind, sind sie äquivalent.

Behauptung: , , .

Beweis durch zirkuläre Äquivalenz:

  • und : Bei beide Ausgabe 1, Selbstschleife (, ). Bei beide Ausgabe 1, Folgezustände und . Wenn , dann .
  • und : Bei beide Ausgabe 1, Selbstschleife. Bei beide Ausgabe 1, Folgezustände und . Wenn , dann .
  • und : Bei beide Ausgabe 0, Selbstschleife. Bei beide Ausgabe 0, Folgezustände und . Wenn , dann .

Dies ist eine zirkuläre Abhängigkeit: . Alle drei Äquivalenzen gelten gleichzeitig oder keine. Da die Ausgaben übereinstimmen und die Struktur konsistent ist, gelten alle drei.

Verschmelzung:

Reduziertes Zustandsdiagramm (3 Zustände):

              Start
               ↓
         ┌─────────┐  0/0   ┌─────────┐  0/1   ┌─────────┐
         │   s₁'   │────────│   s₂'   │────────│   s₃'   │
         │ {s₁,s₄} │←───────│ {s₂,s₅} │←───────│ {s₃,s₆} │
         └─────────┘  1/0   └─────────┘  1/1   └─────────┘
              ↑                                          1/1
              └──────────────────────────────────────────┘
  • : ,
  • : ,
  • : ,

Schritt 4: Zustandskodierung + Übergangstafel (Teilaufgabe d)

3 Zustände Flipflops.

Kodierung (Startzustand auf ):

Zustand
0 0
0 1
1 0

(Code bleibt ungenutzt — Don't-Care für Logikminimierung.)

Übergangstafel mit Kodierung:
0 0 0 0 0 0
1 0 0 0 1 0
0 0 1 0 1 1
1 0 1 1 0 1
0 1 0 1 0 1
1 1 0 0 0 1
0 1 1 — — —
1 1 1 — — —

(Die letzte Zeile mit ist Don't-Care, da dieser Zustand nie erreicht wird.)

Startzustand der Flipflops: (entspricht ).

Schritt 5: Boolesche Funktionen (optional, für vollständigen Schaltkreis)

Aus der Tafel mit Don't-Cares ():

Vereinfacht (mit Don't-Care ):

(Ausgabe ist 1 iff Zustand , d.h. .)

Schaltkreis:

               ┌─────────────┐
    x ────────→│ Übergangs-  │──→ z₁ᵗ⁺¹ ──→[D-FF₁]──→ z₁ᵗ ──┐
               │ funktion δ  │                            ├──→ (an δ)
               │             │──→ z₀ᵗ⁺¹ ──→[D-FF₀]──→ z₀ᵗ ──┘
               └─────────────┘                  │
                     ↑                          │
                     └──────────────────────────┘
                          ck ──→

  Ausgabe: y = z₁ᵗ ∨ z₀ᵗ  (Mealy: y = λ(z, x), hier aber nur von z abhängig
  nach Minimierung, da Ausgabemuster pro Zustand konstant)

Hinweis: Nach der Minimierung hat jeder Zustand ein konstantes Ausgabemuster (: immer 0, /: immer 1). Das reduzierte Verhalten entspricht faktisch einem Moore-Automaten. Die Ausgabefunktion ist .

Typische Klausuraufgabe

Aufbau (identisch in Klausur WS 2024/25 und Probeklausur SoSe 2026):

Gegeben: Mealy-Automat als Zustands- und Ausgangstafel mit 12 Zeilen (6 Zustände × 2 Eingaben).

  • a) (4P) Zustandsdiagramm zeichnen — alle 6 Zustände, alle Übergänge mit -Beschriftung, Startzustand markieren.
  • b) (4P) Hinreichende Äquivalenzbedingung erklären und begründen, warum sie hier auf kein Paar zutrifft. Schlüssel: bei gleicher Ausgabe sind die Folgezustände immer verschieden.
  • c) (2P) Automat auf 3 Zustände minimieren ( löschen). Verschmelzung: , , (zirkuläre Äquivalenz). Reduziertes Diagramm zeichnen.
  • d) (6P) Zustandskodierung wählen (2 FFs für 3 Zustände, Start auf ), Übergangstafel mit binären Codes aufstellen, Don't-Care für ungenutzten Code (), Startzustand der FFs angeben.

Zeitbudget: ~15 Minuten (90 min / 6 Aufgaben).

Tipps:

  • Bei a) systematisch vorgehen: jeden Zustand als Kreis, für und je eine Kante.
  • Bei b) Gruppen mit gleichem Ausgabemuster bilden, dann Folgezustände vergleichen.
  • Bei c) die zirkuläre Äquivalenz argumentieren: .
  • Bei d) Startzustand auf kodieren, Don't-Cares für ungenutzte Codes nutzen (vereinfacht Logik).

Übungsblätter

Blatt Aufgabe Punkte Inhalt Relevanz für A6
Blatt10 2 2+2+2 Mealy-Automat mit 6 Zuständen: Diagramm zeichnen, äquivalente Zustände fassen, Schaltwerk konstruieren + Zustandskodierung DIREKT — identischer Aufbau wie A6
Blatt10 3 1+2+2 Mealy-Automat mit 4 Zuständen: Ausgabefolge berechnen, Zustandstafel aufstellen, Ausgabefunktion bestimmen DIREKT — Ergänzung zu A6
Blatt10 4 2+2+2+1 Quine-McCluskey, KV-Diagramm, Kosten Indirekt (Logikminimierung für )

RISIKO: Dies ist das einzige Übungsblatt zum Thema sequentielle Schaltkreise. Keine weitere Übung vorhanden. Die Aufgaben 2 und 3 auf Blatt10 sind die einzige Vorbereitung für die 16-Punkte-Klausuraufgabe A6.

Quellen

Priorität

CRITICAL — 16 Punkte in der Klausur, identisch in Klausur und Probeklausur.

Risiko: Nur 1 Übungsblatt (Blatt10) als Vorbereitung. Das Thema ist komplex (mehrere Teilschritte: Diagramm → Äquivalenz → Minimierung → Kodierung → Tafel). Bei unzureichender Übung droht der Verlust von 16 Punkten = der Gesamtpunktzahl.

Empfehlung:

  1. Blatt10 Aufgabe 2 mehrfach lösen (mit verschiedenen Automaten)
  2. Den worked example oben vollständig nachvollziehen
  3. Den Syntheseweg aus k430 (Modulo-4-Zähler) durchrechnen
  4. Zustandsminimierung mit der zirkulären Äquivalenzmethode üben