Zustandsautomaten

Ziele

  1. Verständnis der Funktionsweise von zustandsbasierten sequenziellen Logiksystemen
  2. Verständnis der Funktionsweise und Aufbau von Zustandsautomaten
  3. Entwurf von Zustandsautomaten mit VHDL

RTL und Zustandsautomaten

  • Der Bereich von digitalen Systemen reicht von steuerungs- bis zu datenintensiven Systemen.

  • Systeme mit Steuerungsschwerpunkt sind rein reaktive Systeme die auf äußere Ereignisse reagieren.

  • Systeme mit Datenschwerpunkt benötigen Datenverarbeitung mit hohen Datendurchsatz, wie. z.B. im Bereich der digitalen Signal- und Bildverarbeitung.

  • Der Kontrollfluss ist sequenziell aufgebaut, d.h. in mehrere zeitlich getrennte Einzelschritte zerlegt.

  • Wie in vorherigen Kapiteln gezeigt wurde, kann ein sequenzielles System in einen Kontroll- und Datenfluss aufgeteilt werden, mit Steuerungs- und Datenpfadeinheiten.

RTL und Zustandsautomaten

  • Datenpfade enthalten
    1. Arithmetische und logische Recheneinheiten (ALUs),
    2. Logik für den Datentransport zwischen einzelnen Datenpfadeinheiten bzw. Stufen,
    3. Register für die Datenzwischenspeicherung und zum Aufbau von Pipelines, die dadurch gekennzeichnet sind, dass zu einem Zeitpunkt t sich mehrere Datensätze in unterschiedlichen Bearbeitungsstufen befinden können (Erhöhung des Datendurchsatzes).

RTL und Zustandsautomaten

figrtldp1

Abb. 1. Datenpfade mit RTL

Endliche Zustandsautomaten

  • Datenpfade werden mit endlichen Zustandsautomaten gesteuert (FSM: Finite State Machine).

  • Steuerungseinheit ⇔ FSM

  • Datenpfadeinheiten können zyklisch wechselnde Datensätze, d.h. Datenströme, bearbeiten.

  • Der Zustandsautomat muss die einzelnen Operationen im Datenpfad steuern und koordinieren:

    1. Datentransport (Multiplexer)
    2. Datenspeicherung (Register)
    3. Operationen und Daten selektieren (ALU + Multiplexer)

  • Datenpfade bestehen aus einer Vielzahl von regulären Strukturen (einfach zu optimieren),

  • Kontrolleinheiten (FSM) bestehen i.A. aus irregulären Strukturen (“zufällig” strukturierte Logik - schwierig/aufwendig zu optimieren).

Endliche Zustandsautomaten

Partitionierte Sequenzielle Maschinen
Partitionierung einer sequenziellen Maschine (z.B. Mikroprozessor) in einen Daten- und Steuerungspfad macht die Architektur deutlicher und strukturierter, und vereinfacht den System/Hardware-Entwurf.

figrtl3

Abb. 2. Allgemeine Architektur und Strukturierung einer Sequenziellen Maschine.

Endliche Zustandsautomaten

Ein Zustandsautomat ist ein allgemeines sequenzielles System, dessen Reaktionen und Ausgangswerte außer vom aktuellen Zustand auch von den Eingangsgrößen abhängen. Man unterscheidet im wesentlichen zwei verschiedene Typen von Automaten:

Moore-Automat

Bei diesem Automaten hängen die Ausgangssignale nur vom aktuellen Zustand ab, welcher von Eingangssignalen aus der Vergangenheit und vorherigen Zuständen bestimmt wurde.

Mealy-Automat

Bei diesem Automaten hängen die Ausgangssignale zusätzlich von den Eingangssignalen ab.

Endliche Zustandsautomaten

figfsm1

Abb. 3. Blockschaltbild eines allgemeinen Automaten (ohne Datenpfad des RTL Systems!)

Der Moore-Automat

  • Der Eingangsvektor Et = E1 .. EM bezeichnet die Gesamtheit der Eingangsgrößen, den Signalen Ei.
  • Der Zustandsvektor Zt = Z1 .. ZN bezeichnet den inneren Zustand des Systems. Bezeichnung innerer Zustände durch Umstand dass Signale Z nach außen nicht direkt sichtbar sind.
  • Index t und t+1 bezeichnen aktuellen und nächsten Zustand bzw. Vektorwert.

figfsmmoore1

Abb. 4. Architektur des Moore-Automaten

Der Moore-Automat

Zustandsübergänge

  • Die Zustandsübergänge werden mittels Zustandsdiagrammen (State-Transition-Diagram) dargestellt.
  • Jeder Zustand und jeder Übergang wird getrennt eingezeichnet.
  • Die Bedingung E für einen Zustandswechsel wird am Übergangspfeil vermerkt. Innerhalb des Zustandssymbol wird der Zustand und der damit verknüpfte Ausgangsvektor angegeben.

figfsmstates1

Abb. 5. Zustandsdiagramme

Der Moore-Automat

Beispiel: Bitfolgenerkennung

  • Es soll eine Bitfolge auf vorgegebene Muster untersucht werden.

  • Problem-Definition

    • Eingangsvektor E={00,01,10,11}
    • Ausgangsvektor A={0,1} → Impulsfolge detektiert?
    • Z(Σ) ← Folge von Eingangsvektoren (01,11,10)
    • Zustandsvektor Z={Z0,Z1,Z2,Z3}

Der Moore-Automat

figfsmex2

Abb. 6. Zustandsdiagramm für Bitfolgenerkennung.

Der Moore-Automat

VHDL-Implementierung

  1. Partitionierung:

    • Zustandsübergang und Speicherung von Z
    • Kontrollpfad Σ
    • Datenpfad Π

  2. Zustandskodierung: abstrakt 

type states is (Z0,Z1,Z2,Z3);
signal state,state_next: states;
  1. Aufteilung des Zustandsautomaten in drei Prozesse:
    1. process state_trans
    2. process sigma
    3. process pi

Der Moore-Automat

Zustandsspeicher Z 

state_trans: process(clk,reset,state_next)
begin
  if clk event and clk= 1 then
    if reset= 1 then
      state <= Z0;
    else
      state <= state_next;
    end if;
  end if;
end process state_trans;

Ausgangslogik 

pi: process (state)
begin
  case state is
    when Z3 => A <= 1 ;
    when others => A <= 0 ;
  end case;
end process pi;

Der Moore-Automat

Schaltnetzwerk 

sigma: process(state,E)
begin
  case state is
    when Z0 =>
      if E=”01” then state_next <= Z1
      else state_next <= Z0; end if;
    when Z1 =>
      if E=”11” then state_next <= Z2
      elsif E=”01” then state_next
      else state_next <= Z0; end if;
    when Z2 =>
      if E=”10” then state_next <= Z3
      elsif E=”01” then state_next
      else state_next <= Z0; end if;
    when Z3 =>
      if E=”01” then state_next <= Z1
      else state_next <= Z0;
      end if;
  end case;
end process sigma;