chip design flow Introduction to Chip Designchapter_8.ppt

chip design flow Introduction to Chip Design

1. Chapter 8 -- Analysis and Synthesis of
Synchronous Sequential Circuits

2. The Synchronous Sequential Circuit Model
z
m
z
1
y
r
Clock
y
1
M em ory
Com binational
logic
..
.
..
.
......
x
n
x
1
Y
r
Y
1
Figure 8.1

3. Mealy Machine Model
C/0
A/1
C/0
0/0
1/1
1/0
1/0
0/1
0/0
(a)
(b)
X/Z
Present
state
Input x
0 1
N ext state/output
B/1
B/0
A/0
A
B
C
A
B C
Figure 8.2

4. Mealy Machine Timing Diagram -- Example 8.1
C lock
State
Input x
O utput z
0 1
A C
T0 T1 T2 T3 T4 T5
A B C AA
1 0 1 0
01 01 0 0
Figure 8.3

5. Moore Machine Model
X
Y
W
(a)
(b)
Present
state
Input x
0 1
Y
X
X
W
X
Y
O utputs
0
1
0
W/0 X/1
Y/0
0
1
1
00
1
Figure 8.4

6. Moore Machine Timing Diagram -- Example 8.2
Clock
State
Input x
O utput z
0
1
X Y
T0 T1 T2 T3 T4 T5
W
Y X XW
1
0
1
0
00
1
0
1
0
Figure 8.5

7. Analysis of Sequential Circuit State Diagrams --
Example 8.3
0/0 1/0
0/0
1/1
00 01 11
x/z
0/01/0
Figure 8.6

8. Timing Diagram for Example 8.3
C lock
x
y
1
y
2
z
0
1
0
1 1 1
0
1
0 0
0 00 0 0
1
0
1 1
0
0 00 1 1 11 1 1
0
0 00 0 0 10 1 0 0
Figure 8.7

9. Analysis of Sequential Circuit Logic Diagrams
(a )
(b )
C o m b in a tio n a l lo g ic
M e m o r y
C lo c k
D
C
Q
Q
D
C
Q
Q
0 1 2 3 4

D
t
t/D
t
y
y
Y
x
z
Figure 8.8

10. Timing Diagram for Figure 8.8 (a)
C lo ck
G litch
x
y
z
Y = D
0
t/D
t
0 1 2 3 4 5 6 7 8
0
0
0
1
0
1
0
1
1
0
1
0
0
0
0
1
0
1
0
0
1
1
0
0
1
1
0
0
1
1
0
Figure 8.9

11. State Table and State Diagram for Figure 8.8 (a)
A/0
0 1
A
B
B/0
B/0A/1
P resen t
sta te
x
kIn p u t
(c)
N ex t sta te/o u tp u t
0 /0
A B
1 /0
1 /1
0 /0
(d )
0 /0
0 1
1 /0
1 /00 /1
P re sen t
sta te
y
k
x
kIn p u t
(b )
N ex t sta te/o u tp u t
0 1
0
1
P re sen t
sta te
y
k
x
kIn p u t
(a )
x /
z
0
1
Figure 8.10

12. K-Maps for Circuit of Figure 8.8 (a)
0 1
A
B
Present
state
x
kInput
(c)(b)
0 1
0
1
y
k
x
k
(a)
0
1
1
0
0 1
0
1
y
k
x
k
0
0
0
1
y
k + 1
/z
k
A/0B/0
B/0A/1
Figure 8.11

13. Synchronous Sequential Circuit with T Flip-Flop --
Example 8.4
x
z
Q
C lock
y
y
CQ
T
Figure 8.12

14. Timing Diagram for Example 8.4
1 01 0 01
C lock
0x
y
z
T
0
1 00 0 110 1
1 00 0 010 0
2 43 6 851 70
Figure 8.13

15. State Table and State Diagram for Example 8.4
(a)
1/0
y
k + 1
/z
k
x/
z
0/0
1/1
y
k
x
k
y
k
x
k
y
k + 1
/z
k
(b)
P resen t
state
x
k
N ext state/outp ut
(c)
0/0
(d)
A B
0 1
A
B
B/0
B/0
A/0
A/1
0 1
0
1
1/0
1/0
0/0
0/1
0 1
1
0
Figure 8.14

