Microsoft Word - Digital Logic Design v_4_6a

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)