     [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. These values or symbols reflect the meaning of the state machine specification. For binary implementation we would use a binary encoding.

Functions:

• - next state function

• - Moore-type output function, or - Mealey-type output function

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

Equations. Moore machine: (3)

Equations. Mealey machine: (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. Example. For the Up/Down/Stop counter, we have Example. For the vending machine controller, we have      [ENGN3213 Home]

ANU Engineering - ENGN3213