16. K-Maps for Example 8.4
(a )
z
k
x
k
0 1
0
1
(b ) (c)
0
0
0
1
y
k
T
k
x
k
0 1
0
1
1
0
0
1
y
k
y
k + 1
x
k
0 1
0
1
1 *
1
0
0 *
y
k
(d )
y
k + 1
/z
k
x
k
0 1
0
1
1 /0
1 /0
0 /0
0 /1
y
k
Figure 8.15

17. Synchronous Sequential Circuit with JK Flip-flops --
Example 8.5
C lock
x
z
y
1
y
1
y
2
y
2
C
J
1
K
1
Q
Q
Q
Q
C
J
2
K
2
Figure 8.16

18. Timing Diagram and State Table for Example 8.5
C
x 0
y
1
y
2
J
1
= x y
2
K
1
= x
J
2
= x
K
2
= x + y
1
z = x y
1
y
2
0 1 1 1 1 00
1 0 0 0 1 1 10
0 0 0 1 0 1 10
0 0 0 0 0 1 00
0 0 /0
0 0 /0
0 0 /0
0 0 /0
0 1 /0
1 0 /0
1 1 /1
1 1 /0
y
1
y
2
x
0 1
0 0
0 1
1 1
1 0
(b )
(a )
Figure 8.17

19. K-Maps for Example 8.5
y
1
y
2
x
0
0 1
0 0
0 1
1 1
1 0
0
0 1
0 1
0 0
J
1
x
1
0 1
0 0
0 1
1 1
1 0
0
1 0
1 0
1 0
K
1
x
0
0 1
0 0
0 1
1 1
1 0
1
0 1
0 1
0 1
J
2
x
1
0 1
0 0
0 1
1 1
1 0
1
1 1
1 0
1 0
K
2
x
0
0 1
0 0
0 1
1 1
1 0
0
0 0
0 1
0 0
z
y
1
y
2
y
1
y
2
y
1
y
2
y
1
y
2
Figure 8.18

20. Generating the State Table From K-maps --
Example 8.5
x
0 011
1 011
1 01 0
0 01 0
Y
1
Y
2
Y
1
Y
2
/z
y
1
y
2
01
0 1
00
01
11
1 0
0 1
01 0 1
01 0 1
01 0 1
(a )
J
1
K
1
J
2
K
2
J
1
K
1
J
2
K
2
(b ) (c )
0 1
x
0 0
0 1
11
1 0
00
00
00
00
01
10
11
11
0 1
x
0 0
0 1
11
1 0
0 0/0
0 0/0
0 0/0
0 0/0
01 /0
10 /0
11 /1
11 /0
y
1
y
2
y
1
y
2
Figure 8.19

21. Synchronous Sequential Circuit Synthesis
(a ) C om p le te ly sp ec ifie d c irc u it
(b ) In com p le tely sp ec ifie d c irc u it
1 /1
1 /0
1 /0
1 /0
0 /0
0 /0
0 /- 0 /0
0 /0
0 /0
1 /1
0 /-
1 /-
1 /1
A B
C
D
A
B
C
0 1
x
A
B
C
D
D/0
D/0
D/0
D/0
B/0
C/0
B/0
A/1
0 1
x
A
B
C
B/-
B/0
A/-
-/1
C/1
A/-
Figure 8.20

22. Introductory Synthesis Example -- Example 8.6
( a ) S t a t e t a b le
S t a t e
y
1
0
1
1
0
x
0
0 1
0 0
0 1
1 1
1 0
0
0 1
0 0
1 0
0
0
1
1
y
2
A
B
C
D
Y
1
Y
2
/z
( d ) O u t p u t K - m a p
x
0
0 1
0 0
0 1
1 1
1 0
0
0 1
0 1
1 1
x
0
0 1
0 0
0 1
1 1
1 0
1
0 1
1 0
1 0
( b ) S t a t e
a s s i g n m e n t
D
1
(= Y
1
)
( c ) T r a n s i t io n
t a b le
D
2
(= Y
2
)
( e ) E x c it a t i o n K - m a p s
( f) L o g ic d ia g r a m
x
z
C loc k
y1
y1
y2
y2
z
Q
Q C
D1
Q
Q C
D2
0 1
x
A
B
C
D
A/0
A/0
B/0
C/1
B/0
C/1
D/0
D/0
0 1
x
0 0
0 1
1 1
1 0
0 0 /0
0 0 /0
0 1 /0
1 1 /1
0 1 /0
1 1 /1
1 0 /0
1 0 /0
y
1
y
2
y
1
y
2 y
1
y
2
y
1
y
2
Figure 8.21

