State Assignment Methods - Dr. Le Dung

11/26/2012
1
State Assignment Methods
Dr. Le Dung
Faculty of Electronics and Telecommunications
Hanoi University of Science and Technology
State assignment to design FSM
S
X
0 1
A C/0 D/0
B C/0 A/0
C B/0 D/0
D A/1 B/1
S Q1 Q0
A 0 0
B 0 1
C 1 0
D 1 1
State Assignment (1)4 states Æ 2 Flip-Flops
Æ using Q1 Q0 to assign
D1 Q1
Q1clk
D0 Q0
Q0clk
S
X
0 1
00 10/0 11/0
01 10/0 00/0
10 01/0 11/0
11 00/1 01/1
Z 0 1
00
01
11 1 1
10
Q1Q0
x
D1 0 1
00 1 1
01 1
11
10 1
x
D0 0 1
00 1
01
11 1
10 1 1
x Z = Q1Q0
D1=Q1X+Q0X
D0=Q1Q0+Q1X+Q0X
Combinational circuits
2 Inv + 5xAND2 + 3xOR2
Dr. Le Dung 2 Hanoi University of Science and Technology
11/26/2012
2
Number of state assignments
Dr. Le Dung 3 Hanoi University of Science and Technology
where NFF is total number of flip-flops
NS is number of states
NS NFF NSA
2 1 2
3 2 24
4 2 24
5 3 6720
6 3 20160
24 assignments for 4 states
Dr. Le Dung 4 Hanoi University of Science and Technology
No. A B C D No. A B C D 
1 00 01 10 11 13 10 00 01 11 
2 00 01 11 10 14 10 00 11 01 
3 00 10 01 11 15 10 01 00 11 
4 00 10 11 01 16 10 01 11 00 
5 00 11 01 10 17 10 11 00 01 
6 00 11 10 01 18 10 11 01 00 
7 01 00 10 11 19 11 00 01 10 
8 01 00 11 10 20 11 00 10 01 
9 01 10 00 11 21 11 01 00 10 
10 01 10 11 00 22 11 01 10 00 
11 01 11 00 10 23 11 10 00 01 
12 01 11 10 00 24 11 10 01 00 
11/26/2012
3
State assignment problem
S
X
0 1
A C/0 D/0
B C/0 A/0
C B/0 D/0
D A/1 B/1
S Q1 Q0
A 0 0
B 0 1
C 1 0
D 1 1
S Q1 Q0
A 1 0
B 1 1
C 0 0
D 0 1
S Q1 Q0
A 0 0
B 0 1
C 1 1
D 1 0
Assignment (1) Assignment (2) Assignment (17)
Dr. Le Dung 5 Hanoi University of Science and Technology
Z = Q1Q0
D1=Q1X+Q0X
D0=Q1Q0+Q1X+Q0X
Assignment (1)
2 Inv + 5xAND2 + 3xOR2
Z = Q1Q0
D1=Q1X+Q0X
D0=Q1Q0+Q1X+Q0X
Assignment (17)
2 Inv + 5xAND2 + 3xOR2
Z = Q1Q0
D1=Q1X+ Q1Q0+Q1Q0X
D0=Q1X+ Q0X+Q1Q0X
Assignment (2)
2 Inv + 6xAND2 + 4xOR2
State assignment methods
Dr. Le Dung 6 Hanoi University of Science and Technology
• Guideline methods:
+ Straightforward
+ One-hot
+ Minimum-bit-change
• “Near-optimal” methods:
Dolotta & McCluskey method, Weiner and Smith 
method, Torng method, Curtis method, Story method, 
Haring method
(See Ref. for 9.4.4 p619)
11/26/2012
4
Straightforward assignment method
Dr. Le Dung 7 Hanoi University of Science and Technology
• Uses the binary representation of the state number as code 
(s0→000, s1→001, ... s6→110, s7→111, ......)
• Mostly used when the state number has a physical meaning
(E.g. a counter whose count value is sent to a display)
• This method is dangerous for glitches and leads to non-
minimal area and power consumption: multiple bits have to 
change at each state transition (multiple bit-changes 
seldomly happen concurrently; each bit-change requires 
some logic to implement it; each bit-change consumes 
power)
One-hot assignment method
Dr. Le Dung 8 Hanoi University of Science and Technology
• Each state has 1 flip-flop. Only 1 flip-flop in set state, others 
in reset state.
• NFF = NSÆ only useful for small number of states.
• ASM diagram is translated to One-hot FSM model 
+ Short design time.
+ Ideal for FPGA implementations.
s Q0 Q1 Q2 Q3
A 1 0 0 0
B 0 1 0 0
C 0 0 1 0
D 0 0 0 1
11/26/2012
5
Minimum-bit-change assignment method
Dr. Le Dung 9 Hanoi University of Science and Technology
• This method try to minimize the total number 
of bit-changes for all state transitions.
• This method is mostly used when area and
power need to be minimized.
• This method bases on 
+ Some rules
+ Equipvalent rule (rule 0)
+ Adjacent rules (rule 1 + rule 2)
+ Rule 3 + Rule 4 based on the implication graphs
+ Partitioning
Equivalent rule (Rule 0)
Dr. Le Dung 10 Hanoi University of Science and Technology
Not all NSA assignments are unique with respect to the 
resulting excitation and output functions (F and G implement). 
because the rule (Rule0) : Some state assignments are 
equivalent each others, if one assignment is derived from 
other one by 
Æ complementing a state variable (Qi)
or
Æ swapping 2 state variables (Qi and Qj) 
S Q1 Q0
A 0 0
B 0 1
C 1 0
D 1 1
S Q1 Q0
A 1 0
B 1 1
C 0 0
D 0 1
S Q1 Q0
A 0 0
B 1 0
C 0 1
D 1 1
Complementing Q1 Swapping Q1and Q0Assignment (1)
11/26/2012
6
Equivalent state assignments
S
X
0 1
A C/0 D/0
B C/0 A/0
C B/0 D/0
D A/1 B/1
S Q1 Q0
A 0 0
B 0 1
C 1 0
D 1 1
S Q1 Q0
A 1 0
B 1 1
C 0 0
D 0 1
S Q1 Q0
A 0 0
B 1 0
C 0 1
D 1 1
Dr. Le Dung 11 Hanoi University of Science and Technology
Assignment (1) Swapping Complementing Q1
Z = Q1Q0
D1=Q1X+Q0X
D0=Q1Q0+Q1X+Q0X
Assignment (1)
2 Inv + 5xAND2 + 3xOR2
Z = Q1Q0
D1=Q1X+Q0X
D0=Q1Q0+Q1X+Q0X
Complementing Q1
2 Inv + 5xAND2 + 3xOR2
Z = Q1Q0
D1=Q1X+ Q1Q0+Q0X
D0=Q0X+ Q1X
Swapping
2 Inv + 5xAND2 + 3xOR2
Number of unique state assignments
Dr. Le Dung 12 Hanoi University of Science and Technology
11/26/2012
7
3 unique assignments for 4-state FSM
Dr. Le Dung 13 Hanoi University of Science and Technology
Q1Q0
UA (1)
UA (2)
UA (3)
Q1Q0
Q1Q0
cQ1 cQ0 swap swap cQ1 swap swap
Unique assignments in comparison
S
X
0 1
A C/0 D/0
B C/0 A/0
C B/0 D/0
D A/1 B/1
S Q1 Q0
A 0 0
B 0 1
C 1 0
D 1 1
S Q1 Q0
A 0 0
B 1 1
C 0 1
D 1 0
S Q1 Q0
A 0 0
B 0 1
C 1 1
D 1 0
UA (1) UA (2) UA (3)
Dr. Le Dung 14 Hanoi University of Science and Technology
Z = Q1Q0
D1=Q1X+Q0X
D0=Q1Q0+Q1X+Q0X
Unique assignment (1)
2 Inv + 5xAND2 + 3xOR2
Z = Q1Q0
D1=Q1Q0+Q0X
D0=Q1X+Q0X+Q1Q0X
Unique assignment (3)
2 Inv + 6xAND2 + 3xOR2
Z = Q1Q0
D1=Q1X+ Q1Q0+Q1Q0X
D0=Q1X+ Q0X+Q1Q0X
Unique assignment (2)
2 Inv + 6xAND2 + 4xOR2
11/26/2012
8
Adjacent rules for UAs
Dr. Le Dung 15 Hanoi University of Science and Technology
A
B
C
x=0
x=0
Rule 1 Î A adj B 
in assignment
A
D
C
xy=00
xy=01
Rule 2 Î C adj D 
in assignment
Compare the adjacencies of states on UAs
S
X
0 1
A C/0 D/0
B C/0 A/0
C B/0 D/0
D A/1 B/1
S Q1 Q0
A 0 0
B 0 1
C 1 0
D 1 1
S Q1 Q0
A 0 0
B 1 1
C 0 1
D 1 0
S Q1 Q0
A 0 0
B 0 1
C 1 1
D 1 0
UA (1) UA (2) UA (3)
Dr. Le Dung 16 Hanoi University of Science and Technology
Rule 1:
A adj B, A adj C
Rule 2:
C adj D, C adj A
B adj D, A adj B
Q1
Q0
0 1
0
1
UA (1)
A B
C D
A adj B, A adj C, 
C adj D, B adj D
Q1
Q0
0 1
0
1
UA (1)
A B
D C
A adj B, C adj D 
Q1
Q0
0 1
0
1
UA (1)
A C
D B
A adj C, B adj D 
That is why UA (1) is the best assignment
11/26/2012
9
Implication graph
Dr. Le Dung 17 Hanoi University of Science and Technology
S
X
0 1
A E/0 B/0
B A/1 D/1
C E/0 A/0
D A/0 B/1
E D/0 C/0
Complete Implication Graph
Rule 3 on Implication graph
Dr. Le Dung 18 Hanoi University of Science and Technology
S
X
0 1
A E/0 B/0
B A/1 D/1
C E/0 A/0
D A/0 B/1
E D/0 C/0
Rule 1:
A adj C, B adj D, A adj D
Rule 2:
A adj D, B adj E,
A adj B, C adj D
Partially Complete Implication Graph
Rule 1 and Rule 3 are more important than Rule 2
11/26/2012
10
Rule 4 on Implication graph
Dr. Le Dung 19 Hanoi University of Science and Technology
S
X
0 1
A E/0 B/0
B A/1 D/1
C E/0 A/0
D A/0 B/1
E D/0 C/0
Rule 1:
A adj C, B adj D, A adj D
Rule 2:
A adj D, B adj E,
A adj B, C adj D
A is “most transferred to” Æ A = 000
then A should adj D, adj E. B adj D, B adj D 
All rules on Implication graph
Dr. Le Dung 20 Hanoi University of Science and Technology
S
X
0 1
A E/0 B/0
B A/1 D/1
C E/0 A/0
D A/0 B/1
E D/0 C/0
Rule 1:
A adj C, B adj D, A adj D
Rule 2:
A adj D, B adj E,
A adj B, C adj D
A is “most transferred to” Æ A = 000
then A should adj D, adj E. B adj D, B adj D 
Q2
Q1Q0
Saving 111, 110, 101 
11/26/2012
11
Partitioning on Implication Graph
Dr. Le Dung 21 Hanoi University of Science and Technology
S
X
Z
0 1
A D C 0
B F C 0
C E B 0
D B E 1
E A D 0
F C D 0
DE
AB
AC
FE
BC
DF
AF
DC
BE
Complete implication graph
Closed partition 1
Closed partition 2
Closed partition 1 Æ P1 = { (A,B,C) ; ( D, E, F) }
Closed partition 2 Æ P2 = { (A,F) ; (D,C) ; (B,E) }
State Assignment by Using Partitions 
Dr. Le Dung 22 Hanoi University of Science and Technology
S
X
Z
0 1
A D C 0
B F C 0
C E B 0
D B E 1
E A D 0
F C D 0
Q1Q0
Q2
0 1
0 0 A D
01 B E
11 C F
10
Using only P1
Q1Q0
Q2
0 1
0 0 A F
01 B E
11 C D
10
Using P1 & P2
P1 = { (A,B,C) ; ( D, E, F) }
P2 = { (A,F) ; (D,C) ; (B,E) }
Block 0 Block 1
Design with D-FF ?