State Reduction of Synchronous Sequential Circuits

State Reduction:

The reduction of the number of flip-flops in a sequential circuit is referred to as the state
reduction problem. State-reduction algorithms are concerned with procedures for reducing the
number of states in a state table, while keeping the external input-output requirements
unchanged. Since (N) flip-flops produce (2N) states, a reduction in the number of states may
(or may not) result in a reduction in the number of flip-flops. An unpredictable effect in reducing
the number of flip-flops is that sometimes the equivalent circuit (with fewer flip-flops) may
require more combinational gates.

We will illustrate the state reduction procedure with an example. We start with a
sequential circuit whose specification is given in the state diagram shown in Fig. (1). In this
example, only the input-output sequences are important; the internal states are used merely to
provide the required sequences. For this reason, the states marked inside the circles are
denoted by letter symbols instead of their binary values. This is in constant to a binary counter,
where the binary value sequence of the state themselves is taken as the outputs.

There are an infinite number of input sequences that may be applied to the circuit; each
results in a unique output sequence. As an example, consider the input sequence
[01010110100] starting from the initial state (a). Each input of 0 or 1 produces an output of 0 or
1 and causes the circuit to go to the next state. the output and state sequence for the given of 0 and the circuit remains in state (a). With present state (a) and input of 1, the output is 0
and the next state is (b). With present state (b) and input of 0, the output is 0 and next state is (c).
Continuing this process, we find the complete sequence to be as follows:

State a a b c d e f f g f g a

Input 0 1 0 1 0 1 1 0 1 0 0

Output 0 0 0 0 0 1 1 0 1 0 0

In each column, we have the present state, input value, and output value. The next
state is written on top of the next column. It is important to realize that in this circuit, the states
themselves are of secondary importance because we are interested only in output sequences
caused by input sequences.

Now let us assume that we have found a sequential circuit whose state diagram has
less than seven states and we wish to compare it with the circuit whose state diagram is given
by Fig. (1). If identical input sequences are applied to the two circuits and identical outputs
occur for all input sequences, then the two circuits are said to be equivalent (as far as the
input-output is concerned) and one may be replaced by the other. 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.

We now proceed to reduce the number of states for this example. First, we need the
state table; it is more convenient to apply procedures for state reduction using a table rather
than a diagram. The state table of the circuit is listed in Table (1) and is obtained directly from
the state diagram.