23. Flip-flop Input Tables -- Example 8.6
S ta te
tr a n sition s
Q(t)Q(t + e)
(a ) D fl ip -fl op
0
0
1
1
0
1
0
1
R e q u ir e d
in p u ts
D(t)
0
1
0
1
S ta te
tr a n sition s
Q(t)Q(t + e)
(b ) C loc k e d S R
0
0
1
1
0
1
0
1
R e q u ir e d
in p u ts
S(t) R(t)
0
1
0
d
d
0
1
0
S ta te
tr a n sition s
Q(t)Q(t + e)
(c ) C loc k e d T fl ip -fl op
0
0
1
1
0
1
0
1
R e q u ir e d
in p u ts
T(t)
0
1
1
0
S ta te
tr a n sition s
Q(t)Q(t + e)
(d ) C loc k e d J K fl ip -fl op
0
0
1
1
0
1
0
1
R e q u ir e d
in p u ts
J(t)K(t)
0
1
d
d
d
d
1
0
Figure 8.22

24. Generating the JK Flip-flop Excitation Maps --
Example 8.7
x
0
0 1
0 0
0 1
1 1
1 0
0
0
d
d d
( c ) E x c i t a t io n m a p s
x
d
0 1
0 0
0 1
1 1
1 0
d
d d
1 0
0 0
x
0
0 1
0 0
0 1
1 1
1 0
1
d d
d d
1 0
K
1
J
2
1
d
x
d
0 1
0 0
0 1
1 1
1 0
d
1
d
0 1
d
K
2
0
J
1
( b ) E x c it a t i o n t a b l e
J
1
K
1
J
2
K
2
Y
1
Y
2
/z
0 1
x
0 0
0 1
1 1
1 0
0d
0d
d1
d0
0d
1d
d0
d0
( a ) T r a n s i t i o n t a b l e
y
1
y
2
0 1
x
0 0
0 1
1 1
1 0
0 0 /0
0 0 /0
0 1 /0
1 1 /1
0 1 /0
1 1 /1
1 0 /0
1 0 /0
0 1
x
0 0
0 1
1 1
1 0
0d
d1
d0
1d
1d
d0
d1
0d
y
1
y
2
y
1
y
2
y
1
y
2
y
1
y
2
y
1
y
2y
1
y
2
Figure 8.23

25. Clocked JK Flip-Flop Implementation --
Example 8.7
x
z
C loc k
y
1
y
2
Q
Q
C
J
1
Q
Q
C
J
2
K
1
K
2
y
2
y
1
Figure 8.24

26. Application Equation Method for Deriving
Excitation Equations -- Example 8.8
y
1
y
2
x
0
0 1
00
01
11
10
0
0 1
0 1
1 1
Y
1
y
1
x
0
0 1
00
01
11
10
1
0 1
1 0
1 0
Y
2
y
2
y
1
y
2
Figure 8.25

27. Sequence Recognizer for 01 Sequence --
Example 8.9
1/1
1/0 0/0
(d)
A B
0/01/0 0/0
(c)
A B
0/0
1/0
(b)
A B
0/01/0
(a)
A
Figure 8.26

28. Synthesis of the 01 Recognizer with SR Flip-flops
(b ) T r a n sition ta b le a n d outp ut m a p
C loc k
y
k + 1
x
yk
1
0 1
0
1
0
1 0
x
z
yk
0
0 1
0
1
0
0 1
x
B/0
0 1
A
B
A/0
B/0A/1
x
(a ) S ta te ta b le
(c ) E xc ita tion m a p s
S
y
k
1
0 1
0
1
0
d 0
x
R
y
k
0
0 1
0
1
d
0 1
x
z(d ) L og ic d ia g r a m
1 01 01
y
x
z
C loc k
S = x
R = x
0
0 0 10 10 0 0 0
1 01 1 1 11100
1
0
1
(e ) T im in g d ia g r a m
S
R
Q
C
y
k
Q
Figure 8.27

29. Realization of 01 Recognizer with T Flip-flops
(a ) C loc ke d T flip -flop
ex c ita tion m a p
T
x
0 1
0
1
1
0
0
1
y
k
(c) C loc ke d J K e x cita tion m a p s
J
x
0 1
0
1
1
d
0
d
y
k
K
x
0 1
0
1
d
0
d
1
y
k
T
x
y
Q
C
C loc k
Q
(b ) C loc ke d T flip -flop
im p le m e n ta tion
Figure 8.28

