Page 577 - Engineering Digital Design

11.12 STATE MINIMIZATION 547

the state code assignments are chosen by using special partitioning methods that avoid
ORGs and other serious timing problems. These partitioning methods, not involving state
assignment rules 1 and 2, are used to construct the state table from which the S matrix is
derived. These methods are also applicable to synchronous D flip-flop designs, but with an
increased number of state variables required — the price of avoiding ORGs.

11.12 STATE MINIMIZATION

Formal state minimization procedures are available that involve state tables, implication
charts, merger graphs, and the like. Further Reading at the end of this chapter cites references
on this subject. However, such procedures are rarely used in modern state machine design.
For state machines of up to moderate complexity, a minimum or near minimum number of
states can be obtained simply by visual inspection of the state diagram or state table. In fact,
it may not be desirable to obtain a minimum number of states for a particular FSM. There
are occasions where a nonminimum number of states may lead to a more optimum set of
NS and output functions for a state machine. Furthermore, if the state machine is relatively
complex and if it is to be implemented, say, with an FPGA or PAL, it really doesn't matter
whether or not a minimum number of states exist. In cases where hardware capability far
exceeds the state machine requirements, it is only necessary to make certain that the FSM
performs its tasks properly — hardware limitation is not a factor.
In this section, a visual method is used to demonstrate how states can be merged to
produce a more optimum design of relatively simple state machines. Consider the require-
ments for the pulse width adjuster (PWA) in Fig. 11.46, which has a single input X and a
single output P. It is required that X be synchronized in phase with the RET D flip-flops
of the memory. The PWA is to function according to the operation table in Fig. 11.46a,
where the pulse widths are adjusted to one, two, or three clock periods, TCK, as indicated.
The timing diagram in Fig. 11.46b illustrates the pulse width relationship between the in-
put pulse waveform X and the output waveform P relative to seven states a,b,c,d,e, /,
andg.
The state diagram that corresponds to the requirements of the PWA set forth in Fig. 11.46
is shown in Fig. 11.47a. An inspection of the seven states in the state diagram and in the
state table of Fig. 11.47b indicates that two merging operations are possible. If states c and
d are merged to form state c', and if states e, /, and g are merged to form state d', there
results the much simplified state diagram of Fig. 11.47c. This four-state PWA, functions
the same as the seven-state PWA, but at a significant reduction in hardware cost. There
are other advantages to state reductions. For example, in the case of the four-state PWA
in Fig. 11.47c, it can be coded in Gray code so as to eliminate any possibility of ORGs
occurring in the output. However, state reductions alone may or may not eliminate static
hazards in the output.
Notice how easy it is to recognize the merging patterns of the states in Fig. 11.47. Such
visual approaches to the state-merging process can be carried out even on much more
complex FSMs. Usually it is not necessary to apply formal techniques to this process. The
point is that, if the FSM is to be implemented with an array logic device, such as a ROM,
PLA, FPGA, or PAL, it may not matter whether or not a state-minimum design exists. What
is more important is the correct operation of the FSM. Of course, if the FSM is to be