Digital Systems Design

Reduction of State Tables

State Assignment

Dr. Aqeel Sahi

Intro.
- State Table Reduction:
● Reducing the number of states in the state table minimizes the required
logic and may reduce the number of flip-flops.
● A reduced state table leads to less complex flip-flop input equations,
further optimizing the design.

- Effect of Reduction:
● For example, reducing a table from 9 to 8 states can reduce the number
of flip-flops from 4 to 3, cutting down on hardware.
Intro.
- State Assignment:
● After state reduction, assign binary codes to states (state assignment).
● The choice of state assignment affects the efficiency and complexity of the
circuit.
● Finding an optimal state assignment is challenging but can be guided by design
principles (covered in Sections 15.7-15.8).

- Next Steps:
● After assigning states, derive flip-flop input equations to realize the sequential
circuit.
 FSM Design Flow
Statement of Problem

State Graph

Choice of F/F
State Table

Derivation of
Reduction of States
F/F Input Equation and

State Assignment Z Output Equation

Circuit Realization and

Timing Chart
Unit 15 2
 Equivalent States
Equivalent states “  ”
2 machines: N1, N2
state P in N1
state Q in N2

N1 P Z1
X ↓ P  Q iff R  S and Z1=Z2
R
Z2
N2 Q λ(P,x) = λ(Q, x) : output
↓
S
δ(P,x) = δ(Q, x) : next state
x: any single input
Unit 15 4
 Elimination of Redundant States (1/5)
When setting up states, some extra states may be included
eliminate these states

A previous example
Check 4 consecutive inputs
X Z
as a group , then reset
Z = 1 when X = 0101 or 1001
CLK

A brute force approach:

Reset state A, checks 3 consequent bits of every possible combinations.
After the 4th bit coming-in, give output and reset to state A

Unit 15 5
 Elimination of Redundant States (2/5)

A
0 1

B C
0 1 0 1

D E F G
0 1 0 1 0 1 0 1

H I J K L M N P
0 1 0 1/1 0 1/1 0 1
0 1 0 1 0 1 0 1

Unit 15 6
Initial State and State Transitions:

● State A is the reset state, where the system begins.

○ If the input is 0, the system transitions to State B.
○ If the input is 1, the system transitions to State C.
● From State B:
○ A 0 leads to State D (indicating the sequence "00" has been received).
○ A 1 leads to State E (indicating the sequence "01" has been received).
● Similarly, from other states (C, D, E, etc.), each input (0 or 1) drives the
system to the next state, which keeps track of the input sequence.
● Once the fourth bit is received, the system returns to State A (reset state).
● The output is 0 unless the system is in State J or L and receives a 1, in
which case the output is 1 (this corresponds to having detected the
sequences "0101" or "1001").
 Elimination of Redundant States (3/5)
Input P.S. N.S. Present Output
Sequence x  0 x  1 x  0 x  1
Reset A B C 0 0
0 B D E 0 0
1 C F G 0 0
00 D H I 0 0
01 E J K 0 0
10 F L M 0 0
11 G N P 0 0
000 H A A 0 0
001 I A A 0 0
010 J A A 0 1
011 K A A 0 0
100 L A A 0 1
101 M A A 0 0
110 N A A 0 0
111 P A A 0 0
Unit 15 7
Eliminating Redundant States:

● Row Matching is used to simplify the state table by identifying equivalent

states (states that behave the same way for all inputs).
● For example:
○ States H and I have identical next states and outputs, so they are
considered equivalent. State I is replaced with H, and State I is removed
from the table.
○ Similarly, states K, M, N, P all behave the same way as H, so they can be
replaced by H and deleted.
○ States J and L also have the same behavior, so L is replaced with J and
eliminated.
● Further, States D and G, and E and F are identified as equivalent, so they
can be merged, reducing the number of states.
 Elimination of Redundant States (4/5)
Equivalent states: the same N.S. & output
Input P.S. N.S. Present Output
Sequence x  0 x  1 x  0 x  1
Reset A B C 0 0
0 B D E 0 0
1 C E F DG 0 0
00 D H H I 0 0
01 E J H K 0 0
10 E F J L HM 0 0
11 D G H N H P 0 0
000 H A A 0 0
001 H I A A 0 0
010 J A A 0 1
011 H K A A 0 0
100 J L A A 0 1
101 HM A A 0 0
110 H N A A 0 0
111 H P A A 0 0
Unit 15 8
 Elimination of Redundant States (5/5)
P.S. N.S. Output
x  0 x 1 x  0 x 1
A B C 0 0
B D E 0 0
C E D 0 0
-/0 A 0/0
D H H 0 0
0/0 1/0 1/1
E J H 0 0
H A A 0 0 B C
1/0 1/0
J A A 0 1
0/0 0/0

D E
After eliminating redundant states, the state 1/0
table is reduced, and a simplified state diagram -/0 0/0
is created. The final state diagram is much
simpler and identical to the previous one, except
for the state designations. H J
Unit 15 9
 Determination of State Equivalence by Using an
Implication Table (1/4)

Ex: P.S. N.S.