30. Design of a Recognizer for the Sequence 1111 --
Example 8.11
(a ) S ta te d ia g r a m
0 /0
0 /0
0 /0
1 /01 /0 1 /0
1 /1
0 /0
y
1
k
y
2
k
x
0 0
0 1
0 0
0 1
11
1 0
0 1
0 01 0
0 011
0 011
y
1
k+ 1
y
2
k+ 1
(b ) S ta te ta b le
(c ) T r a n sition ta b le
x
0
0 1
0 0
0 1
11
1 0
0
0 0
0 1
0 0
z
(d ) O utp ut m a p
A B C D
0 1
x
A
B
D
C
A/0
A/0
A/0
A/0
B/0
C/0
D/1
D/0
y
1
k
y
2
k
Figure 8.29

31. SR Realization of the 1111 Recognizer
x
d
0 1
0 0
0 1
11
1 0
1
1 1
1 0
d 0
R
2
x
d
0 1
0 0
0 1
11
1 0
d
d 0
1 0
1 0
R
1
y
1
k
y
2
k
x
0
0 1
0 0
0 1
11
1 0
0
0 1
0 d
0 d
S
1
x
0
0 1
0 0
0 1
11
1 0
1
0 0
0 d
0 1
S
2
y
1
k
y
2
k
y
1
k
y
2
k
y
1
k
y
2
k
Figure 8.30

32. Clocked T and JK Realizations of the 1111
Recognizer
x
d
0 1
0 0
0 1
1 1
1 0
d
d d
1 0
1 0
K
1
x
0
0 1
0 0
0 1
11
1 0
1
1 1
1 0
0 1
T
2
y
1
k
y
2
k
x
0
0 1
0 0
0 1
11
1 0
0
0 1
1 0
1 0
T
1
x
0
0 1
0 0
0 1
1 1
1 0
0
0 1
d d
d d
J
1
x
d
0 1
0 0
0 1
11
1 0
d
1 1
1 0
d d
K
2
x
0
0 1
0 0
0 1
11
1 0
1
d d
d d
0 1
J
2
y
1
y
2
x
0
0 1
0 0
0 1
11
1 0
0
0 1
0 1
0 1
Y
1
y
1
y
1
y
2
x
0
0 1
0 0
0 1
11
1 0
1
0 0
0 1
0 1
Y
2
y
2
(a ) C lo c k e d T e xc ita t ion m a p s
(b ) C lo c k e d J K e x c it a tio n m a p s
(c ) E x c it a t io n K - m a p s
y
1
k
y
2
k
y
1
k
y
2
k
y
1
k
y
2
k y
1
k
y
2
k
y
1
k
y
2
k
Figure 8.31

33. Clocked JK Flip-Flop Realization of a 1111
Recognizer
C lock
x
z
C
J
1
K
1
y
1
Q
Q
y
2
C
J
2
K
2
Q
Q
Figure 8.32

34. Design of a 0010 Recognizer
( d )
C o m e h e r e f o r a n
i n c o r r e c t i n p u t x = 0
C o m e h e r e f o r a n
i n c o r r e c t i n p u t x = 1
A B C D E
0 / 0
G
F
0 / 0 1 / 00 / 1
0 / 0
1 / 0
1 / 0
0 / 0
0 / 0
0 / 0
1 / 0
1 / 0
1 / 0
1 / 0
A B C D E
0 / 0
G
F
0 /0 1 / 00 / 1
0 / 0
1 / 0
1 / 0
0 /0
1 / 0
1 / 0
( c )
A B C D E
0 / 0
G
F
0 /0 1 / 00 / 1
1 / 0
1 / 0
0 / 0
1 / 0
1 / 0
( b )
A B C D E
0 / 0
G
F
0 / 0 1 / 00 / 1
( a )
0 1
x
A
B
C
D
G
B/ 0
C/ 0
G/ 0
B/ 1
G/ 0
A/ 0
A/ 0
D/ 0
A/ 0
A/ 0
0 1
x
A
B
C
D
E
F
G
B/ 0
C/ 0
G/ 0
E/ 1
C/ 0
B/ 0
G/ 0
F/ 0
F/ 0
D/ 0
F/ 0
F/ 0
F/ 0
F/ 0
( e ) ( f )
0 / 0
1 /0
1 / 0
A B C D
1 / 0
G
0 / 0
1 / 0
0 / 1
0 / 0 1 / 0
0 / 0
( g )
Figure 8.33

