6.3. State Minimization Using an Implication Chart (or Table)
The Implication Chart Method is a systematic approach to find the states that can be combined into a
single reduced state. This method is cumbersome to do by pencil and paper, but it is well-suited for
automation because it is a systematic approach.
Minimization procedure with an Implication Chart
A 3-bit sequence detector example is used here to demonstrate the Implication Chart use in state
minimization.
Problem Statement
Design a binary sequence detector with the minimum number of states that outputs a 1
whenever the machine has observed the serial input sequence 010 or 110.
Step 1) Use the problem statement to write the Present/Next State Table
(It may help to first do a state diagram.)
Input Sequence
Present State
Next State
X=0 X=1
Output
X=0 X=1
Reset S 0 S 1 S 2 0 0
0
1
S 1
S 2
S 3 S 4
S 5 S 6
0 0
0 0
00
01
10
11
S 3
S 4
S 5
S 6
S 3 S 4
S 5 S 6
S 3 S 4
S 5 S 6
0 0
1 0
0 0
1 0
Step 2) Draw an implication Chart which allows entries relating every state with every other
state as shown below:
- Label vertically from last state (S6) to second state (S1)
- Label horizontally from first state (S0) to next to the last state (S6)