Resolução cap7-Introdução aos sistemas digitais-Ercegovac

Prévia do material em texto

99
Chapter 7
Exercise 7.1
Input:
x(t) 2 fa; b; cg
Output:
z(t) 2 fp; qg
Function:
z(t) =
(
q if number of a's in x(0; t� 1) is even and number of b's is odd.
p otherwise
State:
s(t) = (s
a
(t); s
b
(t))
s
a
(t) = (number of a's) mod 2
s
b
(t) = (number of b's) mod 2
Initial state:
s
a
(0) = 0
s
b
(0) = 0
Transition function:
s
a
(t+ 1) =
(
s
a
(t)
0
if x(t) = a
s
a
(t) otherwise
s
b
(t+ 1) =
(
s
b
(t)
0
if x(t) = b
s
b
(t) otherwise
Output function:
z(t) =
(
q if s(t)=(0,1)
p otherwise
The state transition and output table is shown below. The state diagram for the system is
presented in Figure 7.1 on page 100.
Input
PS x = a x = b x = c
(0,0) (1,0) (0,1) (0,0) p
(0,1) (1,1) (0,0) (0,1) q
(1,0) (0,0) (1,1) (1,0) p
(1,1) (0,1) (1,0) (1,1) p
NS Output (z)
100 Solutions Manual - Introduction to Digital Design - February 3, 1999
(0,0)/p (0,1)/q
(1,1)/p(1,0)/p
b
c
b
b
b
a
aaa
c c
c
Figure 7.1: State Transition Diagram of Exercise 6.1
Exercise 7.2
Input: decimal digit x(t) 2 f0; 1; 2; 3; 4; 5; 6; 7; 8; 9g.
Output: z(t) 2 f0; 1; 2; 3; 4g.
Function:
z(t) = (
t
X
i=0
x(i)) mod 5
State: s(t) 2 f0; 1; 2; 3; 4g
Initial state: s(0) = 0
Function: The state-transition and output functions are described by the expressions:
s(t+ 1) = (s(t) + x(t)) mod 5
z(t) = (s(t) + x(t)) mod 5
Exercise 7.3
State table:
x(t)
PS x = a x = b
S
0
S
0
; 01 S
1
; 11
S
1
S
2
; 11 S
3
; 00
S
2
S
3
; 11 S
3
; 11
S
3
S
3
; 00 S
4
; 01
S
4
S
4
; 01 S
0
; 00
NS, z
Solutions Manual - Introduction to Digital Design - February 3, 1999 101
Exercise 7.4 The state diagram for this exercise is shown in Figure 7.2 on page 101.
A B
C
D
E
a/0
a/0
b/1
b/1
a/0
b/1
a/0
b/1
c/1
c/1
a/0
c/0
b/1
c/1
c/0
Figure 7.2: State Transition Diagram of Exercise 7.4
Exercise 7.5 The state diagram for this exercise is shown in Figure 7.3 on page 101
a a,c a
a a
b,c c
b
c
b
b
cb
1/1 2/0 3/1
4/00/0
Figure 7.3: State diagram of Exercise 7.5
102 Solutions Manual - Introduction to Digital Design - February 3, 1999
Exercise 7.6 The state table for this exercise is:
PS Input
x = 0 x = 1
0 0 1 1
1 1 2 0
2 2 3 1
3 3 4 0
4 4 5 1
5 5 6 0
6 6 0 1
NS Output (z)
From where we obtain the following state transition and output functions:
s(t+ 1) = (s(t) + x(t)) mod 7
z(t) = (s(t) + 1) mod 2
The system is a modulo-7 counter whose output is 1 whenever the number of 1's in the input
modulo 7 is even
Exercise 7.7
There are sixteen possible states. To obtain the state diagram, we �rst obtain the state table,
by an evaluation of the expressions. To simplify the notation, we label the states with an integer
0 � j � 15 whose binary representation is the bit-vector (s
3
; s
2
; s
1
; s
0
). The state table is
Input
PS x = 0 x = 1
0 0 1 0
1 2 3 0
2 4 5 0
3 6 7 0
4 8 9 0
5 10 11 0
6 12 13 0
7 14 15 0
8 1 0 1
9 3 2 1
10 5 4 1
11 7 6 1
12 9 8 1
13 11 10 1
14 13 12 1
15 15 14 1
NS z
Observe that the state transition function is:
s(t+ 1) = (2s(t) + (
�
s(t)
8
�
+ x(t)) mod 2) mod 16
Solutions Manual - Introduction to Digital Design - February 3, 1999 103
0
1
2
3
4
5
6
7
89
10
11
12
13
14
15
00
1
0
1
0
1
0
1
0
1
01
0
1 0
1 01
0
1
0
10
1
0
1
0
1
0
1
1
Figure 7.4: State diagram for Exercise 7.7
The corresponding state diagram is shown in Figure 7.4.
Exercise 7.8
The indicated renaming results is in the following state table
Input
PS x = 0 x = 1
000 000 100 0
001 100 000 0
010 001 101 0
011 101 001 1
100 010 110 0
101 110 010 0
110 011 111 0
111 111 011 1
NS z
From the table we obtain the following expressions:
s
2
(t+ 1) = s
0
(t)� x(t)
s
i
(t+ 1) = s
i+1
(t) for 0 � i � 1
104 Solutions Manual - Introduction to Digital Design - February 3, 1999
z(t) = s
1
(t) � s
0
(t)
Exercise 7.9 The sequential systems described by each table are:
(a) Mealy machine. The output function is a function of the Present State and of the Input.
(b) Moore machine. The output function does not depend on the input.
(c) Moore machine.
Exercise 7.10 The input has four values; we represent it by the bit-vector (x
1
; x
0
) with the
following code: a = 00; b = 01; c = 10; and d = 11.
There are six states; we represent each one by the bit vector (y
2
; y
1
; y
0
) and each state S
i
correspond to a code shown in the next table (arbitrary):
State (y
2
; y
1
; y
0
)
S
0
001
S
1
010
S
2
000
S
3
011
S
4
100
S
5
101
The output z has �ve integer values. We use binary code for these integers, (z
2
; z
1
; z
0
).
The corresponding state table is
PS x = 00 x = 01 x = 10 x = 11
000 001,011 010,001 000,000 000,000
001 011,100 010,001 001,000 001,000
010 010,000 010,000 010,000 101,000
011 011,000 011,000 101,000 011,000
100 100,000 100,000 100,000 010,000
101 000,010 001,001 100,001 101,000
NS(Y
2
Y
1
Y
0
); Output(z)
To obtain switching expressions, Karnaugh maps can be used. Since there are �ve variables, it
is convenient to use 4-variable maps and include the 5th variable in the cells.
Y
2
y
2
y
2
0
y
2
0 0
y
2
y
2
0 0 0 1
0 0 1 0
�
�
	
�
	
�
�
�
	
�
�
	
�
�
	
x
0
x
1
y
0
y
1
Y
1
0
y
0
2
y
0
2
0
y
0
2
y
0
2
0 0
1 1 1 0
1 1 0 1
�
�
	
�
�
	
�
	
�
�
�
�
�
�
�
�
�
x
0
x
1
y
0
y
1
Y
0
y
0
2
0 0 0
y
0
2
y
2
1
y
0
2
1 1 1 1
0 0 1 0
�
�
	
�
�
�
�
�
�
	
�
�
	
�
�
	
�
�
	
x
0
x
1
y
0
y
1
Solutions Manual - Introduction to Digital Design - February 3, 1999 105
z
2
0 0 0 0
y
0
2
0 0 0
0 0 0 0
0 0 0 0
�
�
	
x
0
x
1
y
0
y
1
z
1
y
0
2
0 0 0
y
2
0 0 0
0 0 0 0
0 0 0 0
�
�
	
�
�
	
x
0
x
1
y
0
y
1
z
0
y
0
2
y
0
2
0 0
0 1 0
y
2
0 0 0 0
0 0 0 0
�
�
	
�
�
	
�
�
	
x
0
x
1
y
0
y
1
The expressions are:
Y
2
= x
1
x
0
y
1
y
0
0
+ x
1
x
0
0
y
0
1
y
0
+ x
0
1
y
0
1
y
0
0
y
2
+ x
0
0
y
0
1
y
0
0
y
2
+ x
1
y
0
1
y
0
y
2
Y
1
= x
0
1
y
1
+ y
1
y
0
x
0
+ y
1
y
0
0
x
0
0
+ y
0
x
0
1
y
0
2
+ y
0
1
y
0
0
x
0
y
0
2
Y
0
= x
0
1
x
0
0
y
0
1
y
0
2
+ y
0
0
y
0
y
0
2
+ x
0
1
x
0
y
0
1
y
0
y
2
+ y
1
y
0
+ y
0
x
1
x
0
+ y
1
x
1
x
0
z
2
= x
0
1
x0
0
y
0
1
y
0
y
0
2
z
1
= x
0
1
x
0
0
y
0
2
y
0
1
y
0
0
+ x
0
1
x
0
0
y
2
y
0
1
y
0
z
0
= y
0
1
y
0
x
1
x
0
y
2
+ y
0
2
y
0
1
y
0
x
0
1
+ y
0
1
y
0
x
0
1
x
0
Exercise 7.11
The time behavior of the module-p counter is given by the arithmetic expressions
z(t) = (
t
X
i=0
s(0) + x(t)) mod p
s(0) = S
IN
where S
IN
2 f0; 1; : : : ; p� 1g and x(t) 2 f0; 1g
Exercise 7.12
The number of possible input sequences starting at time t
1
= 5 and going up to t
2
= 16 would
be:
2
16�5+1
= 2
12
possible input sequences
As it's possible to have the system in two di�erent states at time t
1
, S
3
or S
1
, for the same
input sequence it's possible to get two possible sequence pairs. So, the number of sequence pairs
needed to describe the system would be:
2� 2
12
= 2
13
Calling the states by their number (e.g. S
2
is called 2), three possible sequence pairs are:
t 5 6 7 8 9 10 11 12 13 14 15 16
x(t) 1 1 0 0 1 1 1 0 1 1 0 1
s(t) 3 3 3 1 2 2 2 2 0 1 3 1
z(t) c c c a b b b b a a c a
106 Solutions Manual - Introduction to Digital Design - February 3, 1999
t 5 6 7 8 9 10 11 12 13 14 15 16
x(t) 1 1 0 1 1 0 1 1 0 0 1 0
s(t) 3 3 3 1 3 3 1 3 3 1 2 2
z(t) c c c a c c a c c a b b
t 5 6 7 8 9 10 11 12 13 14 15 16
x(t) 1 1 0 1 1 1 0 0 1 1 1 1
s(t) 1 3 3 1 3 3 3 1 2 2 2 2
z(t) a c c a c c c a b b b b
Exercise 7.13
The state diagram of Figure 7.11(a) of the textbook results in the following state table:
Input
PS 0 1
S
init
S
0
; 0 S
1
; 0
S
0
S
00
; 0 S
01
; 0
S
1
S
10
; 0 S
11
; 0
S
00
S
00
; 0 S
01
; 0
S
01
S
10
; 0 S
11
; 0
S
10
S
00
; 0 S
01
; 1
S
11
S
10
; 0 S
11
; 0
NS;Output
From the table we get
P
1
= (S
init
; S
0
; S
1
; S
00
; S
01
; S
11
)(S
10
)
To obtain P
2
, we determine the group of states P
1
to which the successors of each state belong.
group 1 group 2
(S
init
; S
0
; S
1
; S
00
; S
01
; S
11
) (S
10
)
0 1 1 2 1 2 2 1
1 1 1 1 1 1 1 1
Consequently,
P
2
= (S
init
; S
0
; S
00
)(S
1
; S
01
; S
11
)(S
10
)
To obtain P
3
, we determine the group of states of P
2
to which the successors of each state
belong.
group 1 group 2 group 3
(S
init
; S
0
; S
00
) (S
1
; S
01
; S
11
) (S
10
)
0 1 1 1 3 3 3 1
1 2 2 2 2 2 2 2
Thus, P
3
= P
2
= P = (S
init
; S
0
; S
00
)(S
1
; S
01
; S
11
)(S
10
) = (S
init
; A;B)
Using this partition we construct the state table (from the original table):
Solutions Manual - Introduction to Digital Design - February 3, 1999 107
Input
PS 0 1
S
init
S
init
; 0 A; 0
A B; 0 A; 0
B S
init
; 0 A; 1
NS;Output
The corresponding state diagram is equivalent to the one presented in Figure 7.11(b) of the
textbook, thus both diagrams represent the same system.
Exercise 7.14
The loose description has eight states as follows:
s(t) = A if x(t� 1) = a and # of a
0
s is even
s(t) = B if x(t� 1) = a and # of a
0
s is odd
s(t) = C if x(t� 2; t� 1) = ab and # of a
0
s is even
s(t) = D if x(t� 2; t� 1) = ab and # of a
0
s is odd
s(t) = E if x(t� 3; t� 1) = abc and # of a
0
s is even
s(t) = F if x(t� 3; t� 1) = abc and # of a
0
s is odd
s(t) = G if x(t� 3; t� 1) = other and # of a
0
s is even
s(t) = H if x(t� 3; t� 1) = other and # of a
0
s is odd
The corresponding state table is
Input
PS x = a x = b x = c
A B; 0 C; 0 G; 0
B A; 0 D; 0 H; 0
C B; 0 G; 0 E; 0
D A; 0 H; 0 F; 0
E B; 0 G; 0 G; 0
F A; 1 H; 0 H; 0
G B; 0 G; 0 G; 0
H A; 0 H; 0 H; 0
NS;Output
From the table we get
P
1
= (A;B;C;D;E;G;H)(F )
To obtain P
2
, we determine the class of P
1
to which each successor of the states belong.
1 2
(A;B;C;D;E;G;H) (F )
a 1 1 1 1 1 1 1 1
b 1 1 1 1 1 1 1 1
c 1 1 1 2 1 1 1 1
Consequently,
P
2
= (A;B;C;E;G;H)(D)(F )
To obtain P
3
, we repeat the process
108 Solutions Manual - Introduction to Digital Design - February 3, 1999
1 2 3
(A;B;C;E;G;H) (D) (F )
a 1 1 1 1 1 1 1 1
b 1 2 1 1 1 1 1 1
c 1 1 1 1 1 1 3 1
Thus,
P
3
= (A;C;E;G;H)(B)(D)(F )
And once more,
1 2 3
(A;C;E;G;H) (B) (D)
a 2 2 2 2 1 1 1
b 1 1 1 1 1 3 1
c 1 1 1 1 1 1 4
So
P
4
= (A;C;E;G)(H)(B)(D)(F )
Still not ready! Once more (hopefully the last)
1 2 3 4 5
(A;C;E;G) (B) (D) (F ) (H)
a 2 2 2 2 1 1 1 1
b 1 1 1 1 3 5 5 5
c 1 1 1 1 5 4 5 5
So, �nally!
P = P
5
= P
4
= (A;C;E;G)(B)(D)(F )(H)
and the reduced table is
Input
PS x = a x = b x = c
A B; 0 A; 0 A; 0
B A; 0 D; 0 H; 0
D A; 0 H; 0 F; 0
F A; 1 A; 0 A; 0
H A; 0 H; 0 H; 0
NS;Output
Exercise 7.15
From the state table we get
P
1
= (a; b; c; e)(d; h)(f)(g)
To obtain P
2
, we determine the class of P
1
to which the successors of the states belong.
1 2 3 4
(a; b; c; e) (d; h) (f) (g)
0 3 2 3 2 4 4 3 4
1 1 1 1 1 1 1 1 2
Solutions Manual - Introduction to Digital Design - February 3, 1999 109
Thus,
P
2
= (a; c)(b; e)(d; h)(f)(g)
To obtain P
3
, we determine the group of states of P
2
to which the successors of the state belong.
1 2 3 4 5
(a; c) (b; e) (d; h) (f) (g)
0 4 4 3 3 5 5 4 5
1 2 2 1 1 1 1 2 3
Therefore, P = P
3
= P
2
= (a; c)(b; e)(d; h)(f)(g) and the reduced table is
Input
PS x = 0 x = 1
a f; 0 b; 0
b d; 0 a; 0
d g; 1 a; 0
f f; 1 b; 1
g g; 0 d; 1
NS;Output
Exercise 7.16
Based on the outputs for each state we get the �rst partition P
1
as:
P
1
= (A;D;E)(B;F;G)(C;H)
Let's call (A,D,E) as group 1, (B,F,G) as group 2 and (C,H) as group 3.
We can construct a table representing the next group for each state transition:
group 1 group 2 group 3
A D E B F G C H
0 2 2 2 3 3 3 3 3
1 3 3 3 1 1 1 1 1
From the table we can see that the columns for each group of states are the same, and so, the
states in each group are also 2-equivalent. P
2
= P
1
. Renaming the states in group 1 as �, the
states in group 2 as � and in group 3 as 
, we can represent the reduced sequential system as:
PS Input
x = 0 x = 1
� �; 0 
; 0
� 
; 1 �; 1
 
; 0 �; 1
Exercise 7.17
Based on the outputs for each state we get the �rst partition
P
1
= (A;C;G;H)(B;D;E)(F )
To obtain P
2
, we determine the class of P
1
to which the successors of the states belong.
110 Solutions Manual - Introduction to Digital Design - February 3, 1999
group 1 group 2 group 3
A C G H B D E F
a 2 2 2 2 1 1 1
b 1 1 1 1 3 3 3
c 2 2 2 2 2 2 2
d 2 3 3 3 2 2 2
Partition P
2
is
group 1 group 2 group 3 group 4
A C G H B D E F
a 3 3 3 2 2 2
b 1 1 2 4 4 4
c 3 3 3 3 3 3
d 4 4 4 3 3 3
Partition P
3
is
group 1 group 2 group 3 group 4 group 5
A C G H B D E F
a 4 4 2 2 2
b 1 1 5 5 5
c 4 4 4 4 4
d 5 5 4 4 4
STOP.
The equivalent states are: fAg, fB,D,Eg, fC,Gg, fFg, fHg
Minimal state transition table:
PS x = a x = b x = c x = d
A B=1 C=0 B=1 B=1
B C=0 F=1 B=1 B=0
C B=1 A=0 B=1 F=1
F C=1 F=1 B=0 H=0
H B=1 C=0 B=1 F=1
NS=output
Exercise 7.18 Based on the outputs for each statewe get the �rst partition
P
1
= (N;O;Q;R;X;Z)(P;U; V; Y )(S; T;W )
To obtain P
2
, we determine the class of P
1
to which the successors of the states belong.
group 1 group 2 group 3
N O Q R X Z P U V Y S T W
a 3 3 3 3 3 3 2 2 2 2 1 1 1
b 1 2 2 2 1 1 1 1 1 1 2 2 2
Partition P
2
is
Solutions Manual - Introduction to Digital Design - February 3, 1999 111
group 1 group 2 group 3 group 4
N X Z O Q R P U V Y S T W
a 4 4 4 4 4 4 3 3 3 3 1 1 1
b 1 1 1 3 3 3 2 2 1 1 3 3 3
Partition P
3
is
group 1 group 2 group 3 group 4 group 5
N X Z O Q R P U V Y S T W
a 5 5 5 5 5 5 4 4 3 3 1 1 1
b 1 1 1 4 4 4 2 2 1 1 4 4 3
Partition P
4
is
group 1 group 2 group 3 group 4 group 5 group 6
N X Z O Q R P U V Y S T W
a 5 6 5 5 6 6 4 4 3 3 1 1
b 1 1 1 4 4 4 2 2 1 1 4 4
Partition P
5
is
group 1 group 2 group 3 group 4 group 5 group 6 group 7 group 8
N Z X O Q R P U V Y S T W
a 7 7 8 8 6 6 5 5 1 1
b 1 1 6 6 4 4 1 1 6 6
STOP!
Equivalent states: fN,Zg, fOg, fP,Ug, fQ,Rg, fS,Tg, fV,Yg, fWg, fXg
Minimal state transition table:
PS input
x = a x = a
0
N S=f N=e
O S=f V=e
P V=e Q=f
Q W=f V=e
S N=e V=e
V P=f N=f
W X=e P=e
X W=f N=e
NS=output
Exercise 7.19
Input: x(t) 2 fa; b; c; dg
Output: z(t) 2 f0; 1g
State: Since the pattern to be recognized has four symbols, using the vector-state approach, we
represent the state as the vector
s = (s
2
; s
1
; s
0
)
and the states are s(t) 2 f0; 1; 2; :::; 7g.
112 Solutions Manual - Introduction to Digital Design - February 3, 1999
Function: The corresponding state transition and output functions are:
s
i
(t+ 1) = s
i�1
(t) 1 � i � 2
s
0
(t+ 1) = x(t)
z(t) =
(
1 if (s(t); x(t)) = abca
0 otherwise
For the minimum-number-of-states approach, we de�ne a state with the following four values:
s(t) = A if x(t� 1) = a
s(t) = B if x(t� 2; t� 1) = ab
s(t) = C if x(t� 3; t� 1) = abc
s(t) = D if none of the above (Initial)
The state description is given by the following table:
Input
PS a b c d
A A; 0 B; 0 D; 0 D; 0
B A; 0 D:0 C; 0 D; 0
C A; 1 D; 0 D; 0 D; 0
D A; 0 D; 0 D; 0 D; 0
NS; z
The output sequence corresponding to the given input sequence is
x(t) a a b c a b c a d a a a b c a
s(t) D A A B C A B C A D A A A B C A
z(t) 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1
Exercise 7.20 It is not possible to have a sequential system with m � 1 states recognizing a
sequence of length m. As a proof, consider a pattern of length 2, let us say ab. The state diagram
for this sequential system is shown in Figure 7.5. We can easily see from the diagram that the states
are not equivalent, since their outputs are di�erent. Thus, it is not possible to have a reduced state
machine with only ONE state to recognize the pattern with length 2.
We now consider the generation of a m-state machine to recognize a sequence of length m.
Let the pattern to be recognized be p
1
p
2
: : : p
m
. The state description of the pattern recognizer is
obtained by having m states labeled S
0
to S
m�1
as follows:
S
0
is the initial state. Other states are s(t) = S
i
whenever the sequence x(t�i; t�1) = p
1
p
2
: : : p
i
,
i > 0 (that is already i symbols of the pattern have been recognized).
The state-transition function is
s(t+ 1) =
8
>
>
>
<
>
>
>
:
S
i+1
if s(t) = S
i
and x(t) = p
i+1
S
j
if s(t) = S
i
and p
i�j+2
p
i�j+3
: : : p
i
x(t) = p
1
p
2
� � � p
j
; j � 2
S
1
if x(t) = p
1
S
0
otherwise
Solutions Manual - Introduction to Digital Design - February 3, 1999 113
S0 S1
a’/0
a/0
b/1,a’/0,b’/0
a/0
Figure 7.5: Exercise 7.20
and the output function
z =
(
1 if s(t) = S
m�1
and x(t) = p
m
0 otherwise
Exercise 7.21
The state diagram that describes the system is presented in Figure 7.6 page 113, using the
minimum state approach. The vector state approach is not possible to be used since the system is
not a �nite memory system.
a ab abc
a/1 b/1 c/1
c,d/1 b,d/1
b,c,d/1
b,c,d/1 a/1a/1
a/0
b,c,d/0 a/0
a ab abc
a/0
c,d/01 b,d/01
b,c,d/0
c/0b/0
a/0
Even
Odd
a/1
Figure 7.6: State Diagram for Exercise 7.21
114 Solutions Manual - Introduction to Digital Design - February 3, 1999
Exercise 7.22
The input set is I = f0; 1; 2; 3; 4; 5; 6; 7; 8; 9g and the output set 0 = f0; 1; 2; 3; 4g. The state
is formed of two components: s
1
to detect the pattern 358, and s
2
to count mod 5 the number of
instances. For the pattern recognizer, we need three states as follows:
s
1
(t) = A if x(t� 1) = 3
s
1
(t) = B if x(t� 2; t� 1) = 35
s
1
(t) = C if none of above
s
1
(0) = C
The state description of this component is
s
1
(t+ 1) =
8
>
<
>
:
A if x(t) = 3
B if s
1
(t) = A and x(t) = 5
C otherwise
The second component is a modulo 5 counter. Consequently, the state has �ve values which
we label with the integers 0; 1; 2; 3 and 4 to be able to write the state transition as the arithmetic
expression:
s
2
(t+ 1) =
(
(s
2
(t) + 1) mod 5 if s
1
(t) = B and x(t) = 8
s
2
(t) otherwise
s
2
(0) = 0
Finally, the output function is z(t) = s
2
(t).
Exercise 7.23
Following the hint given in the exercise, the sequential system is decomposed into two. System
A recognizes the pattern 0110, and system B recognizes the pattern 1001, as shown in Figure 7.7.
The output z(t) is de�ned as a function of the system A states (S
A
(t)) and system B states (S
B
(t))
as follows:
S
A
(t) S
B
(t) z(t)
f0; 1; 2; 3g { 0
4 f0; 1; 2; 3g 1
4 4 2
The timing behavior for the given input sequence, considering s(t) = (S
A
(t); S
B
(t)) is:
t 0 1 2 3 4 5 6 7
x(t) 0 0 1 0 1 1 1 0
s(t) (0,0) (1,0) (2,1) (1,2) (2,1) (3,1) (0,1) (1,2)
z(t) 0 0 0 0 0 0 0 0
t 8 9 10 11 12 13 14 15
x(t) 1 1 0 0 1 0 1 0
s(t) (2,1) (3,1) (4,2) (4,3) (4,4) (4,4) (4,4) (4,4)
z(t) 0 0 1 1 2 2 2 2
Solutions Manual - Introduction to Digital Design - February 3, 1999 115
0 1 2
34
1 0
10
0 11
0
0 1 2
34
0 1
01
1 00
1
System A System B
Figure 7.7: State Transition Diagram of Exercise 7.23
Exercise 7.24
Since two di�erent patterns are generated, the system consists of two independent pattern
generators, let's call these systems A and B. The corresponding state diagram is given in Figure 7.8.
The states S
A
i belongs to system A and states S
B
i belongs to system B.
S 0 S 1 S 2 S 3 S 4 S 5 S 6-/G -/O -/blank -/U -/C -/L
-/A
S 1 S 2-/U1/R
-/N
0/blank
B
A A A A A A A
B B
S 0
Figure 7.8: State diagram of Exercise 7.24
Exercise 7.25
To make the design simple and tractable, we make the following assumptions:
� Selection of stamps to buy is the �rst step
� If amount of accumulated coins is at least 15c greater than the face value of the selected
stamp, return all coins
Then the inputs and outputs are as follows (ref. Figure 7.9):
Inputs:
Reset : 2 fT; Fg
116 Solutions Manual - Introduction to Digital Design - February 3, 1999
CoinType : 2 fN;D;Qg
StampType : 2 fS1(20c); S2(40c); S3(50c)g
ReturnCoinRequest : 2 fT; Fg
Outputs:
RS1 � Release stamp 1 (20c)
RS2 � Release stamp 2 (40c)
RS3 � Release stamp 3 (50c)
RC � Return Coin
RN � Return Nickel
RD � Return Dime
All outputs take values from the set fT, Fg. The state diagram is shown in Figure 7.10.
Reset RS1
RS2
RS3
Controller RC
RN
RD
Stamp Type
Coin Type
Return Coin RequestFigure 7.9: Inputs & Outputs of Vending Machine Controller
Solutions Manual - Introduction to Digital Design - February 3, 1999 117
S3
Select
S3,10cS3,5c
N/
S3,30cS3,25cS3,15c S3,35cS3,20c
N/ N/ N/ N/
D/ D/ D/
N/N/
S3,40c S3,45c
N/ N/
D/ D/ D/ D/D/
Q/
Q/ Q/
Q/
Q / RS3
Q / RS3, RN
Q / RS3, RD
D / RS3; Q / RS3, RN, RD
N / RS3; D / RS3, RN; Q / RC
S3/
S2
Select Stamp 1
Select Stamp 2
Select Stamp 3
Note: We did not draw the transitions corresponding to inputs RESET and Return Coin Request.
 Basically, for every state, its next state with the above inputs should be the same - go
 back to State Wait. In the mean time, RC is true to return all coins deposited so far.
Q/RS2
Q / RS2, RN
Q/RS2, RD
N / RS2; D / RS2, RN; Q / RC
Select
S1 S1,10cS1,5cS1/
N/ N/ N/
Q / RS1, RN Q / RS1, RD
S1,15c
D / RS1; Q / RS1,RN,RD
D/
D/
N / RS1; D / RS1,RN; Q / RC
Wait
S2 S2,10c
N/ N/ N/
D/
S2,30cSelect S2,5c S2,25cS2,15c S2,35cS2,20c
N/ N/ N/ N/
Q/
Q/
D/
Q/
D/ D/ D/
D/
D / RS2; Q / RS2, RN, RD
Q/
Figure 7.10: State Diagram of Exercise 7.25