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

Prévia do material em texto

119
Chapter 8
Exercise 8.1: A minimum clock width of 5 ns and a latch delay of 2 ns are considered in this
problem.
(a) The minimum delay of the combinational network (t
p
) considered in this problem is obtained
by the following equation
t
p
+ 2ns � 5ns! t
p
� 3ns
(b) If the delay of the combinational network can decrease by 30% and the latch delay can
decrease by 10%, the maximum clock pulse width (T
max
) is calculated by the following equation:
0:7t
p
+ 0:9� 2ns = 0:7� 3 + 1:8 = T
max
! T
max
= 3:9ns
Exercise 8.2:
Using the notation given on Figure 8.15 of the textbook we obtain the following network pa-
rameters:
Combinational Networks' delays:
d1
x
= d1
y
= 4 � t
p
(gate) = 2ns
d2 = 1 � t
p
(gate) = 0:5ns
Network set-up time:
t
x
su
(net) = t
y
su
(net) = t
su
(cell) + d1
x
= 1 + 2 = 3ns
Network hold time:
t
h
(net) = t
h
(cell) = 0:5ns
Network propagation delay:
t
p
(net) = t
p
(cell) + d2 = 3 + 0:5 = 3:5ns
Minimal period:
T
min
= max[(t
in
+ t
x
su
(net)); (t
y
su
(net)+ t
p
(cell)); t
p
(net+ t
out
)] = max[2+3; 3+3; 3:5+2:5] = 6:0ns
Maximal frequency:
f
max
=
1
T
min
=
1
6:0 � 10
�9
� 167MHz
Exercise 8.3
(a) There are no races because of the nonoverlapping nature of the two clocks. This assures
that in each clock cycle only one state change occurs.
(b) The number of states depends on the mode of operation of the network. We consider two
modes.
120 Solutions Manual - Introduction to Digital Design - February 22, 1999
i) The clock period of the system corresponds to one of the phases (say phase 1). In this case,
the gated latch loaded during the phase two clock acts just as a temporary bu�er to prevent
races. The state register corresponds to the register loaded during phase 1. Consequently,
the number of states is 2
n
. The division of the combinational network into two can, in some
cases, make sense because of implementation restrictions. For example, if the combinational
network is implemented using pass transistors, there is a limitation on the number of them
that can be connected in series; in such a case the division in two networks might help.
ii) The clock period is the time between both clocks (phase 1 and phase 2). This results in a
system that has a smaller period than that in (i) (and, therefore, in a faster system). In this
case each register stores part of the state and the number of potential states is 2
2n
, but these
states cannot be utilized in general. The state can be described by two components s
1
(stored
in register 1) and s
2
(stored in register 2). Each component changes in alternate clock cycles.
The output is a combination of two components z
1
and z
2
expressed as:
z
1
(t) = G
1
(s
1
(t); x
1
(t))
z
2
(t) = G
2
(s
2
(t); x
2
(t))
(c) Using the �rst model, the implementation of the system of Exercise 8.4 (Figure 8.40 of
the textbook) is straightforward if we only replace the D-type cells for two gated latches in a
master/slave con�guration, as shown on page 203 of the textbook. Doing this modi�cation, the
new design will behave the same way as the one shown in Exercise 8.4, with a slower clock. One
way to improve this design would be to split the combinational network, reducing the propagation
delay between latches, as shown in Figure 8.1. Observe that one more latch is used in this case.
phase 2
Y1 y1
Y0 y0
x0
x0’
x0’
x1
phase 1 z
Figure 8.1: Redesign of system in Exercise 8.4 using latches - Exercise 8.3
Solutions Manual - Introduction to Digital Design - February 22, 1999 121
Exercise 8.4
The transition and output functions are described by the following expressions:
Y
1
= x
0
0
x
1
+ x
0
y
1
Y
0
= y
0
x
0
0
+ x
0
y
1
z = y
0
PS Input (x
1
x
0
)
y
1
y
0
00 01 10 11
00 00 00 10 00 0
01 01 00 11 00 1
10 00 11 10 11 0
11 01 11 11 11 1
NS(Y
1
Y
0
) Output (z)
The corresponding state table is (for state assignments A = 00; B = 01; C = 10;D = 11 and
input coding a = 00; b = 01; c = 10; d = 11)
PS Inputs
x = a x = b x = c x = d
A A A C A 0
B B A D A 1
C A D C D 0
D B D D D 1
NS Output (z)
The diagram in Figure 8.2 shows the state transitions of this system. The following patterns
are recognized by the system (assuming that A is the initial state): cb; cbb; cbc; cd; cdc.
a,b,d c
b,d
b,c,d
a
b,d
c
a
a
c
A/0 C/0
B/1 D/1
Figure 8.2: State digram for network on Exercise 8.4
122 Solutions Manual - Introduction to Digital Design - February 22, 1999
Exercise 8.5
The state diagram of the pattern recognizer for the sequence 0101011 is shown in Figure 8.3
and has seven states. Each state was labeled with the sequence that it \recognizes". We encode
these states using three state variables (y
2
; y
1
; y
0
) so that the state assignment of state S
i
is the
radix-2 representation of i. The correspondence between the state assignment and sequence that
it detects is shown in the next table.
start 0 01 010
0101
01010010101
0/0 1/0 0/0
1/0
0/0
1/0
1/1
1/0
1/0
0/0 0/0
1/0
0/0
0/0
Figure 8.3: State diagram for system in Exercise 8.5
State Sequence
S
0
start
S
1
0
S
2
01
S
3
010
S
4
0101
S
5
01010
S
6
010101
The state and transition table is:
PS Input
y
2
y
1
y
0
x = 0 x = 1
S
0
000 001,0 000,0
S
1
001 001,0 010,0
S
2
010 011,0 000,0
S
3
011 001,0 100,0
S
4
100 101,0 000,0
S
5
101 001,0 110,0
S
6
110 101,0 000,1
Y
2
Y
1
Y
0
; z
Solutions Manual - Introduction to Digital Design - February 22, 1999 123
The switching expressions for the next state and output are:
Y
2
= y
2
y
0
0
x
0
+ y
2
y
0
x+ y
1
y
0
x
Y
1
= y
0
1
y
0
x+ y
0
2
y
1
y
0
0
x
0
Y
0
= x
0
z = y
2
y
1
x
These expressions are implemented by AND-OR networks and the state is stored in a 3-bit
register. The corresponding sequential network is shown in Figure 8.4.
x’
y0’
y2
x
y2
y0
x
y1
y0
x
y1’
y0 CK
x’
y2
y1
y0
Y2
Y1
Y0
x
z
x’
y2’
y1
y0’
Figure 8.4: Network for Exercise 8.5
Exercise 8.6:
The pattern generator for the sequence abcaba is described by the following transition table:
PS NS/z
A B/a
B C/b
C D/c
D E/a
E F/b
F A/a
Let us de�ne the following encoding:
y
2
y
1
y
0
State
000 A
001 B
010 C
011 D
100 E
101 F
z
1
z
0
00 a
01 b
10 c
124 Solutions Manual - Introduction to Digital Design - February 22, 1999
From the state table and the previous encoding we get the following table and K-maps:
PS NS/z
1
z
0
000 001/00
001 010/01
010 011/10
011 100/00
100 101/01
101 000/00
101 - - -/- -
101 - - -/- -
Y
2
:
0 0 1 0
1 0
- -
y
0
y
1
y
2
�
	
�
�
�
	
Y
1
:
0 1 0 1
0 0
- -
y
0
y
1
y
2
�
�
	
