Sometimes certain properties of sequential circuits may be used to reduce the number of gates and flip-flops during the design.

**STATE REDUCTION &
ASSIGNMENT**

Sometimes
certain properties of sequential circuits may be used to reduce the number of
gates and flip-flops during the design.

The
problem of state reduction is to find ways of reducing the number of states in
a sequential circuit, while keeping the external input-output relationships
unchanged.

**For example, suppose a sequential circuit is
specified by the following seven-state diagram:**

There
are an infinite number of input sequences that may be applied; each results in
a unique output sequence. Consider the input sequence 01010110100 starting from
the initial state a:

An
algorithm for the state reduction quotes that:

“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.”

**Now apply this algorithm to the state table of
the circuit:**

States g
and e both go to states a and f and have outputs of 0 and 1 for x = 0 and x =
1, respectively.

**The procedure for removing a state and
replacing it by its equivalent is demonstrated in the following table**:

Thus,
the row with present state g is removed and stage g is replaced by state e each
time it occurs in the next state columns. Present state f now has next states e
and f and outputs 0 and 1 for x = 0 and x = 1. The same next states and outputs
appear in the row with present state d. Therefore, states f and d are
equivalent and can be removed and replaced with d.

**The final reduced state table is:**

**The state diagram for the above reduced table
is:**

This
state diagram satisfies the original input output specifications.

**Applying the input sequence previously used,
the following list is obtained:**

Note
that the same output sequence results, although the state sequence is
different.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Digital Electronics : Synchronous and Asynchronous Sequential Circuits : State Reduction & Assignment |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.