next up previous contents index

[ENGN3213 Home]

Equivalence and Redundancy

  Other issues to consider in state machine design and analysis include the possibility of redundant states and equivalence of state machines.

Two state machines M1 and M2 are input-output equivalent if they have the same input-output behaviour, i.e.

If the same input sequence is applied to both machines, then the output sequences are indentical. This should hold for all input sequences.

Equivalent machines need not have the same number of states. Indeed, some states may be redundant as far as input-output equivalence is concerned.  

Example. The four state up/down/stop counter is input output equivalent to the state machine of Figure 86.


  
Figure 86: Input-output equivalent to up/down/stop counter.
\begin{figure}
\begin{center}
\epsfig{file=images/seqdesimg5.eps}\end{center}\end{figure}

Example. The one hot implementation of the vending machine has many redundant states.


next up previous contents index

[ENGN3213 Home]

ANU Engineering - ENGN3213