Endelig tilstandsmaskin (FSM)

En endelig tilstandsmaskin (Finite State Machine, FSM) er en sekvensiell krets med et begrenset antall tilstander. Den defineres av tilstandsmengde $S$, starttilstand $S_0$, alfabet (innganger), overgangsrelasjon og utgangsfunksjon.

Moore vs. Mealy

Moore-maskin: Utgangen avhenger kun av nåværende tilstand. Utgangen endres bare ved tilstandsskifte. Typisk én tilstandssyklus forsinkelse på utgangen.
Mealy-maskin: Utgangen avhenger av nåværende tilstand OG nåværende inngang. Reagerer raskere, men utgangen kan endre seg inne i en tilstand hvis inngangen endrer seg.

Tilstandsdiagram og tilstandstabell

Et tilstandsdiagram er en rettet graf der noder er tilstander og piler er overganger merket med inngang (og utgang for Mealy). En tilstandstabell er en tabulær representasjon av det samme: kolonner for nåværende tilstand, inngang, neste tilstand og utgang.

Implementasjon

Implementasjon av en FSM i logikk skjer i tre trinn:

Tilstandskoding: Tildel bitkoder til tilstandene. Binær koding (minimalt antall biter), one-hot koding (én flip-flop per tilstand).
Neste-tilstand-logikk: Kombinatorisk logikk som beregner neste tilstand fra nåværende tilstand og inngang (forenkles med K-kart).
Utgangslogikk: Kombinatorisk logikk som beregner utgangen (Moore: bare fra tilstand; Mealy: fra tilstand og inngang).

Eksempel: Sekvensgjenkjenner (Moore)

Design en FSM som detekterer sekvensen «101» på en seriell inngang $X$. Tilstander: $S_0$ (ingen match), $S_1$ (sett «1»), $S_2$ (sett «10»), $S_3$ (sett «101», utgang $Z=1$).

Overganger:
$S_0 \xrightarrow{X=1} S_1$, $S_0 \xrightarrow{X=0} S_0$
$S_1 \xrightarrow{X=0} S_2$, $S_1 \xrightarrow{X=1} S_1$
$S_2 \xrightarrow{X=1} S_3$, $S_2 \xrightarrow{X=0} S_0$
$S_3 \xrightarrow{X=1} S_1$, $S_3 \xrightarrow{X=0} S_2$

Moore-utgang: $Z = 1$ kun i $S_3$. Med binær koding $S_0=00, S_1=01, S_2=10, S_3=11$ kan neste-tilstand-logikk utledes fra tilstandstabellen og forenkles med K-kart.

Studieguide: Tilstandsmaskiner (FSM)