35. Design of a Serial Binary Adder
(d )
C
QD
a
i
b
i
C
i
S
i
C
i-1
C loc k
0 0 /0
0 1 /1
1 0 /1
11 /0
0 0 /1
0 1 /0
1 0 /0
11 /1
c
i-1
= 0 c
i-1
= 1
a
i
b
i
/s
i
(b )
0 1
a
i
b
i
c
i-1
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
0
0
1
0
1
1
1
0
1
1
0
1
0
0
1
c
i
s
i
(c )
(a )
S h ift re g iste r A
S e r ia l
a d d e r
b
i
s
i
S h ift re g iste r B
a
i
Figure 8.34

36. Design of a Four-State Up/Down Counter
(a ) S ta te d iag ra m
z = 0
0 1
23
z = 3
1
0
z = 1
z = 2
0 1
x
0
1
2
3
1 /0
2 /1
3 /2
0 /3
3 /0
0 /1
1 /2
2 /3
(b ) S ta te tab le
y
1
k
y
2
k
y
1
k + 1
y
2
k + 1
0 1
x
0 0
0 1
1 1
1 0
0 1
1 0
0 0
1 1
1 1
0 0
1 0
0 1
(c ) T r an sition ta b le
y
1
y
2
x
0
0 1
0 0
0 1
1 1
1 0
d 1 d
1 d 0 d
d 1 d 0
d 0 d 1
J
1
K
1
J
1
K
1
(d ) E xcitation m ap s
y
1
y
2
x
1
0 1
0 0
0 1
1 1
1 0
d 1 d
d 1 d 1
d 1 d 1
1 d 1 d
J
2
K
2
J
2
K
2
10
0
1
10
Figure 8.35

37. An Implementation of the Up/Down Counter
C lock
1
L E D s
y
2
x
Q
Q
C
J
1
K
1
y
1
Q
Q
C
J
1
K
1
Figure 8.36

38. Design a BCD Counter
(a )
(b )
x
x
y
3
k
y
2
k
y
1
k
y
0
k
0 0 0 0
0 0 0 1
0 0 1 0
0 0 11
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 11
11 0 0
11 0 1
11 1 0
11 1 1
0
0 0 0 0
0 0 0 1
0 0 1 0
0 0 11
0 1 0 0
0 1 0 1
0 11 0
0 11 1
1 0 0 0
1 0 0 1
d d d d
d d d d
d d d d
d d d d
d d d d
d d d d
1
0 0 0 1
0 0 1 0
0 0 11
0 1 0 0
0 1 0 1
0 11 0
0 11 1
1 0 0 0
1 0 0 1
0 0 0 0
d d d d
d d d d
d d d d
d d d d
d d d d
d d d d
y
3
k + 1
y
2
k + 1
y
1
k + 1
y
0
k + 1
0
1
2
3
4
5
6
7
8
9
0
0
1
2
3
4
5
6
7
8
9
1
1
2
3
4
5
6
7
8
9
0
Figure 8.37 (a) and (b)

39. Design of the BCD Counter (con’t)
( c )
x
0
0
0
0
0
0
0
0
0
d
d
d
d
d
d
d
d
1
0
0
0
0
0
0
0
1
d
d
d
d
d
d
d
d
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1
y
3
k
y
2
k
y
1
k
y
0
k
J
3
x
0
d
d
d
d
d
d
d
d
0
0
d
d
d
d
d
d
1
d
d
d
d
d
d
d
d
0
1
d
d
d
d
d
d
K
3
x
0
0
0
0
0
d
d
d
d
0
0
d
d
d
d
d
d
1
0
0
0
1
d
d
d
d
0
0
d
d
d
d
d
d
J
2
x
0
d
d
d
d
0
0
0
0
d
d
d
d
d
d
d
d
1
d
d
d
d
0
0
0
1
d
d
d
d
d
d
d
d
K
2
x
0
0
0
d
d
0
0
d
d
0
0
d
d
d
d
d
d
1
0
1
d
d
0
1
d
d
0
0
d
d
d
d
d
d
J
1
x
0
d
d
0
0
d
d
0
0
d
d
d
d
d
d
d
d
1
d
d
0
1
d
d
0
1
d
d
d
d
d
d
d
d
K
1
x
0
0
d
0
d
0
d
0
d
0
d
d
d
d
d
d
d
1
1
d
1
d
1
d
1
d
1
d
d
d
d
d
d
d
J
0
x
0
d
0
d
0
d
0
d
0
d
0
d
d
d
d
d
d
1
d
1
d
1
d
1
d
1
d
1
d
d
d
d
d
d
K
0
Figure 8.37 (c)

