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

Prévia do material em texto

85
Chapter 6
Exercise 6.1 From Exercise 5.11, we know that the single-error detector for a 2-out-of-5 code
(a; b; c; d; e) is implemented by the expression:
E(a; b; c; d; e) = abc+ abd+ acd+ bcd+ abe+ ace+ ade+ bce+ bde+ cde+ a
0
b
0
c
0
e
0
+ a
0
b
0
d
0
e
0
+
a
0
c
0
d
0
e
0
+ b
0
c
0
d
0
e
0
Using only gates from Table 4.1 of the textbook we can generate all product terms but the
OR operation of all 14 product terms must be implemented by a tree of gates. To minimize the
delay in the implementation, we should use NAND gates. The generation of the product terms is
done using 3 and 4-input NAND gates from Table 4.1. A 14-input NAND however is not available
and should be obtained combining smaller gates. The large NAND gate may be decomposed into
smaller ones as follows (for a 4-input NAND to 2-input NANDs):
(abcd)
0
= (ab)
0
+ (cd)
0
The possibilities are:
Network Delay
t
pLH
t
pHL
A - First Level: 1 NAND-6, 1 NAND-8, Second Level: 1 OR-2 0.40+0.037L 0.64+0.019L
B - First Level: 1 NAND-4, 2 NAND-5, Second Level: 1 OR-3 0.37+0.038L 0.70+0.022L
C - First Level: 2 NAND-3, 2 NAND-4, Second Level: 1 OR-4 0.27+0.038L 0.62+0.025L
Even though the LH transition delay of network C is less than the one for network A, the HL
transition delay of network C becomes worse when the output load is greater or equal to 3. For this
reason we consider network A as the implementation of the 14-input NAND, since it is going to be
less susceptible to output load values. The resulting circuit is presented in Figure 6.1, on page 86.
The delay of the network is obtained from the critical paths NAND-4 ! NAND-6 ! OR-2 or
NAND-3 ! NAND-8 ! OR-2:
T
pLH
(net) = max(t
pHL
(NAND-4) + t
pLH
(NAND-6) + t
pLH
(OR-2);
t
pHL
(NAND-3) + t
pLH
(NAND-8) + t
pLH
(OR-2))
= max(0:12 + 0:051 � 1 + 0:24 + 0:037 � 1 + 0:12 + 0:037 � L;
0:09 + 0:039 + 0:24 + 0:038 + 0:12 + 0:039L)
= max(0:57 + 0:037L; 0:53 + 0:037L) = 0:57 + 0:037L
T
pHL
(net) = max(t
pLH
(NAND-4) + t
pHL
(NAND-6) + t
pHL
(OR-2);
t
pLH
(NAND-3) + t
pHL
(NAND-8) + t
pHL
(OR-2))
= max(0:10 + 0:037 � 1 + 0:36 + 0:019 � 1 + 0:20 + 0:019 � L;
0:07 + 0:038 + 0:42 + 0:019 + 0:2 + 0:019L)
= max(0:72 + 0:019 � L; 0:75 + 0:019L) = 0:75 + 0:019L
86 Solutions Manual - Introduction to Digital Design - February 2, 1999
f(a,b,c,d,e)
b’
c’
a
b
c
a
b
d’
d
b
a
c
d
c
d
b
a
e’
e
a
c
e
a
d
e
b
c
e
b
d
e
c
d
e
a’
b’
c’
e’
a’
b’
d’
e’
a’
c’
d’
e’
Figure 6.1: Single-error detector for 2-out-of-5 code
Exercise 6.2 Let us use the expressions obtained in Exercise 5.12 (only output variables' names
were changed):
s
0
= x
0
y
0
c
in
+ x
0
0
y
0
0
c
in
+ x
0
y
0
0
c
0
in
+ x
0
0
y
0
c
0
in
s
1
= x
0
1
x
0
y
0
1
c
in
+ x
0
1
y
0
1
y
0
c
in
+ x
0
x
0
1
y
0
1
y
0
+ x
1
x
0
y
1
c
in
+ x
1
y
1
y
0
c
in
+ x
1
x
0
y
1
y
0
+ x
0
1
x
0
0
y
1
c
0
in
+ x
0
1
y
1
y
0
0
c
0
in
+ x
0
1
x
0
0
y
1
y
0
0
+ x
1
y
0
1
y
0
0
c
0
in
+ x
1
x
0
0
y
0
1
c
0
in
+ x
1
x
0
0
y
0
1
y
0
0
c
out
= x
1
y
1
+ x
1
x
0
y
0
+ x
0
y
1
y
0
+ y
1
y
0
c
in
+ x
0
y
1
c
in
+ x
1
x
0
c
in
+ x
1
y
0
c
in
The objective of the design is to reduce the number of gates sharing subnetworks among the
outputs, the manipulation of these expressions follows:
Solutions Manual - Introduction to Digital Design - February 2, 1999 87
s
0
= (x
0
y
0
+ x
0
0
y
0
0
)c
in
+ (x
0
y
0
0
+ x
0
0
y
0
)c
0
in
= (x
0
� y
0
)
0
c
in
+ (x
0
� y
0
)c
0
in
= (x
0
� y
0
)� c
in
s
1
= x
0
1
(x
0
y
0
1
c
in
+ y
0
1
y
0
c
in
+ x
0
y
0
1
y
0
+ x
0
0
y
1
c
0
in
+ y
1
y
0
0
c
0
in
+ x
0
0
y
1
y
0
0
)
+x
1
(x
0
y
1
c
in
+ y
1
y
0
c
in
+ x
0
y
1
y
0
+ y
0
1
y
0
0
c
0
in
+ x
0
0
y
0
1
c
0
in
+ x
0
0
y
0
1
y
0
0
)
= x
0
1
(y
0
1
A+ y
1
B) + x
1
(y
1
A+ y
0
1
B)
= (x
0
1
y
0
1
+ x
1
y
1
)A+ (x
0
1
y
1
+ x
1
y
0
1
)B = (x
1
� y
1
)
0
A+ (x
1
� y
1
)B
where A = x
0
c
in
+ y
0
c
in
+ x
0
y
0
and B = x
0
0
c
0
in
+ y
0
0
c
0
in
+ x
0
0
y
0
0
. It can be shown that B = A
0
, and
the expressions for s
1
becomes:
s
1
= x
1
� y
1
�A
For the c
out
output we obtain:
c
out
= x
1
y
1
+ x
1
A+ y
1
A
= x
1
(y
1
+A) + y
1
(x
1
+A)
= x
1
(y
1
+ y
0
1
A) + y
1
(x
1
+ x
0
1
A)
= x
1
y
1
+ x
1
y
0
1
A+ x
0
1
y
1
A
= x
1
y
1
+ (x
1
y
0
1
+ x
0
1
y
1
)A = x
1
y
1
+ (x
1
� y
1
)A
The expression for A can also be transformed to the following more convenient form:
A = x
0
c
in
+ y
0
c
in
+ x
0
y
0
= x
0
(c
in
+ y
0
) + y
0
(c
in
+ x
0
)
= x
0
(c
in
y
0
0
+ y
0
) + y
0
(c
in
x
0
0
+ x
0
)
= x
0
c
in
y
0
0
+ x
0
y
0
+ y
0
c
in
x
0
0
= (x
0
� y
0
)c
in
+ x
0
y
0
The gate network is shown in Figure 6.2 on page 88.
Exercise 6.3 A high-level speci�cation for this system is:
Input: x is a decimal digit represented in BCD.
Output: two BCD digits y and z.
Function: 10y + z = 3x.
From this speci�cation we de�ne the following switching functions:
x
3
x
2
x
1
x
0
y
3
y
2
y
1
y
0
z
3
z
2
z
1
z
0
0000 0000 0000
0001 0000 0011
0010 0000 0110
0011 0000 1001
0100 0001 0010
0101 0001 0101
0110 0001 1000
0111 0010 0001
1000 0010 0100
1001 0010 0111
88 Solutions Manual - Introduction to Digital Design - February 2, 1999
x0
y0
cin
s0
A
x1
y1
s1
cout
Figure 6.2: Network of Exercise 6.2
The simpli�ed switching expressions are obtained from K-maps (not shown):
y
3
= y
2
= 0
y
1
= x
3
+ x
2
x
1
x
0
y
0
= x
2
x
0
1
+ x
2
x
0
0
z
3
= x
2
x
1
x
0
0
+ x
0
2
x
1
x
0
z
2
= x
3
+ x
2
x
0
1
x
0
+ x
0
2
x
1
x
0
0
z
1
= x
2
x
0
1
x
0
0
+ x
0
2
x
0
1
x
0
+ x
0
2
x
1
x
0
0
z
0
= x
0
The (NAND;NAND) network is shown in Figure 6.3.
Exercise 6.4 A high-level speci�cation for the system is:
Input: A, B,both decimal digits in Excess-3 code.
Output: Y 2 fG;E; Sg
Function:
Y =
8
>
<
>
:
G if A > B
E if A = B
S otherwise
The inputs are represented as A = (a
3
; a
2
; a
1
; a
0
) and B = (b
3
; b
2
; b
1
; b
0
).
The output is encoded as:
Y = (y
1
; y
0
) =
8
>
<
>
:
(0; 0) if A < B
(0; 1) if A = B
(1; 0) if A > B
The network could be designed speci�cally for the Excess-3 code, in which case it would make
use of the corresponding don't cares, or one can use a 4-bit binary comparator. The �rst approach
might give a simpler network, but it is di�cult to design because the simpli�cations would require
K-maps of eight variables (or the use of some tabular minimization technique). Moreover, the
Solutions Manual - Introduction to Digital Design - February 2, 1999 89
x3’
x2
x1
x0
y1
x2
x1’
x0’
x2’
x1’
x0
x2’
x1
x0’
z1
0 y3
0 y2
x2
x1’
x2
x0’
y0
x2
x1
x0’
x2’
x1
x0
z3
x2
x1’
x0
x2’
x1
x0’
z2
x3’
z0
x0
Figure 6.3: Network of Exercise 6.3
reduction would be only valid for a two-level network, which is quite complex anyhow (because of
the eight input variables). Consequently, we design a 4-bit binary comparator. It is an extension
to four bits of the 2-bit comparator described in the textbook. Therefore, we can write directly the
following switching expressions:
Equal = w
3
w
2
w
1
w
0
Greater = a
3
b
0
3
+ w
3
a
2
b
0
2
+ w
3
w
2
a
1
b
0
1
+ w
3
w
2
w
1
a
0
b
0
0
where w
i
= a
i
b
i
+ a
0
i
b
0
i
Due to the code selected, the outputs are
y
1
= Greater
and
y
0
= Equal
The network is shown in Figure 6.4.
Exercise 6.5: The modi�cation of the network of Example 4.6 is shown in Figure 6.5. Since
we are asked to use 4 complex gates 2-AND/NOR2, the best solution is to use them on the level
that has y
i
and w
i
as inputs. The fourth one should not be used to generate z
2
since this output
is composed of 3 products and the complex gate is able to handle only 2. More logic is required
to generate the third product and combine it with the output of the complex gate (that would
90 Solutions Manual - Introduction to Digital Design - February 2, 1999
W
w3
a3
b3
W
a2
b2
w2
W
a1
b1
w1
W
a0
b0
w0
w3
w2
w1
w0
y0
a3
b3’
w3
a2
b2’
w3
w2
a1
b1’
w3
w2
w1
a0
b0’
y1
Figure 6.4: Network of Exercise 6.4
take care of 2 products). For this reason, it is more interesting to use the fourth complex gate
to generate z
1
and keep the same structure of gates that was used in Example 4.6 to generate z
2
.
Although the output of AN3 corresponds to z
0
we didn't use its output as the network output to
avoid the in
uence of the z
0
output load on the delay of the other outputs.
The network characteristics are:
� Load factor: 1
� Fanout factor: considering F = 12 we have F (z
2
) = F (z
1
) = F (z
0
) = 12
� Network size: The NOT gates have size 1 and all others have size 2, thus the network has 23
equivalent gates. The size of the network on Example 4.6 was 38 equivalent gates.
� Number of levels: 6
� Network delays: consider the following table for gate delays:
gate Identi�er Output Load t
pLH
(ns) t
pHL
(ns)
OR3 O1 4 0.27 0.43
NOT N1/N4 3 0.13 0.10
2-AND/NOR2 AN2/AN3 3 0.40 0.18
2-AND/NOR2 AN4 1 0.25 0.13
2-AND/NOR2 AN1 2 0.32 0.16
NOT N2/N3 2 0.10 0.08
NOT N5 L
1
0:02 + 0:038L
1
0:05 + 0:017L
1
AND3 A3 1 0.24 0.20
OR3 O2 L
2
0:12 + 0:038L
2
0:34 + 0:022L
2
The �rst critical path we may consider is O1! N1! AN1! N2! A3! O2 that results
in the following delays:
T
pLH
(x
1
; z
2
) = t
pHL
(O1) + t
pLH
(N1) + t
pHL
(AN1) + t
pLH
(N2) + t
pLH
(A3) + t
pLH
(O2)
Solutions Manual - Introduction to Digital Design - February 2, 1999 91
2-AND/NOR2
ANx
y2 w2 y1 w1 y0 w0
AN1 AN2 AN3
AN4
O1
N1
N2 N3 N4
N5
N6A1 A2 A3
O2
z2
z1
z0
x0
x1
x2
Figure 6.5: Network for Exercise 6.5
= 0:428 + 0:134 + 0:156 + 0:096 + 0:24 + 0:12 + 0:038L
2
= 1:17 + 0:038L
2
T
pHL
(x
1
; z
2
) = t
pLH
(O1) + t
pHL
(N1) + t
pLH
(AN1) + t
pHL
(N2) + t
pHL
(A3) + t
pHL
(O2)
= 0:272 + 0:101 + 0:32 + 0:084 + 0:2 + 0:34 + 0:022L
2
= 1:32 + 0:022L
2
Another path that may be considered is O1 ! N1 ! AN2 ! N3 ! AN4 ! N5, that
results in the following delays:
T
pLH
(x
1
; z
1
) = t
pHL
(O1) + t
pLH
(N1) + t
pHL
(AN2) + t
pLH
(N3) + t
pHL
(A4) + t
pLH
(N5)
= 0:428 + 0:134 + 0:184 + 0:096 + 0:128 + 0:02 + 0:038L
1
= 0:99 + 0:038L
1
T
pHL
(x
1
; z
1
) = t
pLH
(O1) + t
pHL
(N1) + t
pLH
(AN2) + t
pHL
(N3) + t
pLH
(A4) + t
pHL
(N5)
= 0:272 + 0:101 + 0:395 + 0:084 + 0:245 + 0:05 + 0:017L
1
= 1:15 + 0:017L
1
We can see that the path from x
1
to z
2
is still the critical path in this circuit, however, the
delay was reduced when compared to Example 4.6.
Exercise 6.6: A high-level speci�cation for the system is:
Input: x; y 2 f0; 1; 2; 3g
Output: z 2 fG;E; Sg.
Function:
z =
8
>
<
>
:
G if x > y
E if x = y
S if x < y
We encode the output as follows:
92 Solutions Manual - Introduction to Digital Design - February 2, 1999
z z
2
z
1
z
0
G 1 0 0
E 0 1 0
S 0 0 1
From this encoding we write:
z
2
= G = x
1
y
0
1
+ SAME(x
1
; y
1
)x
0
y
0
0
z
1
= E = SAME(x
1
; y
1
)SAME(x
0
; y
0
)
z
0
= S = x
0
1
y
1
+ SAME(x
1
; y
1
)x
0
0
y
0
where SAME(x; y) = xy+x
0
y
0
= (x� y
0
). Since xy
0
, x
0
y and SAME(x; y) are mutually exclusive,
the OR operation may be written as an Exclusive-OR operation, as follows:
z
2
= G = x
1
y
0
1
� (x
1
� y
0
1
)x
0
y
0
0
z
1
= E = (x
1
� y
0
1
)(x
0
� y
0
0
)
z
0
= S = x
0
1
y
1
� (x
1
� y
0
1
)x
0
0
y
0
The NOT gate is implemented using a XOR gate as: x
0
= x � 1. Thus, we can transform the
above expressions as follows:
z
2
= G = x
1
(y
1
� 1)� (x
1
� y
1
� 1)x
0
(y
0
� 1)
z
1
= E = (x
1
� y
1
� 1)(x
0
� y
0
� 1)
z
0
= S = (x
1
� 1)y
1
� (x
1
� y
1
� 1)(x
0
� 1)y
0
The gate network is shown in Figure 6.6
1
y1 y1’
1
y0 y0’
1
x1 x1’
1
x0 x0’
x1
x0
z2=G
z1=E
z0=S
y1
y0
x1
x0
Figure 6.6: Network for Exercise 6.6
Solutions Manual - Introduction to Digital Design - February 2, 1999 93
Exercise 6.7 Using XOR gates it's possible to get the expressions for equality or di�erence:
SAME = x
0
� y
DIFFERENT = x� y
Using these expressions, we obtain the expression for each output, z
2
(GREATER), z
1
(EQUAL)
and z
0
(LESS) as:
z
2
= DIFFERENT:x+ SAME:c
2
z
1
= SAME:c
1
z
0
= DIFFERENT:y + SAME:c
0
The gate network using XOR and NAND gates is shown in Figure 6.7, on page 93.
x’
y
SAME
z1
c1
x
y
DIFFERENT
c2
x
z2
z0
c0
y
Figure 6.7: Comparator using XOR and NAND gates
Exercise 6.8 The complementer is describedby the expressions:
z
i
= x
i
� c
The network that implements a 4-bit complementer using only XOR gates is presented in
Figure 6.8, on page 94.
Exercise 6.9 The MUX function is de�ned as:
MUX(x; y; s) = xs+ ys
0
and using this function we want to represent the following functions using muxes:
� OR(a; b) = a+ b = ab
0
+ b = MUX(a; 1; b
0
)
� NOR(a; b) = (a+ b)
0
= a
0
b
0
= 0:b+ a
0
b
0
= MUX(0; a
0
; b)
94 Solutions Manual - Introduction to Digital Design - February 2, 1999
c
xo
x1
x2
x3
z0
z1
z2
z3
Figure 6.8: Complementer using XOR gates
� NAND(a; b; c) = NAND(a;AND(b; c))
AND(b; c) = bc+ 0:c
0
= MUX(b; 0; c)
NAND(a; z) = (az)
0
= a
0
+ z
0
= a
0
z + 1:z
0
= MUX(a
0
; 1; z)
Thus NAND(a; b; c) = MUX(a
0
; 1;MUX(b; 0; c))
� XOR(a; b) = a� b = a
0
b+ ab
0
= MUX(a
0
; a; b)
� XNOR(a; b) = a� b
0
= ab+ a
0
b
0
= MUX(a; a
0
; b)
Exercise 6.10 From the network in Figure 6.13 we can obtain the following expressions for the
selection signal s (which controls the rightmost multiplexers), and the output signals z
1
and z
2
:
s = ab+ a
0
b
0
= (a� b)
0
z
1
= cs+ c
0
s
0
= c� s
0
= a� b� c
z
2
= bs+ cs
0
= b(ab+ a
0
b
0
) + c(ab
0
+ a
0
b)
= ab+ ab
0
c+ a
0
bc
= a(b+ b
0
c) + b(a+ a
0
c)
= a(b+ c) + b(a+ c)
= ab+ ac+ bc
From the boolean expressions we can see that z
1
= a � b � c corresponds to the high-level
description:
z
1
= (a+ b+ c) mod 2
and z
2
= 1 when 2 or more inputs have the value 1. These equations correspond to sum and
carry-out outputs of a one-bit adder, with inputs a; b, and c.
Solutions Manual - Introduction to Digital Design - February 2, 1999 95
Exercise 6.11 Tree of multiplexers:
Part (a) E(a; b; c; d) = a
0
b+ a
0
b
0
c
0
+ bc
0
d+ abd
0
+ b
0
cd
We use Shannon's decomposition to obtain the following four expressions:
E(a; b; 0; 0) = a
0
b+ a
0
b
0
+ ab = a
0
b
0
+ b = a
0
+ b
E(a; b; 0; 1) = a
0
b+ a
0
b
0
+ b = a
0
+ b
E(a; b; 1; 0) = a
0
b+ ab = b
E(a; b; 1; 1) = a
0
b+ b
0
= a
0
+ b
0
= (ab)
0
From these expressions we obtain the tree of multiplexers as shown in Figure 6.9.
MUX
1
0 MUX
1
0
MUX
1
0
MUX
1
0
MUX
1
0
a’
1
b
a’
1
b’
b
c
c
d
E(a,b,c,d)
E(a,b,1,1)
E(a,b,0,1)
E(a,b,0,0)
E(a,b,c,1)
E(a,b,c,0)
Figure 6.9: Multiplexer tree for E(a; b; c; d) = a
0
b+ a
0
b
0
c
0
+ bc
0
d+ abd
0
+ b
0
cd
Part (b) E(a; b; c; d; e; f) = a� b� c� d� e� f
Using the same type of decomposition we get the functions shown in the next table:
(c; d; e; f) E(a; b; c; d; e; f)
0000 a� b
0001 (a� b)
0
0010 (a� b)
0
0011 a� b
0100 (a� b)
0
0101 a� b
0110 a� b
0111 (a� b)
0
1000 (a� b)
0
1001 a� b
1010 a� b
1011 (a� b)
0
1100 a� b
1101 (a� b)
0
1110 (a� b)
0
1111 a� b
96 Solutions Manual - Introduction to Digital Design - February 2, 1999
The straight implementation of the tree of multiplexers will look like the network shown in Figure
6.10(a). Simplifying the network by removing the repeated terms we obtain the network shown in
Figure 6.10(b), that looks more like a linear array than a tree, but has the same number of levels
and less muxes.
MUX
1
0
MUX
1
0
MUX
1
0
MUX
1
0
MUX
1
0
a
a’
b
s’
d
d
d
d
e
MUX
1
0
a’
a
b
s=a’b+ab’
MUX
1
0
s
s’
c
MUX
1
0
s’
s
c
MUX
1
0
s
s’
c
MUX
1
0
s’
s
c
MUX
1
0
s’
s
c
MUX
1
0
s
s’
c
MUX
1
0
s
s’
c
MUX
1
0
s’
s
c
MUX
1
0
MUX
1
0
MUX
1
0
E(a,b,c,d,e,f)
e
f
(a) full multiplexer tree network (b) simplified network
MUX
1
0
MUX
1
0
MUX
1
0
MUX
1
0
MUX
1
0
MUX
1
0
MUX
1
0
b
E(a,b,c,d,e,f)
c
c
d
d
e
e
f
MUX
1
0
a’
a
b
s=a’b+ab’
MUX
1
0
a
a’
s’
Figure 6.10: Multiplexer network for Exercise 6.11 - part (b) - E(a; b; c; d; e; f) = a�b�c�d�e�f
A better multiplexer tree network is realized considering the implementation of the XOR and
XNOR functions by multiplexers (Exercise 6.9) and the associativity of the XOR function as follows:
a� b� c� d� e� f = [(a� b)� (c� d)]� (e� f)
The network for this case is presented in Figure 6.11. Observe that it has only 3 levels of multiplexers
in the critical path and 7 multiplexers. The previous implementation had 5 levels and used 9
multiplexers.
Exercise 6.12 From Exercise 6.6, and considering that the input numbers are represented as
x = (x
1
; x
0
) and y = (y
1
; y
0
), we have the following expressions for the outputs x = y (E), x > y
(G) or x < y (S):
G(x
1
; x
0
; y
1
; y
0
) = x
1
y
0
1
+ x
0
y
0
1
y
0
0
+ x
1
x
0
y
0
0
Solutions Manual - Introduction to Digital Design - February 2, 1999 97
MUX
1
0
E(a,b,c,d,e,f)
MUX
1
0
c’
c
d
MUX
1
0
a’
a
b
a xor b
MUX
1
0
a
a’
b
(a xor b)’
MUX
1
0
MUX
1
0
MUX
1
0
f
e’
e
c xor d
e xor f
Figure 6.11: Implementation using XOR property to solve Exercise 6.11(b) - E(a; b; c; d; e; f) =
a� b� c� d� e� f
E(x
1
; x
0
; y
1
; y
0
) = (x
1
y
1
+ x
0
1
y
0
1
)(x
0
y
0
+ x
0
0
y
0
0
)
S(x
1
; x
0
; y
1
; y
0
) = x
0
1
y
1
+ x
0
0
y
1
y
0
+ x
0
1
x
0
0
y
0
By decomposition we obtain:
G(x
1
; x
0
; 0; 0) = x
1
+ x
0
+ x
1
x
0
= x
0
+ x
1
= MUX(x
0
; 1; x
0
1
)
G(x
1
; x
0
; 0; 1) = x
1
G(x
1
; x
0
; 1; 0) = x
1
x
0
= MUX(x
0
; 0; x
1
)
G(x
1
; x
0
; 1; 1) = 0
E(x
1
; x
0
; 0; 0) = x
0
1
x
0
0
= MUX(x
0
0
; 0; x
0
1
)
E(x
1
; x
0
; 0; 1) = x
0
1
x
0
= MUX(x
0
; 0; x
0
1
)
E(x
1
; x
0
; 1; 0) = x
1
x
0
0
= MUX(x
0
0
; 0; x
1
)
E(x
1
; x
0
; 1; 1) = x
1
x
0
= MUX(x
0
; 0; x
1
)
S(x
1
; x
0
; 0; 0) = 0
S(x
1
; x
0
; 0; 1) = x
0
1
x
0
0
= MUX(x
0
0
; 0; x
0
1
)
S(x
1
; x
0
; 1; 0) = x
0
1
S(x
1
; x
0
; 1; 1) = x
0
1
+ x
0
0
+ x
0
1
x
0
0
= x
0
0
+ x
0
1
= MUX(x
0
0
; 1; x
1
)
that corresponds to the network of multiplexers shown in Figure 6.12.
98 Solutions Manual - Introduction to Digital Design - February 2, 1999
MUX
1
0
MUX
1
0
y1
y1
MUX
1
0
G
y0
MUX
1
0
MUX
1
0
y1
y1
MUX
1
0
E
y0
MUX
1
0
MUX
1
0
y1
y1
MUX
1
0
S
y0
MUX
1
0
x1
MUX
1
0
x1’
MUX
1
0
x1’
MUX
1
0
x1’
MUX
1
0
x1
MUX
1
0
x1
x0
0
x0
1
x0
0
x0’
0
x0’
0
x0’
1
0
x1
x1’
0
Figure 6.12: Network for Exercise 6.12