x  0 x  1 Z
a da c 0
b f h 0
c ec da 1
d a e 0
e c a 1
f f b 1
g b h 0
h c g 1

Unit 15 10
 Determination of State Equivalence by Using an
Implication Table (2/4)
Implication chart construction N.S.
1. State comparison by implied P.S. x  0 x  1 Z
pair (only for the-same-output a d c 0
pair)
b f h 0
d–f
b c–h Output shall be the same c e d 1
c ╳ ╳ d a e 0
d a–d a–f ╳ e c a 1
c–e e–h
e ╳ ╳ a–d ╳ f f b 1
c–e
b–d a–b g b h 0
f ╳ ╳ e–f ╳ c–f
b–d a–b h c g 1
g c–h b–f ╳ e–h ╳ ╳
h ╳ ╳ d–g ╳ a–g b–g ╳
c–e c–f
a b c d e f g
Unit 15 11
 Determination of State Equivalence by Using an
Implication Table (3/4)
2. Check implied pair iteratively N.S.
P.S. x  0 x  1 Z
a da c 0
b f h 0
d–f ad c ec da 1
b c–h
c ╳ ╳ ce d a e 0
e c a 1
d a–d a–f ╳
c–e e–h f f b 1
e ╳ ╳ a–d ╳
c–e g b h 0
b–d a–b
f ╳ ╳ e–f ╳ c–f
b–d a–b h c g 1
g c–h b–f ╳ e–h ╳ ╳
h ╳ ╳ d–g ╳ a–g b–g ╳
c–e c–f
a b c d e f g
Unit 15 12
 Determination of State Equivalence by Using an
Implication Table (4/4)

N.S.
P.S. x0 x 1 Z
a a c 0
ad b f h 0
ce c c a 1
f f b 1
g b h 0
h c g 1
Unit 15 13
 Equivalent Sequential Circuits (1/3)
Definition : N1  N2 if P in N1  Q in N2
or S in N2  T in N1

N1 N2
Ex: x  0 x 1 x  0 x 1 x  0 x 1 x  0 x 1
A B A 0 0 S0 S3 S1 0 1
B C D 0 1 S1 S3 S0 0 0
C A C 0 1 S2 S0 S2 0 0
D C B 0 0 S3 S2 S3 0 1

Method 1:By 1/0 S0

observation A A  S2 0/0 1/0
0/0 0/0 1/0
1/1 B  S0 0/0
1/1
0/0 C  S3 S2 S1
C B
1/1 D  S1 0/0 0/0
0/0 1/0 S3
D 1/1
Unit 15 14
 Equivalent Sequential Circuits (2/3)
N1 N2
x  0 x 1 x  0 x 1 x  0 x 1 x  0 x 1
A B A 0 0 S0 S3 S1 0 1
B C D 0 1 S1 S3 S0 0 0
C A C 0 1 S2 S0 S2 0 0
D C B 0 0 S3 S2 S3 0 1

C  S3 A  S3
Method 2: By implication S0
D  S1 C  S1
table B  S3 C  S3
1. Construct implication S1
A  S0 B  S0
table by listing all state B  S0 C  S0
S2
pairs. X out pairs with A  S2 B  S2
different outputs C  S2 A  S2
S3
D  S3 C  S3
A B C D
Unit 15 15
 Equivalent Sequential Circuits (3/3)
C  S3 A  S3
S0
D  S1 C  S1 2. X out additional
B  S3 C  S3 nonequivalent state pairs
S1
A  S0 B  S0
B  S0 C  S0
S2
A  S2 B  S2
C  S3 A  S3
C  S2 A  S2 S0
S3 D  S1 C  S1
D  S3 C  S3
B  S3 C  S3
A B C D S1
A  S0 B  S0
B  S0 C  S0
S2
A  S2 B  S2
C  S2 A  S2
S3
D  S3 C  S3
A B C D
A  S2 B S0 C S3 D S1
Unit 15 16
 Incompletely Specified State Tables (1/3)

Ex: X B
Z
Circuit A Sequential Circuit Circuit C
Subsystem

A can only give 100, 110

“0” 100 received
B gives if at the 3rd bit
“1” 110 received

t0 t1 t2 t0 t1 t2
X 1 0 0 Z   0
1 1 0   1
If don’t cares are present, the state table is called incompletely specified
Unit 15 17
 Incompletely Specified State Tables (2/3)

State Graph State Table

N.S. Z
S0 P.S. x  0 x 1 x  0 x 1
0/0 1/– 0/–
S0 – S1 – –
S1
0/– 1/–
0/1
S1 S2 S3 – –
S2 S0 – 0 –
S2 S3
S3 S0 – 1 –
1/– 1/–

Unit 15 18
 Incompletely Specified State Tables (3/3)
N.S. Z
P.S. x  0 x  1 x  0 x  1
S0 – (S0) S1 – (0) –
S1 S 2S0 S3 – (1) –
S2 S0 (S ) 0
– 1 –
S3 S0 – (S3) 1 –
States reduction
N.S. Z
P.S. x0 x 1 x  0 x 1
S0 S0 S1 0 –
S1 S0 S1 1 –

Unit 15 19