40. Realization of the BCD Counter Design
Figure 8.37 (d) and (e)
y
1
k
y
0
k
y
2
k
y
3
k
0
0 00 11 11 0
0 0
0 1
1 1
1 0
d d 0
0 d d 0
0 d d d
0 d d d
x = 0
0
0 00 11 11 0
d d 0
0 d d 0
1 d d d
0 d d d
x = 1
( d )
C l o c k
L i g h t s
x
y
2 J
2
K
2
C
y
1 J
1
K
1
C
y
0 J
0
K
0
C
( e )
y
3 J
3
K
3
C

41. K-map For Y
1
in Example 8.16
0
y
2
y
0
0 d 0
0 0 d 0
1 1 d d
1 1 d d
y
3
y
1
0
y
2
y
0
0 d 0
1 1 d 0
0 0 d d
1 1 d d
y
3
y
1
y
Figure 8.38

42. Robot Controller Floor Plan -- Example 8.17
Exit
M ovable
blocks
B ottom view
of robot
Robot
W heels
Sensor
(X)
Figure 8.39

43. Robot Controller Design
Figure 8.40 (a) -- (e)
y
1
y
2
(a )
N S/z
1
z
2
0 /0 0
1 /0 1
X/Z
1
/Z
2
A B
CD
0 /0 0
1 /1 0
1 /1 0
0 /0 0
1 /0 1
0 /0 0
0 1
x
A
B
C
D
A/0 0
C/0 0
C/0 0
A/0 0
B/0 1
B/0 1
D/1 0
D/1 0
Y
1
Y
2
/z
1
z
2
0 1
x
0 0
0 1
11
1 0
0 0 /0 0
11 /0 0
11 /0 0
0 0 /0 0
0 1 /0 1
0 1 /0 1
1 0 /1 0
1 0 /1 0
(b ) (c )
0 0
0 0
0 1
0 1
0 1
x
0 0
0 1
11
1 0
0 1
0 1
0 0
0 0
0 1
x
0 0
0 1
11
1 0
0 0
1 0
1 1
0 1
0 1
0 0
0 1
11
1 0
z
1
z
2
Y
1
0 1
1 1
1 0
0 0
0 1
x
Y
2
(d ) (e )
0 0
0 1
11
1 0
x
y
1
y
2
y
1
y
2
y
1
y
2
y
1
y
2
y
1
y
2

44. Robot Controller Realization
x
C loc k
Q
1
Q
1
J
1
Q
2
Q
2
J
2
K
1
K
2
z
1
z
2
(f)
Figure 8.40 (f)

45. Candy Machine Controller Design -- Example 8.18
N
C oin
detector
R
C
(a)
(b)
N D/R C
00/00
00/00
00/00
10/10,
01/11
10/00
01/10
C ontrol
unit
R elease
candy
R elease
change
D
10/00
10/00
01/00
10
15
0
5
00/00
01/00
Figure 8.41

46. Algorithmic State Machines (ASMs)
0 1
(a) (b) (c)
State_Name
M oore outputs
Input
M ealy
outputs
Figure 8.42

47. ASM Representation of a Mealy Machine
0 1
z = 0
X
0
1 0
z = 0
X
z = 1
z = 0
X
z = 0 z = 1
1
A
B
C
( a )
1 /0
1 /1 1 /0
0 /0
C
A
B
0 /1
0/0
(b )
X/Y
Figure 8.43

48. ASM Representation of a Moore Machine
0 1
X
0
0 1
X
X
1
A
z = 0
B
z = 1
C
z = 0
1
0
0
C /0
A /0
B /110
(a )
(b )
1
Figure 8.44

49. Eight-Bit Two’s Complementer ASM --
Example 8.19
Figure 8.45
0
z = 0
x
1
z = 1
x
z = 0
0
z = 1
1
B
C om plem ent
rem aining bits
A
L ook for
first 1 bit

