State Reduction

Any design process must consider the problem of minimizing the cost of the final circuit. The two most obvious cost reductions are reductions in the number of flip-flops and the number of gates.

The number of states in a sequential circuit is closely related to the complexity of the resulting circuit. It is therefore desirable to know when two or more states are equivalent in all aspects. The process of eliminating the equivalent or redundant states from a state table/diagram is known as state reduction.

Example: Let us consider the state table of a sequential circuit shown in Table 6.

Present State

Next State

x = 0

x = 1

Output

x = 0

x = 1

B	C
F	D
D	E
F	E
A	D
B	C

1	0
0	0
1	1
0	1
0	0
1	0

Table 6. State table

It can be seen from the table that the present state A and F both have the same next states, B (when x=0) and C (when x=1). They also produce the same output 1 (when x=0) and 0 (when x=1). Therefore states A and F are equivalent. Thus one of the states, A or F can be removed from the state table. For example, if we remove row F from the table and replace all F's by A's in the columns, the state table is modified as shown in Table 7.

Present State

Next State

x = 0

x = 1

Output

x = 0

x = 1

B	C
A	D
D	E
A	E
A	D

1	0
0	0
1	1
0	1
0	0

Table 7. State F removed

It is apparent that states B and E are equivalent. Removing E and replacing E's by B's results in the reduce table shown in Table 8.

Present State

Next State

x = 0

x = 1

Output

x = 0

x = 1

B	C
A	D
D	B
A	B

1	0
0	0
1	1
0	1

Table 8. Reduced state table

The removal of equivalent states has reduced the number of states in the circuit from six to four. Two states are considered to be equivalent if and only if for every input sequence the circuit produces the same output sequence irrespective of which one of the two states is the starting state.