Chapter5: Synchronous Sequential Logic

Lecture6- State Reduction and Assignment

Engr. Arshad Nazir, Asst Prof
Dept of Electrical Engineering
Spring 2023 SEECS 1
 Objectives
• Study State Reduction using Row Matching and Implication
Table Methods
• Make Binary State Assignments

Spring 2023 2
 State Reduction and Assignment
• The analysis of sequential circuits starts from a circuit diagram and culminates
in a state table or diagram whereas the design of a sequential circuit starts
from a set of specifications and culminates in a logic diagram.
• State reduction is one of the important steps in the design of sequential
circuits.
• The reduction of the number of flip flops is referred to as the state reduction
problem.
➢ Algorithms have been developed that aim at reducing the number of states
in the state diagram, while keeping the external input-output requirements
unchanged.
➢ Since m flip flops produce 2m 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. Spring 2023 3
State Reduction and Assignment Cont…
• There are two methods of state reduction:-
➢ Row Matching (Row Elimination)
➢ Implication Table (Pairs Chart)
• In the design procedure, initially states are labeled with alphabets
and are subsequently assigned binary codes to derive expressions.

Spring 2023 4
State Reduction using Row-Elimination
Method Example

Spring 2023 5
 State Reduction using Row-Elimination
Method Example Cont…
• What we would like to find with our example is an equivalent FSM with fewer
states that still generates the same output sequences for identical input
sequences.
• It must be remembered that any two states are equivalent if for the same set of
inputs, both produce the same outputs and are driven into the same next-states or
equivalent states.
• 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.
• Let the given input sequence be 01010110100…
• We can describe the behavior of given sequential circuit by listing input-output
sequence as shown below:-
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 1Spring020231 0 0 6
State Reduction using Row-Elimination
Method Example Cont…
• From the given state diagram of Mealy FSM, we can list State Table
as shown below:-

Spring 2023 7
State Reduction using Row-Elimination
Method Example Cont…
• 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.
– When two states are equivalent, one of them can be removed
without altering the input-output relationships.
• In our example, we look for two present states that go to the same
next state and have the same output for both input combinations.
➢ States g and e are examples, so g can be eliminated and
substituted with e in the leftover state table. This results in one
row representing state g struck/eliminated in the state table.
➢ This state equivalency steps will continued till all non-equivalent
states are left. The resulting state tables are shown next.

Spring 2023 8
State Reduction using Row-Elimination
Method Example Cont…

eg&df

Spring 2023 9
State Reduction using Row-Elimination
Method Example Cont…
• From reduced state table we can draw state diagram with fewer
states as shown below:-

Spring 2023 10
State Reduction using Row-Elimination
Method Example Cont…
• We can once again evaluate the circuit behavior with the same input i.e
01010110100…
• The input out-put sequence after state reduction is listed below:-

State a a b c d e d d e d e 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

• Input-output sequence comparison of both circuits reveals that they are

equivalent.

Spring 2023 11
State Reduction using Implication Table
Method Example
• We can also use Implication Table (sometimes referred to as a “pairs
chart”) to check each pair of states for possible equivalence. The non-
equivalent pairs are systematically eliminated until only the equivalent
pairs remain.
• Implication tables provide graphic method of identifying redundant states
and use grid array to list the possible state equivalencies.
• After equivalent states are found, we can apply row-matching reduction
algorithm to eliminate states. This method is more reliable because using
this method we can find equivalency of those states whose next-states
are not same but equivalent.
• If desired, row matching method can be used to partially reduce the state
table before constructing implication table.

Spring 2023 12
State Reduction using Implication Table
Method Example Cont…

Figure: Structure of Implication Table

Spring 2023 13
State Reduction using Implication Table
Method Example Cont…
• We will use the example of state table shown below to illustrate the
implication table method:-
Present Next State Output (z)
State
Input (x) Input (x)
0 1 0 1

A A B 0 0
B D C 0 1
C F E 0 0
D D F 0 0
E B G 0 0
F G C 0 1
G A F 0 0

Spring 2023 14
State Reduction using Implication Table
Method Example Cont…
• Construct implication table of the form as shown in the next slide. This chart has
a square for every possible pair of states. A square in column i and row j
corresponds to state pair i-j. Thus the squares in the first column correspond to
state pairs A-B, A-C etc.
• A≡B: iff A≡D, B≡C & outputs are same. As outputs of A and B are different so
these states are not equivalent and we inset a cross in the square A-B. Likewise
we compare each state with all other states.
• Note that the squares above the diagonal are not included in the chart. Why?
How do you interpret crosses in some squares?
• After the implication table has been constructed and some of the non-
equivalent states found shown with crosses due to different outputs, go for first
pass. The Implication Table after First and second passes will be as shown in the
next slide.
• Another pass will result in no further elimination of non-equivalent states. The
squares not crossed represent equivalent
Spring 2023
states i.e A≡D≡G and B≡F. 15
State Reduction using Implication Table
Method Example Cont…

The initial Table After the first pass After the second pass

Spring 2023 16
State Reduction using Implication Table
Method Example
• Now we can use row elimination to reduce the state table .
Present Next State Output (z)
State Present Next State Output (z)
State
Input (x) Input (x)
0 1 0 1 Input (x) Input (x)
0 1 0 1
A A B 0 0
A A A B 0 0
B D C 0 1
C FB E 0 0 B A C 0 1
D D F 0 0 C B E 0 0
E B G A 0 0 E B A 0 0
F GA C 0 1
G A F 0 0

Spring 2023 17
 State Assignment
• In order to design a sequential circuit with physical components, it is
necessary to assign coded binary values to the states.
➢ For a circuit with m states, the codes must contain n bits where
2n >= m
➢ In our example,
o The unreduced table requires assignment of 7 states
o The reduced table requires assignment of 5 states
• Binary assignment made in both cases requires three flip-flops with
one and three unused states respectively.
• Unused states of a combination of binary values become our don’t
care conditions which normally leads to a reduction in the number of
gates used for implementation.

Spring 2023 18
 State Assignment Cont…
• Many different assignments can be made to reduced states. The
simplest way to code small state sets is to use the first five integers in
binary counting order
• Another similar assignment is to use the Gray code
• Another possible assignment is the one-hot

Spring 2023 19
 Reduced State Table with Binary
Assignment
• The binary form of the state table is used to derive the combinational
circuit part of the sequential circuit.

Spring 2023 20
The End

Spring 2023 21