1.1 The State Machine

A typical logic system can be represented by a general model called the state machine, as shown in Figure 1-1 . A state machine contains three basic elements – the state, the next-state function, and the output function.

The state of a machine serves as the memory storage from previous instances and is used to determine future behavior. For a state machine to function, it must have sufficient information from the current inputs to determine both the next state and the output. This memory is usually made using a group of flip-flops called the state register. The flip-flops within the state machine are called state variables.

Each state of a machine has a subsequent state determined by the next-state function. The state time is normally determined by a periodic input to the state register. At the end of each state time, the next state becomes the present state. The next-state function, $g$, depends upon the present state, $X$, and the inputs or qualifiers, $Q$. If the basic state time is represented by $T$, and $k$ is a counting integer, then $X\left(kT\right)$ represents the state at a discrete time $kT$. Using this terminology, the next-state function, $g$, can be defined as follows:

$X\left(\right(k+1)T=g[X\left(kT\right),Q\left(kT\right)]$

The notation can be simplified by using a delay operator, which is an arrow pointing in the direction of the next-state replacement, as shown below:

The output function generates a set of outputs or instructions, $I$, based on the state and the input information for each state. The output function, $f$, is expressed as follows:

$I\left(kT\right)=f\left[X\right(kT),Q(kT\left)\right]$

The notation can be simplified as follows: