Page 171 - DCAP108_DIGITAL_CIRCUITS_AND_LOGIC_DESIGNS

Digital Circuits and Logic Design

Notes 10.2.1 State Reduction

The problem of state reduction is to find ways of reducing the number of states in a sequential
circuit without altering the input-output relationships.

In other words, to reduce the number of states, redundant states should be eliminated. A redundant
state S is a state which is equivalent to another state S.
j
i
Two states are said to be equivalent if, for each member of the set of inputs, they give exactly the
same output and send the circuit either to the same state or to an equivalent state.
m
Since, ‘m’ flip-flops can describe a state machine of up to 2 states, reducing the number of states
may (or may not) result in a reduction in the number of flip-flops. For example, if the number of
states is reduced from 8 to 5, we still need 3 flip-flops.
However, state reduction will result in more do-not-care states. The increased numbers of do-
not-care states can help obtain a simplified circuit for the state machine.

Consider the shown state diagram.

Figure 10.6: State Diagram

The state reduction proceeds by first tabulating the information of the state diagram into its
equivalent state-table form (as shown in the table 10.4).
The problem of state reduction requires identifying equivalent states. Each N state is replaced
by 1 state.
Consider the following state table.
States ‘g’ and ‘e’ produce the same outputs, i.e. ‘1’ and ‘0’, and take the state machine to same next-
states, ‘a’ and ‘f’, on inputs ‘0’ and ‘1’ respectively. Thus, states ‘g’ and ‘e’ are equivalent states.
We can now remove state ‘g’ and replace it with ‘e’ as shown.

We next note that the above change has caused the states’ and ‘f’ to be equivalent. Thus, in the
next step, we remove state ‘f’ and replace it with ‘d’.

There are no more equivalent states remaining. The reduced state table results in the following
reduced state diagram.

166 LOVELY PROFESSIONAL UNIVERSITY