�
�
	
Y
0
:
1 0 0 1
1 0
- -
y
0
y
1
y
2
�
�
�
�
z
1
:
0 0 0 1
0 0
- -
y
0
y
1
y
2
�
�
	
z
0
:
0 1 0 0
1 0
- -
y
0
y
1
y
2�
�
	
�
	
�
The expressions we get from the K-maps are:
Y
2
= y
1
y
0
+ y
2
y
0
0
Y
1
= y
0
2
y
0
1
y
0
+ y
1
y
0
0
Y
0
= y
0
0
z
1
= y
1
y
0
0
z
0
= y
0
2
y
0
1
y
0
+ y
2
y
0
0
The network that implements a canonical version of this sequential network is presented in
Figure 8.5 on page 125.
Exercise 8.7
The state diagram for this system is presented in Figure 8.6. State S
1
represents a 1 followed
by a EVEN block of zeros, and state S
5
indicates that the system received the required sequence.
The corresponding state table is:
Input
PS x = 0 x = 1
S
0
S
0
S
1
0
S
1
S
2
S
3
0
S
2
S
1
S
1
0
S
3
S
2
S
4
0
S
4
S
5
S
4
0
S
5
S
4
S
1
1
NS output(z)
Solutions Manual - Introduction to Digital Design - February 22, 1999 125
Combinational
Network
Comb.
Network
cells
z1
z0
y2
y1
y0
Y2
Y1
Y0
CK
y2’
y2
y1’
y1
y0’
y0
y1
y0
y2
y0’
y2’
y1’
y0
y1
y0’ z0
z1
Figure 8.5: Pattern generator of Exercise 8.6
We use the state code i (in binary) for the state S
i
. The PS is represented by the 3-bit vector
(y
2
y
1
y
0
) and the NS by the vector (Y
2
Y
1
Y
0
). The output switching expression is:
z = y
2
y
0
The K-maps for the next state bits are shown next.
S0/0 S1/0 S3/0 S4/0 S5/1
S2/0
0
1
0,1 0
1
1
1
0
1
0
0
S1 - block of zeros of EVEN length
S5 - block of zeros of ODD length
(after correct prefix) 
Figure 8.6: State diagram for Exercise 8.7
126 Solutions Manual - Introduction to Digital Design - February 22, 1999
Y
2
:
0 0 0 0
1 1
- -
1 0
- -
0 0 1 0
y0
y1
y2
x
�
�
�
�
�
�
�
�
�
�
Y
1
:
0 1 1 0
0 0
- -
0 0
- -
0 1 0 0
y0
y1
y2
x
��
�
�
�
�
Y
0
:
0 0 0 1
1 0
- -
0 1
- -
1 1 0 1
y0
y1
y2
x
�
�
�
�
�
�
�
�
�
�
�
�
The switching expression for Y
2
,Y
1
, and Y
0
are:
Y
2
= y
2
y
0
0
+ x
0
y
2
+ xy
1
y
0
Y
1
= y
0
2
y
0
1
y
0
+ x
0
y
0
2
y
0
Y
0
= xy
0
2
y
0
1
+ xy
0
1
y
0
+ y
1
y
0
0
+ x
0
y
2
y
0
0
The corresponding sequential network is shown in Figure 8.7.
CK
y2
y1
y0
z
y2
y0’
x’
y2
x
y1
y0
y2’
y1’
y0
x’
y2’
y0
x
y2’
y1’
x
y1’
y0
y1
y0’
x’
y2
y0’
Y2
Y1
Y0 y2
y1
y2’
y1’
y0’
x x’
Figure 8.7: Network for Exercise 8.7
Solutions Manual - Introduction to Digital Design - February 22, 1999 127
Exercise 8.8
We need a 3-bit vector to represent the six states and a 2-bit vector to represent the output.
Let us de�ne the following encoding:
y
2
y
1
y
0
State
000 A
001 B
010 C
011 D
100 E
101 F
z
1
z
0
00 a
01 b
10 c
From the state table and the encoding we get the following K-maps.
Y
2
:
0 0 1 0
1 0
- -
0 1
- -
1 0 0 0
y
0
y
1
y
2
x
�
�
�
�
�
�
�
�
�
�
�
�
Y
1
:
0 1 0 1
0 0
- -
1 0
- -
0 0 1 0
y
0
y
1
y
2
x
�
�
�
�
�
�
�
�
�
�
�
�
Y
0
:
1 0 0 1
1 0
- -
1 0
- -
1 0 0 1
y
0
y
1
y
2
x
�
�
�
�
z
1
:
0 0 0 0
0 1
- -
0 1
- -
0 1 1 0
y
0
y
1
y
2
x
�
�
�
�
�
�
�
�
z
0
:
0 0 1 0
1 0
- -
1 0
- -
1 0 0 1
y
0
y
1
y
2
x
�
�
�
�
�
�
�
�
�
�
�
The corresponding switching expressions are
Y
0
= y
0
0
Y
1
= x
0
y
0
2
y
0
1
y
0
+ x
0
y
1
y
0
0
+ xy
2
y
0
0
+ xy
1
y
0
Y
2
= x
0
y
2
y
0
0
+ x
0
y
1
y
0
+ xy
2
y
0
+ xy
0
2
y
0
1
y
0
0
z
1
= y
2
y
0
+ xy
0
z
0
= x
0
y
1
y
0
+ y
2
y
0
0
+ xy
0
0
The sequential network is shown in Figure 8.8 on page 128.
Exercise 8.9:
Direct application of K-maps is not possible for this problem. To design this network it is
important to decompose it into smaller parts, as shown in Figure 8.9. The NOTBCD module
detects when the input code, or the stored minimum value is not a valid BCD code. The input
vector is represented by the vector x = (x
3
; x
2
; x
1
; x
0
), and the state vector is y = (y
3
; y
2
; y
1
; y
0
).
Input x (y) is not a valid BCD code if x > 9 (y > 9). This condition is represented by the
expression x is not BCD = x
3
x
2
+ x
3
x
1
(y is not BCD = y
3
y
2
+ y
3
y
1
). The NOTBCD module is
implemented by an expression that combines both cases:
NOTBCD = x is not BCD + y is not BCD = x
3
x
2
+ x
3
x
1
+ y
3
y
2
+ y
3
y
1
128 Solutions Manual - Introduction to Digital Design - February 22, 1999
x’
y1
y0
x’
y2
y0’
x
y2
y0
x
y2’
y1’
y0’
x’
y2’
y1’
y0
x’
y1
y0’
x
y2
y0’
x
y1
y0
y2
y0
x
y0
x’
y1
y0
y2
y0’
x
y0’
z1
z0
Y2
Y1
Y0
y0’
y2
y2’
y1
y1’
y0
y0’
CK
Figure 8.8: Sequential network for Exercise 8.8
The MIN module is speci�ed as:
Inputs: x; y 2 f0; 1; 2; � � � ; 15g
Output: z 2 f0; 1; 2; � � � ; 15g
Function:
z =
(
x if x < y
y otherwise
The MINmodule may be implemented as an iterative array, comparing bits frommost-signi�cant
to least-signi�cant. Each bit slice has two \data" inputs x
i
and y
i
and two \carry" inputs e
i
(equal)
and s
i
(x
j
< y
j
for some j < i), and the outputs: m
i
, e
i�1
, and s
i�1
. The folllowing expressions
are used for each output:
e
i�1
= e
i
(x
i
� y
i
)
0
s
i�1
= s
i
+ (x
0
i
y
i
)e
i
m
i
= s
i�1
x
i
+ s
0
i�1
y
i
Solutions Manual - Introduction to Digital Design - February 22, 1999 129
MIN
CLK
NOTBCD
OR Mem.Cells
x
yY
Figure 8.9: Network for Exercise 8.9
e
4
= 1
s
4
= 0
The �nal gate network for the system is shown in Figure 8.10.
Exercise 8.10:
To implement a sequential network that performs a Binary-to-Gray code conversion we use the
given equation:
g
i
= b
i
� b
i+1
, i = 1; ::::; n � 1
g
n
= b
n
Thus, the conversion is done from left to right, storing a new binary-code bit in each clock cycle.
Initially the internal variable is 0 (b
i+1
= 0).
The sequential network is shown in Figure 8.11.
Exercise 8.11
To perform subtraction it is necessary to have a representation of negative integers, since the
result can be negative. Several of these representations are given in Chapter 10. Here we simplify
the problem by assuming that the result is positive.
Given two n-bit integers represented in the binary number system by x = (x
n�1
; : : : ; x
0
) and
y = (y
n�1
; : : : ; y
0
), and the result represented by (s
n�1
; : : : ;s
0
), the function to be performed
serially in each bit position, for addition and subtraction, is described by the following tables:
Addition
x
i
y
i
c
i
c
i+1
s
i
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0
1 0 0 0 1
1 0 1 1 0
1 1 0 1 0
1 1 1 1 1
Subtraction
x
i
y
i
b
i
b
i+1
s
i
0 0 0 0 0
0 0 1 1 1
0 1 0 1 1
0 1 1 1 0
1 0 0 0 1
1 0 1 0 0
1 1 0 0 0
1 1 1 1 1
130 Solutions Manual - Introduction to Digital Design - February 22, 1999
e i-1
m
x
y
ie
MIN slice
MIN slice
MIN slice
x3
y3
x2
y2
x1
y1
1 0
MIN slice
x0
y0
y3
y2
y3
y1
NOTBCD
CLK
y3
y2
y1
y0
x3
x2
x3
x1
s i
s i-1
Figure 8.10: Minimum detector for Exercise 8.9
where c
i
is the carry-in bit at position i, and b
i
is the borrow-in bit.
Let the variable k indicate the operation to be performed as follows:
k =
(
1 for x+ y
0 for x� y
Since we want to combine both operations in the same module, let us make c = b. A switching
expression for the result s
i
is:
s
i
= x
i
� x
i
� c
i
for i = 1; : : : ; n� 1
s
n
= c
n
CLK
g i
BINARY-to-GRAY
b i
bi+1
D Q
Figure 8.11: Binary-to-Gray converter
Solutions Manual - Introduction to Digital Design - February 22, 1999 131
providing that a
n
= b
n
= 0.
A switching expression for c
i+1
is
c
i+1
= c
i
y
i
+ (k � x
i
)
0
(c
i
+ y
i
)
The initial condition c
0
= 0 is set with INIT = 1.
The sequential network is given in Figure 8.12.
INIT
bi
k
ai si
CK
c
i+1
ci
D Q
Figure 8.12: Adder/subtractor, Exercise 8.11
Another implementation of this sequential adder/subtractor is possible using complementation
and addition. This approach will become clear after the discussion in Chapter 10.
Exercise 8.12
The state diagram for this sequential network is presented in Figure 8.13, for the case of receiving
least signi�cant bit and most signi�cant bit �rst. In each transition we use a pair of bits representing
bits from input A (a(t)) and B (b(t)), respectively. The system output is the same as the state
coding used.
For both implementation we need three states, coded as:
State (y
1
; y
0
)
EQUAL (A = B) 00
GREATER (A > B) 01
SMALLER (A < B) 10
(a) Least-signi�cant bit �rst:
In this case the transition table is:
PS Inputs (a(t),b(t))
00 01 10 11
00 00 10 01 00
01 01 10 01 01
10 10 10 01 10
NS (Y
1
; Y
0
)
132 Solutions Manual - Introduction to Digital Design - February 22, 1999
SMALLER
GREATEREQUAL
00,11 01
10
00,11,10
01
10
00,11,01
LEAST SIGNIFICANT BIT FIRST
SMALLER
GREATEREQUAL
00,11 01
10
MOST SIGNIFICANT BIT FIRST
Figure 8.13: Serial Binary Magnitude Comparator, Exercise 8.12
We can see from the table that:
Y
1
= y
1
(a(t)
0
� b(t)) + a(t)
0
b(t)
Y
0
= y
0
(a(t)
0
� b(t)) + a(t)b(t)
0
The network is presented in Figure 8.14.
(b) Most-signi�cant bit �rst: In this case the transition table is:
PS Inputs (a(t),b(t))
00 01 10 11
00 00 10 01 00
01 01 01 01 01
10 10 10 10 10
NS (Y
1
; Y
0
)
The new expressions are:
Y
1
= y
1
+ y
0
0
a(t)
0
b(t)
Y
0
= y
0
+ y
0
1
a(t)b(t)
0
Solutions Manual - Introduction to Digital Design - February 22, 1999 133
y1
y0
a(t)
b(t)
Y1
Y0
CK
y1
y0
Mem.
Cell
Figure 8.14: Serial Binary Magnitude Comparator, Exercise 8.12 (a)
These expressions are easily implemented using gates.
Exercise 8.13
In order to simplify the design of this system, we decompose the state (S(t)) into two compo-
nents: the number of digits being inserted (S
1
(t)), and the correctness of the input (S
2
(t)). The
�rst component is implemented by a modulo-4 counter with states S
1
(t) 2 f0; 1; 2; 3g, and the
second component by a two-state machine with states S
2
(t) 2 fY;Ng. The output is generated as
a function os these states.
The initial state is S(t) = (0; Y ), and the combination (0; N) never happens. The state transi-
tion table for the two-component system is:
Inputs
S
1
(t)S
2
(t) x = 0 x = 5 x = 6 others
0Y 1Y 1N 1N 1N
1Y 2N 2Y 2N 2N
1N 2N 2N 2N 2N
2Y 3N 3N 3Y 3N
2N 3N 3N 3N 3N
3- 0Y 0Y 0Y 0Y
S
1
(t+ 1)S
2
(t+ 1)
The state diagram for the lock is shown in Figure 8.15. We consider that the counter state
S
1
(t) is represented by the vector (c
1
; c
0
), and S
2
(t) assumes the values 1 for Y and 0 for N . The
expression for the next state of the two-state component and the outputs are:
S
2
(t+ 1) = d
0
c
0
1
c
0
0
S
2
(t) + d
5
c
0
1
c
0
S
2
(t) + d
6
c
1
c
0
0
S
2
(t) + c
1
c
0
where d
i
= 1 when x = i. Thus,
S
2
(t+ 1) = S
2
(t)(x
0
3
x
0
2
x
0
1
x
0
0
c
0
1
c
0
0
+ x
0
3
x
2
x
0
1
x
0
c
0
1
c
0
+ x
0
3
x
2
x
1
x
0
0
c
1
c
0
0
) + c
1
c
0
z
2
(t) = c
1
c
0
(S
2
(t)(x
3
x
0
0
)
0
+ S
2
(t)
0
) = c
1
c
0
(x
0
3
+ x
0
+ S
2
(t)
0
)
z
1
(t) = c
1
c
0
S
2
(t)x
3
x
0
0
134 Solutions Manual - Introduction to Digital Design - February 22, 1999
0Y 1Y 2Y 3Y
1N 2N 3N
0/00 5/00 6/00
0’/00 5’/00 6’/00
-/00-/00
-/10
8/01
8’/10
Figure 8.15: State diagram for lock { Exercise 8.13
x3
x2
x1
x0
c1’
c0’
c1’
c0
c1
c0’
s2(t)
s2(t+1)
Modulo-4
Counter
CLK
CN
T
1
0
1
c1
c0
c1’
c0’
c1
c0
z2
z1d8
d0
d5
d6
x3
x0
D Q
CLK Q’ s2(t)’
Figure 8.16: Network for lock in Exercise 8.13
The gate network that implements the locker is shown in Figure 8.16.
Exercise 8.14 We apply the same concepts presented for the D-latch network on page 200 of
the textbook and the master/slave con�guration shown in Figure 8.11 of the textbook. The general
network con�guration is shown in Figure 8.17. The slave cell is a D-type latch, as discussed in the
book. A combinational network must be designed to activate the set/reset inputs of an SR latch.
C represents the clock input.
The table for the combinational network is shown next:
Solutions Manual - Introduction to Digital Design - February 22, 1999 135
SR cell
SR
Cell Q
Q’
Comb.
Circ.
J
K
C
A
S
R
Figure 8.17: Gate implementation of an edge-triggered JK 
ip-
op
C J K Q S R
0 - - - 0 0
1 0 0 0 0 -
1 0 0 1 - 0
1 0 1 0 0 -
1 0 1 1 0 1
1 1 0 0 1 0
1 1 0 1 - 0
1 1 1 0 1 0
1 1 1 1 0 1
It is easy to see that
S = Q
0
CJ
R = QCK
The combinational network is composed of two AND gates only.
The timing diagram for the network is shown in Figure 8.18. The timing diagram of the internal
signal A, the output of the master module, is also shown.
J
K
C
Q
A
Figure 8.18: Timing diagram for Exercise 8.14
Exercise 8.15 The solution of this exercise is similar to Exercise 8.14, making J = K = T .
136 Solutions Manual - Introduction to Digital Design - February 22, 1999
Exercise 8.16 From the network we obtain the following table, based on the expressions below:
J
A
= K
A
= xQ
B
J
B
= K
B
= x
PS Input Input
Q
A
Q
B
x = 0 x = 1 x = 0 x = 1
00 0000 0011 00 0101 0000 1111 01 10
10 0000 0011 10 11
11 0000 1111 11 00
J
A
K
A
J
B
K
B
NS
The outputs are expressed as:
z
3
= Q
A
Q
B
z
2
= Q
A
Q
0
B
z
1
= Q
0
A
Q
B
z
0
= Q
0
A
Q
0
B
Giving the following names to the states:
State Name Code
S
0
00
S
1
01
S
2
10
S
3
11
we get the transition table:
PS Input Output
Q
A
Q
B
x = 0 x = 1
S
0
S
0
S
1
0
S
1
S
1
S
2
1
S
2
S
2
S
3
2
S
3
S
3
S
0
3
NS
The state diagram for the given network is presented in Figure 8.19, and corresponds to a
modulo-4 counter with decoded output.
Exercise 8.17
The expression for the 
ip-
op inputs are
J
A
= xQ
C
J
B
= Q
0
A
J
C
= xQ
B
K
A
= xQ
0
B
K
B
= Q
A
K
C
= x
0
Q
0
B
Solutions Manual - Introduction to Digital Design - February 22, 1999 137
S0/0 S1/1
S2/2S3/3
0
1
0
1
0
1
0
1
Figure 8.19: State diagram for Exercise 8.16
From the characteristic expressions of the JK 
ip-
op we get the following expressions for the
transition functions:
Q
A
(t+ 1) = Q
A
(t)(x
0
+Q
B
(t)) + xQ
0
A
(t)Q
C
(t)
Q
B
(t+ 1) = Q
B
(t)Q
0
A
(t) +Q
0
B
(t)Q
0
A
(t)
Q
C
(t+ 1) = Q
C
(t)(Q
B
(t) + x) +Q
0
C
(t)xQ
B
(t)
z = Q
0
C
(t)
The corresponding transition table is
PS Input Input Output
Q
A
Q
B
Q
C
x = 0 x = 1 x = 0 x = 1 z
000 00,10,01 01,10,00 010 010 1
001 00,10,01 11,10,00 010 111 0
010 00,10,00 00,10,10 010 011 1
011 00,10,00 10,10,10 011 111 0
100 00,01,01 01,01,00 100 000 1
101 00,01,01 11,01,00 100 001 0
110 00,01,00 00,01,10 100 101 1
111 00,01,00 10,01,10 101 101 0
J
A
K
A
; J
B
K
B
; J
C
K
C
NS
To get a high-level description we de�ne the following code:
138 Solutions Manual - Introduction to Digital Design - February 22, 1999
Q
A
Q
B
Q
C
state
000 S
0
001 S
1
010 S
2
011 S
3
100 S
4
101 S
5
110 S
6
111 S
7
The resulting state table is
PS Input Output
x = 0 x = 1 z
S
0
S
2
S
2
1
S
1
S
2
S
7
0
S
2
S
2
S
3
1
S
3
S
3
S
7
0
S
4
S
4
S
0
1
S
5
S
4
S
1
0
S
6
S
4
S
5
1
S
7
S
5
S
5
0
NS
The state diagram is shown in Figure 8.20.
A timing diagram can be obtained from the following input/output sequence pairs (the input
is arbitrary):
x(t) 0 1 0 1 1 0 0 1 0 1 1 1 0 1 0 0 0 1 1
s(t) 0 2 3 3 7 5 4 4 0 2 3 7 5 4 0 2 2 2 3 7
z 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 0 1
Exercise 8.18
The expressions for the 
ip-
op inputs are
T
A
= Q
A
+Q
0
B
T
B
= Q
A
+Q
B
The 
ip-
ops change state in every clock pulse depending only on the previous state. The
transition table is
PS FF inputs NS
Q
A
(t)Q
B
(t) T
A
(t) T
B
(t) Q
A
(t+ 1)Q
B
(t+ 1)
00 1 0 10
01 0 1 00
10 1 1 01
11 1 1 00
Let us de�ne the following encoding:
Solutions Manual - Introduction to Digital Design - February 22, 1999 139
S0/1
S1/0
S2/1
S3/0
S0/1
S5/0
S6/1
S7/0 1
0
0
1
0
1
1
1
0,1
0
0
1
0,1
0
Figure 8.20: State diagram for Exercise 8.17
Q
A
Q
B
00 S
0
01 S
2
10 S
1
11 S
3
The resulting state table is
PS NS
S
0
S
1
S
1
S
2
S
2
S
0
S
3
S
0
The state diagram is presented in Figure 8.21. It is an autonomous modulo-3 counter.
Exercise 8.19
The expressions for the 
ip-
op inputs and for the output are
J
A
= 1 K
A
= 1
J
B
= Q
0
C
K
B
= 1
J
C
= Q
B
K
C
= 1
z = Q
0
A
Q
0
B
Q
0
C
The sequential network does not have any input; therefore, the state register changes in each
clock pulse depending only on the previous state. The transition table is
140 Solutions Manual - Introduction to Digital Design - February 22, 1999
S0 S1 S2 S3
Figure 8.21: State diagram for Exercise 8.18
PS FF inputs NS Output
Q
A
(t)Q
B
(t)Q
C
(t) J
A
(t)K
A
(t) J
B
(t)K
B
(t) J
C
(t)K
C
(t) Q
A
(t+ 1)Q
B
(t+ 1)Q
C
(t+ 1) z(t)
000 11 11 01 110 1
001 11 01 01 100 0
010 11 11 11 101 0
011 11 01 11 100 0
100 11 11 01 010 0
101 11 01 01 000 0
110 11 11 11 001 0
111 11 01 11 000 0
Let us de�ne the following encoding:
Q
A
Q
B
Q
C
state
000 A
001 B
010 C
011 D
100 E
101 F
110 G
111 H
The resulting transition table is
PS NS z
A G 1
B E 0
C F 0
D E 0
E C 0
F A 0
G B 0
H A 0
Let us try to reduce the number of states:
P
1
=
1
(A)
2
2
(B;
2
C;
2
D;
2
E;
2
F;
1
G;
2
H)
1
Solutions Manual - Introduction to Digital Design - February 22, 1999 141
P
2
=
1
(A)
3
2
(F;
1
H)
1
3
(B;
3
C;
2
D;
3
E;
3
G)
3
P
3
=
1
(A)
4
2
(F;
1
H)
1
3
(C)
2
4
(B;
4
D;
4
E;
3
G)
4
P
4
=
1
(A)
5
2
(F;
1
H)
1
3
(C)
2
4
(E)
3
5
(B;
4
D;
4
G)
5
P
5
=
1
(A)
5
2
(F;
1
H)
1
3
(C)
2
4
(E)
3
5
(G)
6
6
(B;
4
D)
4
P
6
= P
5
= f(A); (E); (C); (F;H); (G); (B;D)g
The reduced state table is
PS NS z
(A) = S
0
S
1
1
(E) = S
1
S
2
0
(C) = S
2
S
3
0
(F;H) = S
3
S
0
0
(G) = S
4
S
5
0
(B;D) = S
5
S
1
0
The state diagram is shown in Figure 8.22.
S0/1 S1/0 S2/0
S3/0S4/0S5/0
Figure 8.22: State diagram for Exercise 8.19
The network in its equilibrium state produces a 1 every six clock pulses, that is, it implements
a modulo-6 frequency divider.
Exercise 8.20
The expressions for the 
ip-
op inputs are:
T
A
= Q
A
+Q
B
T
B
= Q
0
A
+Q
B
The transition table is
142 Solutions Manual - Introduction to Digital Design - February 22, 1999
PS FF inputs NS
Q
A
(t)Q
B
(t) T
A
(t)T
B
(t) Q
A
(t+ 1)Q
B
(t+ 1)
00 01 01
01 11 10
10 10 00
11 11 00
Let us de�ne the following encoding:
Q
A
Q
B
00 S
0
01 S
1
10 S
2
11 S
3
The resulting state table is
PS NS
S
0
S
1
S
1
S
2
S
2
S
0
S
3
S
0
The state diagram is shown in Figure 8.23. The network implements an autonomous modulo-3
counter.
S0 S1 S2 S3
Figure 8.23: State diagram for Exercise 8.20
Exercise 8.21
The expressions for the 
ip-
op inputs and for the output are
S
2
= xQ
0
1
+ xQ
0
2
Q
0
0
R
2
= Q
2
Q
1
J
1
= Q
0
(x
0
+Q
2
)
K
1
= Q
0
+Q
2
T
0
= (x
0
+Q
2
+Q
1
)(Q
0
2
+Q
0
1
+Q
0
)(x+Q
0
2
+Q
1
+Q
0
0
)
z = (Q
0
2
�Q
1
)(x
0
Q
0
0
) +Q
0
1
(x
0
Q
0
) + (Q
2
�Q
1
)(xQ
0
0
) +Q
1
(xQ
0
)
The transition table is
Solutions Manual - Introduction to Digital Design - February22, 1999 143
PS Input Input
Q
2
Q
1
Q
0
x = 0 x = 1 x = 0 x = 1
000 00 00 1 10 00 0 001,1 100,0
001 00 11 1 10 01 0 010,1 101,0
010 00 00 1 10 00 1 011,0 111,1
011 00 11 1 00 01 1 000,0 000,1
100 00 01 1 10 01 1 101,0 101,1
101 00 11 0 10 11 1 111,1 110,0
110 01 01 0 01 01 0 000,1 000,0
111 01 11 1 01 11 1 000,0 000,1
S
2
R
2
J
1
K
1
T
0
NS,z
Let us de�ne the following encoding:
Q
2
Q
1
Q
0
000 A
001 B
010 C
011 D
100 E
101 F
110 G
111 H
The resulting state table is
PS Input
x = 0 x = 1
A B,1 E,0
B C,1 F,0
C D,0 H,1
D A,0 A,1
E F,0 F,1
F H,1 G,0
G A,1 A,0
H A,0 A,1
NS,z
Let us try to reduce the number of states.
P
1
group 1 group 2
(A,B,F,G) (C,D,E,H)
0 1 2 2 1 2 1 1 1
1 2 1 1 1 2 1 1 1
P
2
group 1 group 2 group 3 group 4 group 5
(A) (B,F) (G) (C) (D,E,H)
0 2 4 5 1 5 1 2 1
1 5 2 3 1 5 1 2 1
144 Solutions Manual - Introduction to Digital Design - February 22, 1999
P
3
group 1 group 2 group 3 group 4 group 5 group 6 group 7
(A) (B) (F) (G) (C) (E) (D,H)
0 2 5 7 1 7 3 1 1
1 6 3 4 1 7 3 1 1
P
4
= P
3
= f(A); (B); (F ); (G); (C); (E); (D;H)g
The reduced state table is
PS Input
x = 0 x = 1
(A) � S
0
S
1
; 1 S
4
; 0
(B) � S
1
S
2
; 1 S
5
; 0
(C) � S
2
S
3
; 0 S
3
; 1
(D;H) � S
3
S
0
; 0 S
0
; 1
(E) � S
4
S
5
; 0 S
5
; 1
(F ) � S
5
S
3
; 1 S
6
; 0
(G) � S
6
S
0
; 1 S
0
; 0
NS,z
The state diagram is shown in Figure 8.24.
S0 S1 S2
S3
S4S5S6
0/1 0/1
0/0
1/1
1/0
0/0
1/1
0/0
1/1
1/0
0/1
1/0
1/0
0/1
Figure 8.24: State diagram for Exercise 8.21
We now show that the network performs a serial conversion from BCD to Excess-3. Assume that
the initial state is S
0
and that the BCD digit (x
3
; x
2
; x
1
; x
0
) is applied with the least signi�cant
bit (x
0
) �rst. From the state diagram (following the corresponding paths) we get the following
table (since after a sequence of length four the state is again S
0
, we only consider sequences of that
length):
Solutions Manual - Introduction to Digital Design - February 22, 1999 145
x
3
x
2
x
1
x
0
z
3
z
2
z
0
0000 0011
0001 0100
0010 0101
0011 0110
0100 0111
0101 1000
0110 1001
0111 1010
1000 1011
1001 1100
This corresponds to the desired converter. A timing diagram is
x 0 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0
State S
0
S
1
S
2
S
3
S
0
S
1
S
2
S
3
S
0
S
4
S
5
S
3
S
0
S
4
S
5
S
3
z 1 1 0 0 1 1 1 0 0 0 1 1 0 1 1 0
Exercise 8.22
Since the excitation function of a D 
ip-
op is
D(t) = Q(t+ 1)
the D input for each 
ip-
op implementation corresponds to its characteristic function. That
is,
for a SR 
ip-
op
D(t) = Q(t+ 1) = S +R
0
Q(t)
for a T 
ip-
op
D(t) = Q(t+ 1) = T �Q(t)
for a JK 
ip-
op
D(t) = Q(t+ 1) = Q(t)K
0
+Q(t)
0
J
The corresponding networks are shown in Figures 8.25.
Exercise 8.23
To recognize a sequence with two consecutive 1's followed by one 0 we need to distinguish be-
tween the following cases:
S
2
: x(t� 2) = x(t� 1) = 1
S
1
: Not S
2
and x(t� 1) = 1
S
0
: None of the above
The corresponding state table is
146 Solutions Manual - Introduction to Digital Design - February 22, 1999
CK
CK
T
J
K
Q
Q’
Q
Q’
(a)
(b)
(c)
D Q
Q’CK
S
R
Q
Q’
D Q
Q’
D Q
Q’
Figure 8.25: Networks of Exercise 8.22
PS Input
x = 0 x = 1
S
0
S
0
; 0 S
1
; 0
S
1
S
0
; 0 S
2
; 0
S
2
S
0
; 1 S
2
; 0
NS,z
To implement these states we need at least two 
ip-
ops. Let us de�ne the following state
assignment:
Q
2
Q
1
S
0
00
S
1
01
S
2
10
The resulting state table is
PS Input
Q
2
Q
1
x = 0 x = 1
00 00,0 01,0
01 00,0 10,0
10 00,1 10,0
NS,z
Solutions Manual - Introduction to Digital Design - February 22, 1999 147
Since the excitation function of a JK 
ip-
op is
PS NS
0 1
0 0- 1-
1 -1 -0
JK
the inputs J
1
;K
1
; J
2
, and K
2
to the JK 
ip-
ops are
PS Input
Q
2
Q
1
x = 0 x = 1
00 0-,0- 0-,1-
01 0-,-1 1-,-1
10 -1,0- -0,0-
J
2
K
2
; J
1
K
1
Switching expressions for these 
ip-
op inputs are
J
2
= Q
1
x J
1
= Q
0
2
x
K
2
= x
0
K
1
= 1
An expression for the output is
z = Q
2
x
0
The sequential network is shown in Figure 8.26.
J
K
CK
Q
Q’
J
K
CK
Q
Q’
1 2
x
1
CK
Q1 Q2
x’
z
Figure 8.26: Network for Exercise 8.23
Exercise 8.24
Since the output at time t depends on the inputs at time t � 3; t � 2; t � 1, it is necessary to
store these in the state register. That is, the register consists of three 
ip-
ops such that
Q
2
(t) = x(t� 3)
Q
1
(t) = x(t� 2)
Q
0
(t) = x(t� 1)
148 Solutions Manual - Introduction to Digital Design - February 22, 1999
Consequently, the state description is
Q
2
(t+ 1) = Q
1
(t)
Q
1
(t+ 1) = Q
0
(t)
Q
0
(t) = x(t)
z = x(t� 3)� x(t� 2)� x(t� 1)� x(t) = Q
2
�Q
1
�Q
0
� x
If we use D 
ip-
ops, we get
D
2
= Q
1
D
1
= Q
0
D
0
= x
The sequential network is shown in Figure 8.27.
D Q
Q’
D Q
Q’
D Q
Q’
Z
Q0 Q1
X
CK
FF0 FF1 FF2
Figure 8.27: Network for Exercise 8.24
Exercise 8.25
We have to store the last input to be able to recognize the sequence 11; therefore, we need:
S
0
: x(t� 1) = 0
S
1
: x(t� 1) = 1
The state table is
PS Input
x = 0 x = 1
S
0
S
0
; 0 S
1
; 0
S
1
S
0
; 0 S
1
; 1
NS,z
Coding S
0
as 0 and S
1
as 1, the resulting state table is
PS Input
Q x = 0 x = 1
0 0,0 1,0
1 0,0 1,1
NS,z
Solutions Manual - Introduction to Digital Design - February 22, 1999 149
We only need one JK 
ip-
op. Since its excitation function is
PS NS
0 1
1 0- 1-
1 -1 -0
JK
the inputs are
J = x
K = x
0
The output is described by
z = Qx
The sequential network is shown in Figure 8.28.
J
K
CK
Q
Q’
CK
Z
X
Figure 8.28: Network for Exercise 8.25
Exercise 8.26
The state corresponds to the count. That is,
s(t+ 1) = (s(t) + 1) mod 3
Using a radix-2 representation for the count we get the following state table
PS Input
Q
2
Q
1
x = 0 x = 1
00 00 01
01 01 10
10 10 00
NS
Since the excitation function of a SR 
ip-
op is
PS NS
0 1
0 0- 10
1 01 -0
SR
150 Solutions Manual - Introduction to Digital Design - February 22, 1999
we get the following switching expressions
S
2
= xQ
1
S
1
= xQ
0
2
Q
0
1
R
2
= xQ
2
R
1
= xQ
1
The output is obtained directly from the state register. The sequential network is shown in
Figure 8.29.
S
R
CK
Q
Q’
S
R
CK
Q
Q’
Q2
Q2’
Q1
Q1’
x
CK
CK
Figure 8.29: Network for Exercise 8.26
Exercise 8.27
a) To design a cyclic counter with the output sequence 0; 1; 3; 7; 6; 4; 0; 1; : : : we need six states.
In this �rst part, we select the coding so that the output corresponds to the state. The state table
is
PS Input
x = 0 x = 1
000000 001
001 001 011
011 011 111
100 100 000
110 110 100
111 111 110
NS = z
Since the excitation function of a JK 
ip-
op is
PS NS
0 1
0 0- 1-
1 -1 -0
JK
Solutions Manual - Introduction to Digital Design - February 22, 1999 151
we get the following 
ip-
op inputs
PS Input
Q
2
Q
1
Q
0
x = 0 x = 1
000 0- 0- 0- 0- 0- 1-
001 0- 0- -0 0- 1- -0
011 0- -0 -0 1- -0 -0
100 -0 0- 0- -1 0- 0-
110 -0 -0 0- -0 -1 0-
111 -0 -0 -0 -0 -0 -1
J
2
K
2
J
1
K
1
J
0
K
0
From K-maps we obtain
J
2
= xQ
1
K
2
= xQ
0
1
J
1
= xQ
0
K
1
= xQ
0
0
J
0
= xQ
0
2
K
0
= xQ
2
The sequential network is shown in Figure 8.30. Recall that the output z = (z
2
; z
1
; z
0
) corre-
sponds to the state vector (Q
2
; Q
1
; Q
0
).
J
K
CK
Q
Q’
J
K
CK
Q
Q’
0 1
x
CK
J
K
CK
Q
Q’
2
z2
z1
z0
Figure 8.30: Network for Exercise 8.27
b) In this second case, the state table is
PS Input
x = 0 x = 1
S
0
S
0
S
1
0
S
1
S
1
S
2
1
S
2
S
2
S
3
3
S
3
S
3
S
4
7
S
4
S
4
S
5
6
S
5
S
5
S
0
4
NS Output
with the following encoding for the state:
152 Solutions Manual - Introduction to Digital Design - February 22, 1999
Q
2
Q
1
Q
0
S
0
000
S
1
001
S
2
010
S
3
011
S
4
100
S
5
101
Using the previously given excitation function for a JK 
ip-
op, the 
ip-
ops inputs are
PS Input Output
Q
2
Q
1
Q
0
x = 0 x = 1 z(t)
000 0- 0- 0- 0- 0- 1- 000
001 0- 0- -0 0- 1- -1 001
010 0- -0 0- 0- -0 1- 011
011 0- -0 -0 1- -1 -1 111
100 -0 0- 0- -0 0- 1- 110
101 -0 0- -0 -1 0- -1 100
J
2
K
2
J
1
K
1
J
0
K
0
From K-maps we obtain
J
2
= xQ
1
Q
0
K
2
= xQ
0
J
1
= xQ
0
2
Q
0
K
1
= xQ
0
J
0
= x K
0
= x
For the output,
z
2
= Q
2
+ Q
1
Q
0
z
1
= Q
1
+ Q
2
Q
0
0
z
0
= Q
1
+ Q
0
2
Q
0
The sequential network is shown in Figure 8.31.
A comparison of the networks of Figures 8.30 and 8.31 indicates that solution (a) results in a
simpler network.
Exercise 8.28
A modulo-7 up/down counter requires seven states. Since the counter is binary, the state
assignment is speci�ed. The system has two inputs: x the variable to be counted, and c, to control
up (c = 1) or down (c = 0) counting. The state table is
PS Input
x = 0 x = 1(down) x = 1(up)
000 000 110 001
001 001 000 010
010 010 001 011
011 011 010 100
100 100 011 101
101 101 100 110
110 110 101 000
NS = z
Solutions Manual - Introduction to Digital Design - February 22, 1999 153
J
K
CK
Q
Q’
J
K
CK
Q
Q’
0 1
x
CK
J
K
CK
Q
Q’
2
Q1
Q0
Q2
Q2
Q0’
Q1
z2 z1
Q2’
Q0
Q1
z0
Figure 8.31: Network for Exercise 8.27 (b)
(a) Based on the excitation function for a T 
ip-
op we obtain the following table for 
ip-
op
inputs:
PS Input
Q
2
Q
1
Q
0
x = 0 x = 1(down) x = 1(up)
000 000 110 001
001 000 001 011
010 000 011 001
011 000 001 111
100 000 111 001
101 000 001 011
110 000 011 110
T
2
T
1
T
0
From K-maps we obtain:
T
2
= x(cQ
1
Q
0
+ cQ
2
Q
1
+ c
0
Q
0
1
Q
0
0
)
T
1
= x(cQ
0
+Q
2
Q
1
+ c
0
Q
0
0
) = x((c�Q
0
0
) +Q
2
Q
1
)
T
0
= x(c+Q
2
+Q
1
+Q
0
)(c
0
+Q
0
2
+Q
0
1
)
The network is shown in Figure 8.32.
(b) using D-type 
ip-
ops the next state is given as input, Q(t + 1) = D(t), so the �rst table
shown in this exercise is used. This time, the next state bits for the case x = 0 have values di�erent
than zero, and for this reason we need to consider the cases x = 0 and x = 1 separately. Let the
inputs of the D-type FFs be D
2
;D
1
, and D
0
. For the case x = 1, using K-maps, we obtain:
D
2
(x = 1) = Q
2
Q
0
+Q
1
Q
0
c+Q
2
Q
0
1
c+Q
2
Q
1
c
0
+Q
0
2
Q
0
1
Q
0
0
c
0
D
1
(x = 1) = Q
0
1
Q
0
0
c
0
+Q
0
1
Q
0
c+Q
1
Q
0
c
0
+Q
0
2
Q
1
Q
0
0
c
D
0
(x = 1) = Q
2
Q
0
1
Q
0
0
+Q
0
2
Q
0
0
c+Q
1
Q
0
0
c
0
For x = 0 the expressions for D
i
are:
D
2
(x = 0) = Q
2
D
1
(x = 0) = Q
1
D
0
(x = 0) = Q
0
154 Solutions Manual - Introduction to Digital Design - February 22, 1999
Combining both cases we obtain the expressions:
D
2
= (Q
2
Q
0
+Q
1
Q
0
c+Q
2
Q
0
1
c+Q
2
Q
1
c
0
+Q
0
2
Q
0
1
Q
0
0
c
0
)x+Q
2
x
0
D
1
= (Q
0
1
Q
0
0
c
0
+Q
0
1
Q
0
c+Q
1
Q
0
c
0
+Q
0
2
Q
1
Q
0
0
c)x+Q
1
x
0
D
0
= (Q
2
Q
0
1
Q
0
0
+Q
0
2
Q
0
0
c+Q
1
Q
0
0
c
0
)x+Q
0
x
0
The network is shown in Figure 8.32.
(c) the implementation of this circuit using a combination of T and D-type 
ip-
ops is a com-
bination of the cases presented in the previous two designs. Considering the two least signi�cant
state bits stored in T-type FFs and the most-signi�cant in a D-type FF, the switching expressions
are:
D
2
= (Q
2
Q
0
+Q
1
Q
0
c+Q
2
Q
0
1
c+Q
2
Q
1
c
0
+Q
0
2
Q
0
1
Q
0
0
c
0
)x+Q
2
x
0
T
1
= x((c�Q
0
0
) +Q
2
Q
1
)
T
0
= x(c+Q
2
+Q
1
+Q
0
)(c
0
+Q
0
2
+Q
0
1
)
The network for this case is easily obtained from the other networks given for parts (a) and (b).
Exercise 8.29
To recognize the sequence x(t�3; t) = 0101 or 0110 we need to distinguish among the following
cases:
S
4
: x(t� 3; t� 1) = 011
S
3
: x(t� 3; t� 1) = 010
S
2
: x(t� 2; t� 1) = 01
S
1
: Not S
3
and x(t� 1) = 0
S
0
: None of the above
The corresponding state table is
PS Input
x = 0 x = 1
S
0
S
1
; 0 S
0
; 0
S
1
S
1
; 0 S
2
; 0
S
2
S
3
; 0 S
4
; 0
S
3
S
1
; 0 S
2
; 1
S
4
S
1
; 1 S
0
; 0
NS,z
Assigning to each state the binary value of its subindex the resulting state table is
PS Input
Q
2
Q
1
Q
0
x = 0 x = 1
000 001,0 000,0
001 001,0 010,0
010 011,0 100,0
011 001,0 010,0
100 001,1 000,0
NS,z
Solutions Manual - Introduction to Digital Design - February 22, 1999 155
(a) T-type FF implementation
(b) D-type FF implementation
D Q
Q2
CK
D2
Q2
Q0
Q1
Q0
c
Q2
Q1’
c
Q2
Q1
c’
Q2’
Q1’
Q0’
c’
x
x’
Q2
T Q
Q1
CK
x
Q1
Q2
x
T1
c
Q0’
c
Q1
Q
x
c
Q2
Q
x
c’
Q1’
Q0’
x
T Q
Q2
CK
T2
T Q
Q0
CK
c
Q2
Q1
Q0
T0
c
Q2
Q1
Q0
x
D Q
Q1
CK
D1
Q1’
Q0’
c’
Q1’
Q0
c
Q1
Q0
c’
Q2’
Q1
Q0’
c
x
x’
Q1
D Q
Q0
CK
D0
Q2
Q1’
Q0’
Q2’
Q0’
c
Q1
Q0’
c’
x
x’
Q0
Figure 8.32: Networks for Exercise 8.28
Sincethe excitation function of a JK 
ip-
op is
PS NS
0 1
0 0- 1-
1 -1 -0
JK
we determine the inputs J
2
;K
2
; J
1
;K
1
; J
1
, and K
1
to be
156 Solutions Manual - Introduction to Digital Design - February 22, 1999
PS Input
Q
2
Q
1
Q
0
x = 0 x = 1
000 0- 0- 1- 0- 0- 0-
001 0- 0- -0 0- 1- -1
010 0- -0 1- 1- -1 0-
011 0- -1 -0 0- -0 -1
100 -1 0- 1- -1 0- 0-
J
2
K
2
J
1
K
1
J
0
K
0
Using K-maps we get the following switching expressions:
J
2
= xQ
1
Q
0
0
K
2
= 1
J
1
= xQ
0
K
1
= xQ
0
0
+ x
0
Q
0
J
0
= x
0
K
0
= x
The output expression is:
z = x
0
Q
2
+ xQ
1
Q
0
The sequential network is shown in Figure 8.33
J
K
CK
Q
Q’
J
K
CK
Q
Q’
Q2
Q1
Q2’
Q1’
2
1
x x’
x
Q1
Q0’
"1"
x
Q0
x
Q0’
x’
Q0
CK
x’
x
Q0
z
J
K
CK
Q
Q’
Q0
Q0’
0
x’
x
Figure 8.33: Network for Exercise 8.29
Exercise 8.30 The modulo-5 counter presented in Example 8.8 was implemented using T-type
ip-
op. For this problem we need to synthesize di�erent functions for D-type 
ip-
ops. The
transition table, though, is exactly the same.
Solutions Manual - Introduction to Digital Design - February 22, 1999 157
PS Input
Q
2
Q
1
Q
0
x = 0 x = 1
000 000 001
001 001 010
010 010 011
011 011 100
100 100 000
NS
Since the D-type 
ip-
ops has as inputs the bits of the next state (shown in the transition
table), the K-maps are:
D
2
:
0 0 0 0
1
- - -
0
- - -
0 0 1 0
Q
0
Q
1
Q
2
x
D
1
:
0 0 1 1
0
- - -
0
- - -
0 1 0 1
Q
0
Q
1
Q
2
x
D
0
:
0 1 1 0
0
- - -
0
- - -
1 0 0 1
Q
0
Q
1
Q
2
x
The inputs of the D-type 
ip-
ops are:
D
2
= xQ
1
Q
0
+ x
0
Q
2
D
1
= xQ
0
1
Q
0
+Q
1
Q
0
0
+ x
0
Q
1
D
0
= xQ
0
2
Q
0
0
+ x
0
Q
0
The gate network for the sequential system is presented in Figure 8.34. Comparing Figure 8.34
with Figure 8.28 of the text we can easily see that this implementation uses more gates than the
one done with T-type 
ip-
ops.
Exercise 8.31 To implement Example 8.9 using JK 
ip-
ops we use the following state tran-
sition table and output, that already includes the appropriate input functions for the 
ip-
ops:
PS Input Input
Q
1
Q
0
01 10 11 01 10 11
00 01,0 10,1 10,0 0-1- 1-0- 1-0-
01 00,0 11,1 11,0 0{1 1{0 1{0
10 11,0 10,0 00,1 -01- -00- -10-
11 10,0 00,0 11,1 -0-1 -1-1 -0-0
NS, z J
1
K
1
J
0
K
0
The Kmaps for the combinational circuit that activates the JK inputs of the 
ip-
ops are:
158 Solutions Manual - Introduction to Digital Design - February 22, 1999
D Q
Q’CK
x
Q1
Q0
x’
Q2
D2 Q2
Q2’
D Q
Q’CK
x
Q2’
Q0’
x’
Q0
D0 Q0
Q0’
D Q
Q’CK
x
Q1’
Q0
Q1
Q0’
D1 Q1
Q1’
x’
Q1
Figure 8.34: Modulo-5 counter implemented using D-type 
ip-
ops
J
1
:
-
0 1 1
-
0 1 1
- - - -
- - - -
x
0
x
1
Q
0
Q
1
�
�
�
�
K
1
:
- - - -
- - - -
-
0 0 1
-
0 1 0
x
0
x
1
Q
0
Q
1
�
�
�
�
��
�
J
0
:
-
1 0 0
- - - -
- - - -
-
1 0 0
x
0
x
1
Q
0
Q
1
�
�
�
�
K
0
:
- - - -
-
1 0 0
- - - -
-
1 0 1
x
0
x
1
Q
0
Q
1
�
�
�
�
�
�
�
�
which result in the following expressions:
J
1
= x
1
Solutions Manual - Introduction to Digital Design - February 22, 1999 159
k
1
= x
1
x
0
Q
0
0
+ x
0
0
Q
0
J
0
= x
0
1
K
0
= x
0
1
+ x
0
0
Q
1
The gate network for this exercise is shown in Figure 8.35. This network has fewer gates than
that of Figure 8.29 of the text.
J
K
CK
Q
Q’
Q0
Q0’
1
x1
J
K
CK
Q
Q’
Q0
Q0’
0
x1
x0
Q0’
x0’
Q0
CK
x1’
x0’x0
x1’x1
x0’
Q1
x1
x0
Q1
x0’
Q1’
z
Figure 8.35: Network for Exercise 8.31
Exercise 8.32 Modulo-3 binary counter using \one 
ip-
op per state" approach.
The counter has 3 states S 2 f0; 1; 2g, thus 3 
ip-
ops are required. The state codes are:
y
2
y
1
y
0
State
0 0 1 0
0 1 0 1
1 0 0 2
The counter changes state when the input x = 1. The state diagram for the counter is shown in
Figure 8.36. The switching expressions for the network can be obtained by inspection of the state
diagram:
Y
2
= S
1
x+ S
2
x
0
= y
1
x+ y
2
x
0
Y
1
= y
0
x+ y
1
x
0
Y
0
= y
2
x+ y
0
x
0
z
1
= y
2
z
0
= y
1
The corresponding network is shown in Figure 8.37.
160 Solutions Manual - Introduction to Digital Design - February 22, 1999
S0 S1 S2
0
1
0
1
0
1
Figure 8.36: State Diagram for a Modulo-3 Counter
Y1
y1
D Q
FF0
D Q
FF2
y0
y2
x Y0
y2
y0
Y2
y2
D Q
FF1
y1
CK
z0
z1
Figure 8.37: Modulo-3 counter - Exercise 8.32
Exercise 8.33 Each state is represented by one 
ip-
op. Consider that the input of these FFs
are represented as NA;NB;NC;ND;NE; and NF respectively. The switching expressions for
these variables are:
NA = Fx
0
+Bx
NB = Ax
0
+ Cx
NC = Bx
0
+ Cx
ND = Cx
0
+Ex
NE = Dx
0
+ Fx
NF = Ex
0
+Ax
For the following output encoding
z
1
z
0
a 00
b 01
c 10
the switching expressions for the output are:
z
0
= Dx
0
+Ax+Cx+E
Solutions Manual - Introduction to Digital Design - February 22, 1999 161
z
1
= Bx+Dx+ F
The network that corresponds to these expressions is shown in Figure 8.38.
D Q
FF2
CNC
C
B
NB
A
D Q
FF0
Ax NA
B
F
D Q
FF1
B
CK
C
D Q
FF2
DND
E
C
D Q
FF2
ENE
F
D
D Q
FF2
FNF
A
E
D
x’
A
C
x
z0
E
B
D
x
z1
F
Figure 8.38: Network for Exercise 8.33
Exercise 8.34 The sequential network with a shifting state register is shown in Figure 8.39,
using a Mealy model. A Moore model implementation would require an extra 
ip-
op.
D Q
FF0
D Q
FF0
D Q
FF0
D Q
FF0
x
CK
z
Figure 8.39: Network for Exercise 8.34