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

Prévia do material em texto

163
Chapter 9
Exercise 9.1 (a) Implement a 10 output (decimal) decoder for 2-out-of-5 code using NAND
gates. The 2-out-of-5 code represents decimal digits as shown in the following table:
i x
4
x
3
x
2
x
1
x
0
0 00011
1 11000
2 10100
3 01100
4 10010
5 01010
6 00110
7 10001
8 01001
9 00101
Each output z
i
of the decoder is activated when the input has the 2-out-of-5 code that represents
the value i in decimal and the enable input E = 1. The expressions for the outputs are:
z
0
= x
0
4
x
0
3
x
0
2
x
1
x
0
E
z
1
= x
4
x
3
x
0
2
x
0
1
x
0
0
E
z
2
= x
4
x
0
3
x
2
x
0
1
x
0
0
E
z
3
= x
0
4
x
3
x
2
x
0
1
x
0
0
E
z
4
= x
4
x
0
3
x
0
2
x
1
x
0
0
E
z
5
= x
0
4
x
3
x
0
2
x
1
x
0
0
E
z
6
= x
0
4
x
0
3
x
2
x
1
x
0
0
E
z
7
= x
4
x
0
3
x
0
2
x
0
1
x
0
E
z
8
= x
0
4
x
3
x
0
2
x
0
1
x
0
E
z
9
= x
0
4
x
0
3
x
2
x
0
1
x
0
E
Part of the gate network for the circuit is shown in Figure 9.1.
x4 x4’
x3 x3’
x2 x2’
x1 x1’
x0 x0’
x4’
x3’
x2’
x1
x0
E
z0
x4
x3
x2’
x1’
x0’
E
z1
Figure 9.1: Network for Exercise 9.1 (a)
164 Solutions Manual - Introduction to Digital Design - March 22, 1999
(b) Implement a 10 output (decimal) decoder using NAND gates for a 4-bit Gray code. The
code table is shown next.
i g
3
g
2
g
1
g
0
0 0000
1 0001
2 0011
3 0010
4 0110
5 0111
6 0101
7 0100
8 1100
9 1101
The expressions for the ten outputs z
0
to z
9
are:
z
0
= g
0
2
g
0
1
g
0
0
E
z
1
= g
0
2
g
0
1
g
0
E
z
2
= g
0
2
g
1
g
0
E
z
3
= g
0
2
g
1
g
0
0
E
z
4
= g
2
g
1
g
0
0
E
z
5
= g
2
g
1
g
0
E
z
6
= g
0
3
g
2
g
0
1
g
0
E
z
7
= g
0
3
g
2
g
0
1
g
0
0
E
z
8
= g
3
g
0
0
E
z
9
= g
3
g
0
E
The implementation, shown in Figure 9.2, consists of six 4-input NAND gates, two 5-input NAND
gates, two 3-input NAND gates, and 14 NOT gates.
(c) Implement a 10 output (decimal) decoder using NAND gates for a 2-4-2-1 code. The code
table is shown next.
i c
3
c
2
c
1
c
0
0 0000
1 0001
2 0010
3 0011
4 0100
5 1011
6 1100
7 1101
8 1110
9 1111
The switching expressions for the decoder outputs are:
z
0
= c
0
3
c
0
2
c
0
1
c
0
0
E
Solutions Manual - Introduction to Digital Design - March 22, 1999 165
E
g3
g2
g1
g0
g3’
g2’
g1’
g0’
g2’
g1’
g0’
g2’
g1’
g0
g2’
g1
g0
g2’
g1
g0’
g2
g1
g0’
g2
g1
g0
g3
g0’
g3
g0
z0
z1
z2
z3
z4
z5
z6
z7
z8
z9
g3’
g2
g1’
g0
g3’
g2
g1’
g0
Figure 9.2: Network for Exercise 9.1 (b)
z
1
= c
0
3
c
0
2
c
0
1
c
0
E
z
2
= c
0
3
c
0
2
c
1
c
0
0
E
z
3
= c
0
3
c
0
2
c
1
c
0
E
z
4
= c
0
3
c
2
c
0
1
c
0
0
E
z
5
= c
3
c
0
2
c
1
c
0
E
z
6
= c
3
c
2
c
0
1
c
0
0
E
z
7
= c
3
c
2
c
0
1
c
0
E
z
8
= c
3
c
2
c
1
c
0
0
E
z
9
= c
3
c
2
c
1
c
0
E
Part of the gate network that implements these expressions is shown in Figure 9.3.
166 Solutions Manual - Introduction to Digital Design - March 22, 1999
c3 c3’
c2 c2’
c1 c1’
c0 c0’
c3’
c2’
c1’
c0’
E
z0
c3’
c2’
c1’
c0
E
z1
Figure 9.3: Gate network for Exercise 9.1 (c)
Exercise 9.2: Implement a BCD decoder using an Excess-3 decoder, a 2-input binary decoder
and a NOR gate.
The relation between BCD code and the Excess-3 code is:
x 0 1 2 3 4 5 6 7 8 9 10 11 12
z (Ex-3) - - - 0 1 2 3 4 5 6 7 8 9
y (BCD) 0 1 2 3 4 5 6 7 8 9 - - -
where x is the radix-2 representation of the input vector and z and y are the indices of the outputs
of the decoders with value 1.
From the table we see that for x between 3 and 9, the output of the Excess-3 decoder can be
relabeled to give some of the outputs of the BCD decoder. Since for x between 0 and 2, no output
of the Excess-3 decoder has value 1, it is necessary to decode these values separately. It's possible
to do this using a 2-input binary decoder that has as inputs the bits x
1
and x
0
(the least signi�cant
bits) and making the enable input active when x � 3.
The corresponding network is shown in Figure 9.4, on page 167.
Exercise 9.3 The 4-bit Odd/Even parity functions have value 1 when the number of 1s in the
input vector is odd/even. The implementation of these functions using a 4-input decoder and OR
gates is shown in Figure 9.5. The even parity is produced by output EP and the odd parity by
output OP .
Exercise 9.4: For a coincident decoder using n = 12 and k = 4, we use r = n=k = 3 4-input
decoders and 2
12
3-input AND gates.
The circuit is shown in Figure 9.6. In the �gure only some of the AND gates are shown, with
the corresponding output numbers. In general, if we partition the input into groups of 4 bits, we
get:
u = 8x
11
+ 4x
10
+ 2x
9
+ x
8
s = 8x
7
+ 4x
6
+ 2x
5
+ x
4
t = 8x
3
+ 4x
2
+ 2x
1
+ x
0
and the output z
i
= 1 if i = u2
8
+ s2
4
+ t.
Solutions Manual - Introduction to Digital Design - March 22, 1999 167
E
E
Excess-3
dec
Binary
dec
0
1
2
3
0
1
2
3
4
5
6
7
8
9
0
1
2
3
0
1
BCD: (x3,x2,x1,x0)
decoded outputs: yi
y4
y5
y6
y7
y8
y9
y0
y1
y2
y3
x0
x1
x2
x3
Figure 9.4: BCD decoder - Exercise 9.2
Exercise 9.5 Part (a)
� number of levels in the tree of decoders = 20=4 = 5 levels.
� the number of decoders in this tree = 1 + 16 + 16
2
+ 16
3
+ 16
4
= 69905 decoders.
Part (b) using coincident decoding we need �ve 4-input decoders to receive the 20 inputs. We
would need 2
20
AND gates.
Exercise 9.6
Let us call x = (x
9
; x
8
; x
7
; x
6
; x
5
; x
4
; x
3
; x
2
; x
1
; x
0
) the input vector of the 10-input decoder. The
output vector will depend on the code to be generated.
E
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
x3
x2
x1
x0
3
2
1
0
Dec.
I0
I1
I2
I3
I4
I5
I6
I7
I8
I9
I10
I11
I12
I13
I14
I15
I1
I2
I4
I8
I7
I11
I13
I14
EP
I0
I3
I5
I6
I9
I10
I12
I15
OP
1
Figure 9.5: Parity functions - Exercise 9.3
168 Solutions Manual - Introduction to Digital Design - March 22, 1999
3 2 1 0
15 14 2 1 0
E Decoder
3 2 1 0
15 14 2 1 0
E Decoder
3 2 1 0
15 14 2 1 0
E DecoderE E E
x11 x10 x9 x8 x7 x6 x5 x4 x3 x2 x1 x0
z4095 z4094 z31 z1 z0
Figure 9.6: Coincident decoder for Exercise 9.4
(a) For the 2-out-of-5 code (consider the table presented in exercise 9.1) the expressions are:
z
4
= (x
1
+ x
2
+ x
4
+ x
7
)E
z
3
= (x
1
+ x
3
+ x5
+ x
8
)E
z
2
= (x
2
+ x
3
+ x
6
+ x
9
)E
z
1
= (x
0
+ x
4
+ x
5
+ x
6
)E
z
0
= (x
0
+ x
7
+ x
8
+ x
9
)E
(b) For the 4-bit Gray code the output vector is (z
3
; z
2
; z
1
; z
0
) (see table in Exercise 9.1.). The
expressions are:
z
3
= (x
8
+ x
9
)E
z
2
= (x
4
+ x
5
+ x
6
+ x
7
+ x
8
+ x
9
)E
z
1
= (x
2
+ x
3
+ x
4
+ x
5
)E
z
0
= (x
1
+ x
2
+ x
5
+ x
6
+ x
9
)E
(c) For Excess-3 code the output vector is (z
3
; z
2
; z
1
; z
0
). The Excess-3 code is shown in the
next table:
i z
3
z
2
z
1
z
0
0 0011
1 0100
2 0101
3 0110
4 0111
5 1000
6 1001
7 1010
8 1011
9 1100
Solutions Manual - Introduction to Digital Design - March 22, 1999 169
The expressions for the outputs are:
z
3
= (x
5
+ x
6
+ x
7
+ x
8
+ x
9
)E
z
2
= (x
1
+ x
2
+ x
3
+ x
4
+ x
9
)E
z
1
= (x
0
+ x
3
+ x
4
+ x
7
+ x
8
)E
z
0
= (x
0
+ x
2
+ x
4
+ x
6
+ x
8
)E
The networks of gates are easily obtained from these expressions.
Exercise 9.7
From the �gure, we get the following expressions for the circuit outputs:
D = (I
0
8
+ I
0
9
)
0
= I
8
I
9
C = ((I
0
8
+ I
0
9
)
0
:(I
0
4
+ I
0
5
+ I
0
6
+ I
0
7
))
0
= (I
8
I
9
:(I
0
4
+ I
0
5
+ I
0
6
+ I
0
7
))
0
B = (I
8
I
9
:(I
0
2
I
4
I
5
+ I
0
3
I
4
I
5
+ I
0
6
+ I
0
7
))
0
= (I
8
I
9
(I
0
6
+ I
0
7
) + I
9
I
8
I
7
I
6
I
5
I
4
(I
0
3
+ I
0
2
))
0
A = ((I
8
I
9
):(I
0
1
I
2
I
4
I
6
+ I
0
3
I
4
I
6
+ I
0
5
I
6
+ I
0
7
) + I
0
9
)
0
= (I
0
9
+ I
9
I
8
I
0
7
+ I
9
I
8
I
7
I
6
I
0
5
+ I
9
I
8
I
7
I
6
I
5
I
4
I
0
3
+ I
9
I
8
I
7
I
6
I
5
I
4
I
3
I
2
I
0
1
)
0
From these expression we get the following table:
I
0
9
I
0
8
I
0
7
I
0
6
I
0
5
I
0
4
I
0
3
I
0
2
I
0
1
D' C' B' A' Output(decimal)
1 - - - - - - - - 1 0 0 1 9
0 1 - - - - - - - 1 0 0 0 8
0 0 1 - - - - - - 0 1 1 1 7
0 0 0 1 - - - - - 0 1 1 0 6
0 0 0 0 1 - - - - 0 1 0 1 5
0 0 0 0 0 1 - - - 0 1 0 0 4
0 0 0 0 0 0 1 - - 0 0 1 1 3
0 0 0 0 0 0 0 1 - 0 0 1 0 2
0 0 0 0 0 0 0 0 1 0 0 0 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0
Consequently, if Z = (D
0
; C
0
; B
0
; A
0
) represents a decimal digit z in BCD, we get
z =
(
i if (I
0
i
= 1 for some i > 0) and (I
0
j
= 0 for all j > i);
0 otherwise
which corresponds to a priority encoder function.
170 Solutions Manual - Introduction to Digital Design - March 22, 1999
Exercise 9.8: (a) From Figure 9.34 of the textbook we get the following table:
BCD 7-segment display
b
3
b
2
b
1
b
0
abcdefg
0000 0000001
0001 1001111
0010 0010010
0011 0000110
0100 1001100
0101 0100100
0110 0100000
0111 0001111
1000 0000000
1001 0001100
The implementation of this code converter using a decoder and OR gates is shown in Figure 9.7.
The implementation using a decoder and an encoder is not e�cient, and for this reason it is not
shown. Two 4-bit encoders or a large 7-bit encoder should be used, and since there is only a small
set of 7-segment codes, many of the encoder inputs would not be used, or would require OR gates
to combine two or more decoder outputs.
b0
b1
b2
b3
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
1
2
3
Binary
decoder
E
1
a
b
d
c
e
f
g
Figure 9.7: Network of Exercise 9.8 (a)
Solutions Manual - Introduction to Digital Design - March 22, 1999 171
(b) Four-bit binary to 4-bit Gray code. The function table is:
binary Gray
b
3
b
2
b
1
b
0
g
3
g
2
g
1
g
0
0000 0000
0001 0001
0010 0011
0011 0010
0100 0110
0101 0111
0110 0101
0111 0100
1000 1100
1001 1101
1010 1111
1011 1110
1100 1010
1101 1011
1110 1001
1111 1000
Although the implementation by a gate network is quite simple, we show two di�erent imple-
mentations in Figure 9.8. One uses a decoder and OR gates, and the other uses a decoder and
encoder.
b0
b1
b2
b3
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
1
2
3
Binary
decoder
E
1
g3
g2
g1
g0
b0
b1
b2
b3
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
1
2
3
Binary
decoder
E
1
g0
g1
g2
g3
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
1
2
3
Binary
encoder
E
1
Figure 9.8: Binary to Gray-code converter - Exercise 9.8 (b)
172 Solutions Manual - Introduction to Digital Design - March 22, 1999
(c) BCD to 2-out-of-5 code converter. The function table of the system follows:
BCD 2-out-of-5
b
3
b
2
b
1
b
0
c
4
c
3
c
2
c
1
c
0
0000 00011
0001 11000
0010 10100
0011 01100
0100 10010
0101 01010
0110 00110
0111 10001
1000 01001
1001 00101
Two implementations of this code converter, one using a decoder and OR gates, and another using
a decoder and encoder are shown in Figure 9.9.
b0
b1
b2
b3
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
1
2
3
Binary
decoder
E
1
c0
c1
c2
c3
c4
b0
b1
b2
b3
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
1
2
3
Binary
decoder
E
1
c0
c1
c2
c3
c4
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
0
1
2
3
4
Binary
encoder
E
1
0
Figure 9.9: Network of Exercise 9.8 (c)
Exercise 9.9: The implementation is shown in Figure 9.10, on page 173. The outputs of the
decoder are labeled according to the Gray code and connected to the corresponding inputs of the
encoder.
Exercise 9.10 A speci�cation of the cyclic priority encoder is
z = i if x
i
= 1 and x
(i+j)mod 8
= 0 for (j � (c� i) mod 8)
Solutions Manual - Introduction to Digital Design - March 22, 1999 173
Binary
decoder
Binary
Encoder
2
1
0
0
1
2
3
4
5
6
7E E
0
1
2
3
4
5
6
7
2
1
0
g2
g1
g0
b2
b1
b0
1 1
Figure 9.10: Code converter Binary-Gray, Exercise 9.9
where c is the value of the control input.
In one implementation, a left 7-shifter is used to move the highest-priority input (x
c
) to the
highest input of the priority encoder (w
7
). The amount of shift is therefore 7 � c to the left (this
is obtained by complementing each bit of the binary representation of c).
This produces w
(i+7�c)mod 8
= x
i
, so that if x
i
is the highest-priority input, the output of the
priority encoder would be (i+7� c) mod 8. Consequently, to obtain the correct result, the output
of the encoder y has to be decremented by (7� c) mod 8. That is,
z = (y � (7� c)) mod 8 = (y + c+ 1) mod 8
The corresponding network is shown in Figure 9.11(a). To avoid the complementation of c, we
can use a right shift of c insteadof the left shift. This would put x
c
in w
0
instead of w
7
. Therefore,
the connections between the output of the shifter and the input of the priority encoder have to be
as shown in the Figure 9.11(b).
x1
x2
x3
x4
x5
x6
x7
x0
x1
x2
x3
x4
x5
x6
x7
-7
-6
-5
-4
-3
-2
-1
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
Left
7-Shifter
2 1 0
+
c0
c1
c2
z0
z1
z2
A
cin
1
Priority
Encoder
0
1
2
3
4
5
6
7 A
0
1
2
E
1
w7
w0
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
0
1
2
3
4
5
6
7
Right
7-Shifter
2 1 0
Priority
Encoder
0
1
2
3
4
5
6
7 A
0
1
2
E
1
c2 c1 c0
x0
x1
x2
x3
x4
x5
x6
x7
x0
x1
x2
x3
x4
x5
x6
(a)
(b)
Figure 9.11: Cyclic priority encoder - Exercise 9.10
174 Solutions Manual - Introduction to Digital Design - March 22, 1999
Exercise 9.11
Input: x 2 f0; 1; 2; 3; 4; 5; 6; 7g, represented in binary by the vector x = fx
2
; x
1
; x
0
g; x
i
2 f0; 1g.
Output: y 2 f0; 1; 2; 3; 4; 5; 6; 7g, represented in binary by the vector y = fy
2
; y
1
; y
0
g; y
i
2 f0; 1g
Function: y = (3x) mod 8
The function table for the system is:
x 0 1 2 3 4 5 6 7
y 0 3 6 1 4 7 2 5
The implementation of this system using a binary decoder and a binary encoder is shown in
Figure 9.12.
Binary
Encoder
E
0
1
2
3
4
5
6
7
2
1
0
x2
x1
x0
y2
y1
y0
1
Binary
decoder
2
1
0
0
1
2
3
4
5
6
7E
1
Figure 9.12: Function y = 3x using decoder and encoder
Exercise 9.12 The 64-input encoder network in Figure 9.35 of the textbook consists of two
levels of modules. In the �rst level there are eight encoders, each of them encoding part of the
input vector x. Since there is only one input with value 1, the outputs of all encoder modules are 0
except the one corresponding to this x
i
= 1. Also, only the corresponding A has value 1. Naming
w
j
the value of the 3-bit output of the encoder that has inputs x
i
, 8k � i � 8k + 7, the output is
described as:
w
j
=
(
i mod 8 if x
i
= 1 for j = bi=8c
0 otherwise
and
A
j
=
(
1 if x
i
= 1 for j = bi=8c
0 otherwise
In the second level, there are three OR gates with eight inputs each which produce (y
2
; y
1
; y
0
) and
an eight-input encoder to encode the A outputs of the �rst level encoders and produce (y
5
; y
4
; y
3
).
The connection of the OR gates produces:
2
X
j=0
y
j
2
j
= OR(w
7
; w
6
; :::; w
0
) = i mod 8
Solutions Manual - Introduction to Digital Design - March 22, 1999 175
since all w's except one are 0.
Similarly, the output of the second-level encoder is
5
X
j=3
y
j
2
j
= bi=8c
and, therefore,
y =
5
X
j=0
y
j
2
j
= bi=8c � 2
3
+ i mod 8 = i
and the network performs the encoding function.
Exercise 9.13 The 256-input multiplexer has eight select inputs. Since each 4-input multiplexer
has two select inputs, the tree has four levels. The number of multiplexer in each level is:
�rst level:
256
4
= 64
second level:
64
4
= 16
third level:
16
4
= 4
fourth level:
4
4
= 1
(9:1)
A total of 85 multiplexers distributed in four levels are required to implement a 256-input
multiplexer.
Exercise 9.14
The exercise asks for a multiplexer tree with r levels, and 2
n
inputs in the last level, with
n = rk. That means, each multiplexer has k selection lines and 2
k
inputs. Figure 9.13 shows a
block diagram of the �rst and second level of the tree. We can see from the �gure that from one level
to the next, the number of inputs is multiplied by p = 2
k
(the number of inputs of each individual
multiplexer module). For r levels, the total number of inputs in the last level is p
r
= 2
rk
= 2
n
.
Level 1
p inputs
p inputs2
Level 2
Mux Mux Mux Mux
Figure 9.13: Two levels of multiplexer tree
The number of modules is:
r�1
X
j=0
p
j
= p
0
+ p
1
+ p
2
+ : : :+ p
r�1
=
p
r
� 1
p� 1
176 Solutions Manual - Introduction to Digital Design - March 22, 1999
Exercise 9.15
f(a; b; c; d) = oneset(1; 3; 4; 9; 14; 15)
abcd f(a; b; c; d)
0 0000 0
1 0001 1
2 0010 0
3 0011 1
4 0100 1
5 0101 0
6 0110 0
7 0111 0
8 1000 0
9 1001 1
10 1010 0
11 1011 0
12 1100 0
13 1101 0
14 1110 1
15 1111 1
(a) the implementation using 8-input multiplexer is presented in Figure 9.14. The expression
can be manipulated as follows:
f(a; b; c; d) = a
0
b
0
c
0
d+ a
0
b
0
cd+ a
0
bc
0
d
0
+ ab
0
c
0
d+ abcd
0
+ abcd
f(a; b; c; d) = m
0
(a; b; c)d +m
1
(a; b; c)d +m
2
(a; b; c)d
0
+m
4
(a; b; c)d +m
7
(a; b; c)(d
0
+ d)
0
1
2
3
4
5
6
7
2 1 0
MUX
a b c
f(a,b,c,d)
d
d
d’
0
d
0
0
1
Figure 9.14: Implementation for Exercise 9.15 (a)
Solutions Manual - Introduction to Digital Design - March 22, 1999 177
(b) the implementation using 4-input multiplexer is presented in Figure 9.15. The expression
for this implementation is:
f(a; b; c; d) = m
0
(a; b)(c
0
d+ cd) +m
1
(a; b)c
0
d
0
+m
2
(a; b)c
0
d+m
3
(a; b)(cd + cd
0
)
f(a; b; c; d) = m
0
(a; b)d+m
1
(a; b)(c + d)
0
+m
2
(a; b)(c + d
0
)
0
+m
3
(a; b)c
MUX
0
1
2
3
1 0
f(a,b,c,d)
c
d
d
c
a b
d
Figure 9.15: Network for Exercise 9.15 (b)
Exercise 9.16 The implementation of an 8-input multiplexer using a 3-input binary decoder
and NAND gates is shown in Figure 9.16. The selection lines s = (s
2
; s
1
; s
0
) are decoded and used
to make z = i
j
, such that j = s = s
2
:2
2
+ s
1
:2 + s
0
.
Binary
decoder
2
1
0
0
1
2
3
4
5
6
7E
1
s2
s1
s0
i0
i1
i2
i3
i4
i5
i6
i7
z
Figure 9.16: Network for Exercise 9.16
178 Solutions Manual - Introduction to Digital Design - March 22, 1999
Exercise 9.17
Part (a) The speci�cation of an n�bit simple shifter is given on page 265 of the textbook. A
description of an 8-bit shifter is easily obtained from there. The block diagram of the circuit is
shown in Figure 9.17.
x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 x 0 x -1
SHIFTER
shift/no shift
left/right
E
y 7 y 6 y 5 y 4 y 3 y 2 y 1 y 0
s
d
Figure 9.17: Block diagram of 8-bits shifter
To generate each output, a 4-input multiplexer is used as shown in Figure 9.18. The selection
inputs are de�ned according to following table:
c
1
c
0
Operation s d E
00 LEFT shift L 1
01 RIGHT shift R 1
10 NO SHIFT no shift - 1
11 DISABLED - - 0
Considering shift = L = 1 and no shift = R = 0 (same convention used in page 266 of the
textbook) we obtain the following Kmaps:
MUX
0
1
2
3
1 0
c1 c0
x
i-1
x
i
x
i+1
0
iy
Figure 9.18: Circuit for each output of the 8-bit simple shifter
c
1
1 1 1 1
1 0 0 1
E
d
s
�
�
�
�
�
�
	
c
0
1 0 0 1
1 0 1 1
E
d
s
�
�
�
�
�
�
	
Solutions Manual - Introduction to Digital Design - March 22, 1999 179
that correspond to the following expressions:
c
1
= E
0
+ s
0
c
0
= sd+E
0
Part (b) An 8-bit bidirectional 3-shifter is speci�ed as:
Inputs:
x = (x
10
; x
9
; x
8
; x
7
; : : : ; x
0
; x
�1; x
�2
; x
�3
), with x
i
2 f0; 1g.
s 2 f0; 1; 2; 3g
d 2 fL;Rg
E 2 f0; 1g
Output: y = (y
7
; y
6
; : : : ; y
1
; y
0
), with y
j
2 f0; 1g.
Function:
y
i
=
8
>
<
>
:
x
i�s
if (d = L) and (E = 1)
x
i+s
if (d = R) and (E = 1)
0 otherwise
(9:2)
Let us assume that L = 1 and R = 0. Each output is generated by an 8-input multiplexer as
shown in Figure 9.19. The table for the control inputs c
2
c
1
c
0
is:
0
1
2
3
4
5
6
7
2 1 0
MUX
c2 c1 c0
x
i-3
x
i-2
x
i-1
x
i
x
i+1
x
i+2
x
i+3
0
 y
i
Figure 9.19: Circuit for each output of the 8-bit bidirectional shifter
Eds 000 001 002 003 010 011 012 013 100 101 102 103 110 111 112 113
c
2
c
1
c
0
111 111 111 111 111 111 111 111 011 100 101 110 011 010 001 000
The values on the table are mapped into the following Kmaps, considering that s is represented
in binary code:
180 Solutions Manual - Introduction to Digital Design - March 22, 1999
c
2
1 1 1 1
1 1 1 1
0 0 0 0
0 1 1 1
s
0
s
1
d
E
�
�
�
�
��
��
��
��
c
1
1 1 1 1
1 1 1 1
1 1 0 0
1 0 1 0
s
0
s
1
d
E
�
�
�
�
�
�
�
�
�
�
	
��
	
c
0
1 1 1 1
1 1 1 1
1 0 0 1
1 0 0 1
s
0
s
1
d
E
�
�
�
�
�
�
�
�
The switching expressions are:
c
2
= E
0
+ s
1
d
0
+ s
0
d
0
c
1
= E
0
+ ds
0
1
+Es
1
s
0
+ s
0
1
s
0
0
c
0
= E
0
+ s
0
0
Exercise 9.18 The module is obtained by renaming inputs and outputs of the shift register.
For the right 3-shifter we have the speci�cation:
Inputs:
x = (x
n+2
; x
n+1
; x
n
; x
n�1
; : : : ; x
1
; x
0
), with x
i
2 f0; 1g
s 2 f0; 1; 2; 3g
E 2 f0; 1g
Output: y = (y
n�1
; y
n�2
; : : : ; y
1
; y
0
), y
i
2 f0; 1g
Function:
y
j
=
(
x
j+s
if E = 1
0 otherwise
(9:3)
And we would like to have a left 3-shifter, which is speci�ed as:
Inputs:
w = (w
n�1
; w
n�2
; : : : ; w
1
; w
0
; w
�1
; w
�2
; w
�3
), with w
i
2 f0; 1g
s 2 f0; 1; 2; 3g
E 2 f0; 1g
Output: z = (z
n�1
; z
n�2
; : : : ; z
1
; z
0
), z
i
2 f0; 1g
Function:
z
i
=
(
w
i�s
if E = 1
0 otherwise
(9:4)
The mapping of the inputs is
x
i
= w
k
with k = n� 1� i. Renaming the output also, we have
y
j
= z
t
with t = n� 1� j. Replacing these values on Equation 9.3 we obtain:
z
t
=
(
x
n�1�t+s
= w
n�1�(n�1�t+s)
= w
t�s
if E = 1
0 otherwise
(9:5)
Solutions Manual - Introduction to Digital Design - March 22, 1999 181
that corresponds to a 3-left shifter.
Exercise 9.19 A n-bit p-shifter has (n+2p) input bits and n output bits. It can shift right or
left (direction input d) and the distance of shifting can vary from 0 to p.
The implementation of a 32-bit 3-shifter using four 8-bit 3-shifters is presented in Figure 9.20.
The circuit on the top is a 32-bit 3-shifter that shifts to the left only. The circuit on the bottom of
the �gure is a bi-directional 32-bit 3-shifter. The input of the circuit was named i
31
to i
0
, and the
output z
31
to z
0
.
10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3
8-bit 3-shifter
d
s
3
8-bit 3-shifter
d
s
3
8-bit 3-shifter
d
s
3
8-bit 3-shifter
d
s
3
LEFT
shift inputs
i 7 to i 0i15to i 8i23to i16i31to i24
z31to z24 z23to z16
z15to z8 z 7to z0
distance
from 0 to 3
LEFT 32-bit 3-shifter
8-bit 3-shifter
d
s
3
8-bit 3-shifter
d
s
3
8-bit 3-shifter
d
s
3
8-bit 3-shifter
d
s
3
LEFT/RIGHT
shift inputs
i 7 to i 0i15to i 8i23to i16i31to i24
z31to z24 z23to z16
z15to z8 z 7to z0
distance
from 0 to 3
Bi-directional 32-bit 3-shifter
shift inputs
10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3
10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 10 9 8 7 6 5 4 3 2 1 0 -1 -2 -310 9 8 7 6 5 4 3 2 1 0 -1 -2 -310 9 8 7 6 5 4 3 2 1 0 -1 -2 -3
Figure 9.20: Exercise 9.19
Exercise 9.20 Calling the output of stage 1 w1 and of stage 2 w2 then:
w1
j
=
(
x
j
if s
0
= 0
x
(j+1)mod8
if s
0
= 1
which indicates that this stage rotates 0 or 1 position left depending on the value of s
0
.
Similarly,
w2
j
=
(
w1
j
if s
1
= 0
w1
(j+2)mod8
if s
1
= 1
Finally,
182 Solutions Manual - Introduction to Digital Design - March 22, 1999
y
j
=
(
w2
j
if s
2
= 0
w2
(j+4)mod8
if s
2
= 1
and this corresponds to rotating 0 or 4 positions.
Consequently, the module rotates left s = 4s
2
+2s
1
+ s
0
positions with 0 � s � 7. For example,
if the input vector is (x
7
; x
6
; :::; x
0
) = 11010110 the output vector, for a rotation of 2 to the left is:
01011011.
Exercise 9.21 Design of
Part (a) 12-bit right 3-shifter using 4-bit right shifter modules. The network is shown in Figure
9.21.
right 3-shifterdist E
6 5 4 3 2 1 0
3 2 1 0
right 3-shifterdist E
6 5 4 3 2 1 0
3 2 1 0
right 3-shifterdist E
6 5 4 3 2 1 0
3 2 1 0
x11 x10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 x 0x14 x13 x12
d
E
Figure 9.21: 12-bit right 3-shifter
Part (b) using k-bit right p-shifter modules we may implement a larger n-bit right p-shifter
using:
M = d
n
k
e
modules of k-bit right p-shifter. The input vector of the n-bit shifter is:
x = (x
n+p�1
; x
n+p�2
; :::; x
n�1
; x
n�2
; :::; x
1
; x
0
)
Each k-bit shifter module i receives the vector:
x
(i)
= (x
ik+p�1
; :::; x
ik+1
; x
ik
)
The enable and distance control lines of all shifters are connected together to from the control
lines of the larger shifter.
Exercise 9.22
Considering the network formed by the decoder and the multiplexer we have that
z =
(
1 if (w; d; e) = (f; g; h)
0 otherwise
(9:6)
where w is the output of the �rst multiplexer. An expression for this output is:
w = a
0
b
0
c+ bc
0
+ abc = ab+ bc
0
+ a
0
b
0
c
Solutions Manual - Introduction to Digital Design - March 22, 1999 183
a
b
b
c’
a’
b’
c
w
f
d
g
e
h
z
Figure 9.22: Network for Exercise 9.22
The gate network that implements the network in Figure 9.38 of the textbook is shown in Figure
9.22. The equality comparator that generates z is implemented using XOR and NOR gates (as
proposed in the hint). The gate network to generate w is implemented with AND and OR gates.
Exercise 9.23 The network in Figure 9.39 of the textbook has a serial line (w) between the
MUX and DEMUX that is described as:
w =
(
x
i
if i = 4a+ 2b+ c and E
1
= 1
0 otherwise
(9:7)
The outputs of the DEMUX are speci�ed as:
y
i
=
(
w if i = 4a+ 2b+ c and E
2
= 1
0 otherwise
(9:8)
Combining both equations we obtain:
y
i
=
(
x
i
if i = 4a+ 2b+ c and E
1
= E
2
= 1
0 otherwise
(9:9)
So, y
i
is the same as x
i
or is zero. This circuit is useful to allow the sharing of the single line
between Mux and Demux among all pairs of (input,output): (x
0
; y
0
), (x
1
; y
1
) ...and so on. It's
used in communication lines to divide the full capacity of the communication line among the many
transmitters and receivers. Each pair can communicate without interference of the other pairs.
Exercise 9.24
From the network we obtain:
Y
0
= x
0
y
0
1
S
0
1
+ x
0
y
1
S
1
+ xy
0
1
S
3
+ xy
1
(S
2
+ S
0
)
= x
0
y
0
1
(y
0
2
y
0
)
0
+ x
0
y
1
y
0
2
y
0
+ xy
0
1
y
2
y
0
+ xy
1
(y
2
y
0
0
+ y
0
2
y
0
0
)
= x
0
y
0
1
y
2
+ x
0
y
0
1
y
0
0
+ x
0
y
1
y
0
2
y
0
+ xy
0
1
y
2
y
0
+ xy
1
y
0
0
Y
1
= x
0
y
0
1
(S
3
+ S
0
) + x
0
y
1
(S
2
+ S
0
) + xy
0
1
S
0
+ xy
1
(S
3
+ S
2
)
= x
0
y
0
1
(y
2
y
0
+ y
0
2
y
0
0
) + x
0
y
1
(y
2
y
0
0
+ y
0
2
y
0
0
) + xy
0
1
y
0
2
y
0
0
+ xy
1
(y
2
y
0
+ y
2
y
0
0
)
= x
0
y
0
1
y
2
y
0
+ x
0
y
0
1
y
0
2
y
0
0
+ x
0
y
1
y
0
0
+ xy
0
1
y
0
2
y
0
0
+ xy
1
y
2
184 Solutions Manual - Introduction to Digital Design - March 22, 1999
Y
2
= x
0
y
0
1
(S
0
+ S
1
) + x
0
y
1
S
1
+ xy
0
1
S
0
+ xy
1
(S
1
+ S
0
)
= x
0
y
0
1
(y
0
2
y
0
0
+ y
0
2
y
0
) + x
0
y
1
y
0
2
y
0
+ xy
0
1
y
0
2
y
0
0
+ xy
1
(y
0
2
y
0
0
+ y
0
2
y
0
)
= x
0
y
0
1
y
0
2
+ x
0
y
1
y
0
2
y
0
+ xy
0
1
y
0
2
y
0
0
+ xy
1
y
0
2
z = (y
2
� y
0
)y
0
1
x = (y
0
2
y
0
+ y
2
y
0
0
)y
0
1
x = x(y
0
2
y
0
1
y
0
+ y
2
y
0
1
y
0
0
)
From these expressions we following state transition and output table:
State PS Input
Number y
2
y
1
y
0
x = 0 x = 1
0 000 111,0 110,0
1 001 100,0 000,1
2 010 010,0 101,0
3 011 101,0 100,0
4 100 001,0 000,1
5 101 011,0 001,0
6 110 010,0 011,0
7 111 000,0 010,0
NS (Y
2
Y
1
Y
0
),z
To reduce the number of states we use the minimization procedure presented in Section 7.6 of the
textbook. The �rst partition is:
#1 #2
x 1 4 0 2 3 5 6 7
0 1 1 2 2 2 2 2 2
1 2 2 2 2 1 1 2 2
Second partition:
#1 #2 #3
x 1 4 0 2 6 7 3 5
0 1 1 2 2 2 2 3 3
1 2 2 2 3 3 2 1 1
Third partition:
#1 #2 #3 #4
x 1 4 0 7 2 6 3 5
0 1 1 2 2 3 3 4 4
1 2 2 3 3 4 4 1 1
No more new partitions! Stop. The reduced sequential system has only 4 states. We rename the
states as:
Sate number State name
1,4 A
0,7 B
2,6 C
3,5 D
and obtain the following state transition and output table:
Solutions Manual - Introduction to Digital Design - March 22, 1999 185
PS Input
x = 0 x = 1
A A,0 B,1
B B,0 C,0
C C,0 D,0
D D,0 A,0
NS,z
A state diagram for the system is shown in Figure 9.23 and corresponds to a modulo-4 counter.
A B
CD
0/0 0/0
0/00/0
1/1
1/0
1/0
1/0
Figure 9.23: State digram for Exercise 9.24
A better canonical implementation of this sequential circuit is shown in Figure 9.24 and it uses
only two memory elements and some gates. The design steps are not shown.
y0
y1
Y0
Y1
x x z
Figure 9.24: Redesign of sequential system in Exercise 9.24
Exercise 9.25 From the circuit presented in the �gure we can obtain the state diagram in
Figure 9.25. The binary decoder connected to the state register generates the signals S
i
, which is 1
when the sequential system is at state i. The system outputs correspond to the state signals, that
means, each output is active in one particular state. For this reason we used the output names as
186 Solutions Manual - Introduction to Digital Design - March 22, 1999
state names to make the state diagram more meaningful. In each present state we identify which
input of the binary encoder is 1. This input determines the next state. For example, the origin
of arcs going into state S
1
(check) are obtained by considering the input of the Binary Encoder
labeled 1, which is S
0
for input GO, S
2
(always, no condition), and S
3
(always).
The state diagram shows the operation of a controller which starts to operate with a GO signal.
During operation it monitors two variables: dist and count and issues movement control signals
and counter control signals, until (dist � 10) and (count = 3).
CLEAR
COUNT check turn
left
count
up
movestop
Initial
GO’
GO
dist > 10
(dist � 10) and
(count = 3)
(dist � 10) and
(count 6= 3)
Figure 9.25: Exercise 9.25
Exercise 9.26. The codewords of both systems are presented in the following table:
n Code A Code B
p = (3n) mod 16 q = (7n) mod 16
p
2
p
1
p
0
q
2
q
1
q
0
0 0000 0000
1 0011 0111
2 0110 1110
3 1001 0101
4 1100 1100
5 1111 0011
6 0010 1010
7 0101 0001
8 1000 1000
9 1011 1111
10 1110 0110
11 0001 1101
12 0100 0100
13 0111 1011
14 1010 0010
15 1101 1001
Solutions Manual - Introduction to Digital Design - March 22, 1999 187
(a) the design of an A-to-B converter using one 8-input multiplexer and one 2-input XOR gate
is shown in Figure 9.26. Observe that:
q
0
= p
0
q
1
= p
1
q
2
= p
2
� p
0
and q
3
is easily implemented using an 8-input multiplexer from the following function table:
p
3
p
2
p
1
p
0
q
3
0000 0
0001 1
0010 1
0011 0
0100 0
0101 0
0110 1
0111 1
1000 1
1001 0
1010 0
1011 1
1100 1
1101 1
1110 0
1111 0
0
1
2
3
4
5
6
7 2 1 0
MUX
p3 p2 p1
q0
q1
q2p2
p0
p1
0
1
1
0
q3
Figure 9.26: Code converter - Exercise 9.26 (a)
(b) the code converter designed using one 4-input decoder and one 16-input encoder is shown
in Figure 9.27.
188 Solutions Manual - Introduction to Digital Design - March 22, 1999
p0
p1
p2
p3
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
1
2
3
Binary
decoder
E
1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
1
2
3
Binary
encoder
E
1
q0
q1
q2
q3
Figure 9.27: Code converter - Exercise 9.26 (b)