Page 570 - Engineering Digital Design

540 CHAPTER 11 / SYNCHRONOUS FSM DESIGN CONSIDERATIONS

for a "pencil-and-paper" design of an FSM than is the state table. There are, however, several
important usages of state tables, among them being their use for CAD purposes explored in
Section 11.11.
The state table provides a relatively simple means of obtaining the state code assignments
required for the optimum or near-optimum NS and output logic of an FSM by using D flip-
flops as the memory. There are three state assignment rules by which this can achieved,
listed in descending order of priority:

Rule 1 (The "into rule"): Make logically adjacent assignments to present states
that branch "into" a common next state, provided that their input conditions are
the same.
Rule 2 (The "from rule"): Make logically adjacent assignments to states that
are the next states "from" a common present state, provided that their input
conditions are logically adjacent.
Rule 3 (The output rule): Make logically adjacent assignments to states having
the same outputs. Rule 3 is relatively unimportant except where large numbers
of outputs are involved.

In Fig. 11.43a use is made of the next state table in applying rules 1 and 2 to the FSM
of Fig. 11.42. Here, rule 1 has the highest priority and is applied to state adjacency sets in
columns under constant input conditions. Thus, by rule 1, states within the set {abc} should
be made logically adjacent, and those within set {de} should be made adjacent, both sets be-
ing under the same input condition IQ — Sf . Similarly, states within sets {ae} and {bd}, under
input condition I\=ST, should be made logically adjacent, etc. Rule 2, of lesser priority,
is applied to the rows of the state table as indicated in Fig. 11.43a. Now the input conditions
must be logically adjacent. For example, in present state d, states with sets {de}, {cd}, and
{ce} should be made logically adjacent. State sets that appear in both rule 1 and rule 2 are
given the highest priority and are indicated in dashed boxes. These are followed in priority by
those that appear only in rule 1. Those of least priority appear only in rule 2. Notice that not
all sets appearing in rules 1 and 2 can be accommodated, hence the reason to prioritize, as just
discussed. For example, it is not possible to include set {ce} together with the higher priority
sets.
By incorporating rules 1 and 2, as indicated in Fig. 11.43a, there results the following
three-bit state assignments:

a = 000, 6 = 001, c = 011, </=101, and e = 100.

These assignments are used in the state diagram of Fig. 11.43b and will generate an optimum
or near-optimum set of next-state functions, but only in three bits. It is possible, albeit
unlikely, that a four-bit set could result in a more optimum set of next-state functions.
However, no attempt will be made to explore this possibility. Note that ORGs are possible
in both P and Q.
The NS K-maps are plotted from the state diagram in Fig. 11.43b, assuming the use
of D flip-flops, and are given in Fig. 11.44 together with the output K-maps. Also
shown are the minimum covers for the K-maps that yield the following NS and output