Finite state machines

Moore machine

Moore machine is a finite state machine whose output depends only on current state. Finite in this case refers to number of states.

Moore machine

Moore machine can be defined as 6-tuple:

\begin{equation*} M = (S, S_0, \Sigma, \Lambda, T, G) \end{equation*}

Where:

S is finite set of states;
S₀ is the initial state;
Σ is the input alphabet;
Λ is the output alphabet
T is the transition function which maps state and input to next state
G is the mapping function which maps each state to the output alphabet

Moore machine can also be expressed as diagram as shown in the figure below.

Moore machine state diagram notation

Moore machine example with two states and four transitions

Moore machine can also be expressed as state transition table also known as flow table:

Input	Current state	Next state	Output
0	S0	S1	1
0	S1	S1	0
1	S1	S1	0
1	S0	S0	1

There are two critical paths distinguished in Moore machine: from input to flip-flop and from flip-flop to output.

Mealy machine

Mealy machine is a finite state machine where outputs is determined by both - current state and current inputs.

Mealy machine

Mealy machine state diagram notation

Mealy machine example with two states and four transitions

There are three critical paths distinguished in Mealy machine: from input to flip-flop; flip-flop to output and from input to output. Mealy machine with latched outputs is essentially Moore machine.

State minimization

Consider following non-minimized state diagram derived from the behavioural specification.

Mealy machine with single input I, single output and 7 states.

In order to minimize a FSM flow table can be used.

State tag	Next state		Output
State tag	I=0	I=1	I=0	I=1
S0	S1	S2	0	1
S1	S3	S4	1	1
S2	S5	S6	0	0
S3	S1	S2	0	1
S4	S1	S6	0	0
S5	S3	S2	1	1
S6	S1	S2	0	1

All output combinations belong to the same class:

\begin{equation*} \{S_0, S_3, S_6\}, \{S_1, S_5\}, \{S_2, S_4\} \end{equation*}

States that have the same future and same outputs are equivalent:

\begin{align*} E_0 = {S_0, S_3, S_6} \\ E_1 = {S_1} \\ E_2 = {S_2} \\ E_4 = {S_4} \\ E_5 = {S_5} \end{align*}

Minimized flow table basically substitutes states 3 and 6 with state 0:

State tag	Next state		Output
State tag	I=0	I=1	I=0	I=1
E0	E1	E2	0	1
E1	E0	E4	1	1
E2	E5	E0	0	0
E4	E1	E0	0	0
E5	E0	E2	1	1

Minimized finite state machine with 5 states.

State encoding

There are three main methods for encoding state of a state machine. When using binary of Gray code a decoder is required to determine the state. With one-hot encoding a decoder is not necessary.

Binary	Gray code	One-hot
000	000	00000001
001	001	00000010
010	011	00000100
011	010	00001000
100	110	00010000
101	111	00100000
110	101	01000000
111	100	10000000

Hamming distance for binary encoding varies. For Gray code hamming distance is 1 for linear state progression, which is preferred in some cases to save power as number of transistor switches is decreased. For hot-one encoding the hamming distance is always 2 regardless of transition.

VHDL KTH