50. Binary Multiplier Controller -- Example 8.20
Figure 8.46
R e g is te r A
R e g is te r M
0
4
M u lip lie r
2 -b it
c o u n te r
C
o u t
A d d e r
P ro d u c t
H a lt
C o n tro l
u n it
C
0
Q
0
S u m
A d d
S h ift
R e g is te r c on tro l sig n a ls
S ta r tA d dS h ift
0
R e g is te r Q
4 4
4
4
M u lip lic a n d
4
4
1
Q
0
0
C
0
S ta r t
1
H a lt
A 0
M M u ltip lie r
Q M u ltip lic a n d
C N T 0
S h ift rig h t A: Q
C N T C N T + 1
A A + M
H a lt 1
(a ) (b )

51. One-Hot State Assignments
Sequential Assignment One-hot Assignment
State y1y0 y3y2 y1y0
A 00 0001
B 01 0010
C 10 0100
D 11 1000
Table 8.1

52. ASM Design Using One-Hot State Assignments
Figure 8.47 (a) -- (b)
A
B
S ta te A
B e g in C loc k
(a)
D
A
Q
A
C
S ta te B
D
B
Q
B
C
S ta te A
S ta te B
S ta te C
.
.
.
B
C loc k
D
A
Q
A
C
D
B
Q
B
C
.
.
.
.
.
.
C
D
C
Q
C
C
A
(b)

53. ASM Design Using One-Hot Assignments (con’t)
Figure 8.47 (c)
M o or e
o u tp u t
z = 1
M e a ly
o u tp u t
0 1
I n p u ts
S ta t e A
S ta te B
S ta t e C
C lo c k
D
A
Q
A
C
A
D
A
Q
B
C
z
D
A
Q
C
C
x
(c )

54. One-hot Design of A Multiplier Controller --
Example 8.21
Figure 8.48
C l o c k
D
A
Q
A
C
D
B
Q
B
C
D
D
Q
D
C
D
C
Q
C
C
B e g i n
S t a r t
A d d
Q
0
H a l t
C
0
S h i f t
C l o c k
D
B
Q
B
C
B e g i n
z
x
S t a r t
D
A
Q
A
C
(a )
( b )

55. Incompletely Specified Circuits -- Detonator
(Example 8.22)
x zD etonator
(a) (b)
1/0 1/0 1/0 1/1
0 1
x
A
B
C
D
A/0
-/-
-/-
-/-
B/0
C/0
D/0
-/1
(c)
0 /0
A B C D -
Figure 8.49

56. Detonator Example K-maps
y
2
y
1
x
00
0 1
00
01
11
10
01
d d10
d dd d
d d11
y
2
k +1
y
1
k +1
x
0
0 1
00
01
11
10
0
d 0
d 1
d 0
z
x
0
0 1
00
01
11
10
0
d 1
d d
d 0
T
2
x
0
0 1
00
01
11
10
1
d 1
d d
d 1
T
1
y
2
y
1
y
2
y
1
y
2
y
1
Figure 8.50

57. Detonator Realization
Clock
x
C
T
1
z
y
1
y
2
Q
Q C
T
2
Q
Q
Figure 8.51

58. Sate Assignments and Circuit Realization
( a )
Y
2
Y
1
/z D
2
0 1
x
0 0
0 1
1 1
1 0
0d/1
1 0 / 0
d d/0
d d/d
0 0 /0
0 0 /0
1 0 /1
0 1 /1
x
1
0 1
0 0
0 1
1 1
1 0
d 0 0
1 0 0 0
d d 1 0
d d 0 1
x
1
0 1
0 0
0 1
1 1
1 0
0
0 0
0 1
d 1
z D
1
D
2
D
1
T
2
x
0
0 1
0 0
0 1
1 1
1 0
d 0 0
1 1 0 1
d d 0 1
d d 1 1
T
1
T
2
T
1
J
2
x
0
0 1
0 0
0 1
1 1
1 0
d 0 d
1 d 0 d
d d d 0
d d d 1
K
2
J
2
K
2
J
1
x
d
0 1
0 0
0 1
1 1
1 0
d 0 d
d 1 d 1
d d d 1
d d 1 1
K
1
J
1
K
1
( b ) ( c )
( d ) ( e )
y
2
y
1
y
2
y
1
y
2
y
1
y
2
y
1
y
2
y
1
y
2
y
1
Figure 8.52