[ENGN3213 Home]

   
Formal Definition of Finite State Machines

  We know that combinational logic circuits are described formally using Boolean algebra, a mathematical formalism. State machines are also described in mathematical terms, as follows.

Finite sets:

• X - input values

• Z - output values

• S - states

  These sets can be symbolic, not necessarily binary. E.g.

$$X = \{ {\rm\ up, \ down, \ stop } \ \}$$

These values or symbols reflect the meaning of the state machine specification. For binary implementation we would use a binary encoding.

Functions:

• $f : S \times X \to S$ - next state function

• $h : S \to Z$ - Moore-type output function, or
  $h : S \times X \to Z$ - Mealey-type output function

The function f is called the next state function, and h is called the output function.

  Equations. Moore machine:

$$% latex2html id marker 95 \begin{array}{rl} s(t+1) & = f(s(t)... ... z(t) & = h(s(t)) \ \ \ \ {\rm - output \ equation} \end{array}$$ (3)

  Equations. Mealey machine:

$$% latex2html id marker 106 \begin{array}{rl} s(t+1) & = f(s(t... ... & = h(s(t),x(t)) \ \ \ \ {\rm - output \ equation} \end{array}$$ (4)

In these equations t indicates time, and so the equations specify how the value of the state s=s(t+1) at time t+1 is determined by the state value s=s(t) at time t and the input x=x(t) at time t. The equations are a description of the sequential operation of the machine. The outputs are specified in either of two ways, corresponding to the names Moore machine and Mealey machine. The only difference is that a Mealey output may depend explicitly on the current input value x(t) whereas a Moore output depends only on the current state s(t).

The FSM black-box model is illustrated in Figure 50.

  

Figure 50: Finite state machine (FSM).

Example. For the Up/Down/Stop counter, we have

$$\begin{array}{rl} X & = \{ {\rm\ up, \ down, \ stop } \ \} \\... ..., \ s4 } \ \} \\ Z & = \{ {\rm\ odd, \ even } \ \} \end{array}$$

Example. For the vending machine controller, we have

$$\begin{array}{rl} X & = \{ {\rm\ coins, \ return, \ change-av... ...e-candy, \ return-all-coins, \ return-change } \ \} \end{array}$$

[ENGN3213 Home]