60-265 COMPUTER
SYSTEM ARCHITECTURE I: DIGITAL DESIGN

Solution for Midterm #1

Question: 1 (a) (12
Marks)

Use
Boolean algebra to prove that

X.Y + X’.Y.Z +
X.Y.Z + Y.Z’.W’ + Z’.W + Y.Z’.W = Y + Z’.W

State the Identities used,
if any, at each step.

Hint: Some of the identities, which may be used are:

1 + A = 1;  A.1
= A;   A + A’ = 1;   A
+ A’.B = A + B

Solution:

X.Y + X’.Y.Z + X.Y.Z +
Y.Z’.W’ + Z’.W + Y.Z’.W

= Y (X + X’Z + XZ
+Z’W’ + Z’W) + Z’W

= Y (X + Z + XZ +Z’) +
Z’W

By using A + A’B = A + B, A + A’ = 1, A.1 = A

= Y (X + XZ +1) + Z’W

By using A + A’ = 1

= Y + Z’W = RHS

By using 1 + A = 1, A.1 = A

Question: 1 (b) (4 Marks)

Given a
function:   F1(X, Y,
Z, W) = Y + Z’.W.

Implement the
function by using NAND gates only.

Solution:

F1(X, Y, Z, W) = Y +
Z’W

F1(X, Y, Z, W) = (Y +
Z’W)’’ = (Y’. (Z’W)’)’

Question: 1 (c) (4Marks)

For the following
network (Fig. 1), find the Boolean expressions for ANY TWO of W, X, Y and Z in
terms of A, B, C and D.

FIG.1

Hint:
Find the output functions by going from left to right and by determining the
output of each gate.

Solution:

W = A + B. (C+ D)

X = B’. (C + D) +
B.C’.D’

Y = C’.D’ + C.D

Z = D’

Question: 2 (a) (12
Marks)

A
Logic Function F2(A, B, C, D) has the following
Prime Implicants:

A’.D,   A’.B.C’,   B.C’.D’,   A.C’.D’,   A.B’.C’,   B’.C’.D.

Obtain its Karnaugh Map.

Hint: For each Prime
Implicant go through the following two steps:

Step 1:
Select the rows and columns, corresponding to the literals in the Prime
Implicant.

Step 2:
Put 1’s in the cells lying at the inter-section of the selected rows and
columns.

Which
of the Prime Implicants of F2(A,
B, C, D) are
Essential?

Solution:

K-MAP

CD

AB

00

01

11

10

00

0

1

1

0

01

1

1

1

0

11

1

0

0

0

10

1

1

0

0

Essential P.I.: A’.D

Question: 2 (b) (8
Marks)

Obtain the Karnaugh Map for

F3(A, B, C, D) = ∑ m(1, 5, 6, 7,
11, 12, 13, 15).

From the Karnaugh Map, find the simplified
expression for F3(A, B, C, D) in
‘Product Of Sum (POS)’ form.

Solution:

K-MAP

CD

AB

00

01

11

10

00

0

1

0

0

01

0

1

1

1

11

1

1

1

0

10

0

0

1

0

F3 (A, B, C, D) = (A + C
+ D). (A + B + C’). (A’ + B + C). (A’ + C’+ D)

Question: 3 (a) (8
Marks)

Write
the Truth table for a Full Adder.

Solution:

A

B

Cin

S

Cout

0

0

0

0

0

0

0

1

1

0

0

1

0

1

0

0

1

1

0

1

1

0

0

1

0

1

0

1

0

1

1

1

0

0

1

1

1

1

1

1

Question: 3 (b) (12
Marks)

Write
the expressions for the Sum and Carry-output in terms of the three inputs of
the Full Adder so that the Full Adder can be implemented by using two XOR
gates, two AND gates and one OR gate.

Draw
the schematic diagram of the Full Adder by using two XOR gates, two AND gates
and one OR gate.

Solution:

Cout = A’.B.Cin
+ A.B’.Cin + A.B. Cin’ + A.B. Cin

= (A’.B + A.B’)
Cin + A.B

=
(A      B). Cin
+ A.B

S = A’.B’. Cin
+ A’.B. Cin’ + A.B’. Cin’ + A.B.
Cin

= (A’.B’
+ A.B). Cin + (A’.B + A.B’). Cin’

Let P = A      B = A’.B +
A.B’

P’ = (A’.B +
A.B’)’ = (A + B’). (A’ + B) = A.A’ + A.B +
A’.B’ + B.B’ = A.B + A’.B’

S = P’. Cin + P. Cin’ =
P      Cin
= (A
B)      Cin

Question: 3 (c) (10
Marks)

Use
three Full Adders and one Half Adder to draw the schematic diagram of a 4-bit
Adder.

Solution:

Question: 4 (a) (10
Marks)

F4(A, B, C, D) = Σ ( m(1, 3,
4, 11, 12, 15).

Use a 8-to-1 MUX, along with an Inverter, to
obtain an implementation.

Hint: A
few of the inputs of the MUX may be connected to 0.

Solution:

Y =
A’.B’.C’.I0 + A’.B’.C.I1 + A’.B.C’I2
+ A’.B.C.I3 + A.B’.C’.I4 + A.B’.C.I5 + A.B.C’.I6
+     A.B.C.I7

F4 =
A’.B’.C’.D + A’.B’.C.D +
A’.B.C’.D’ + A.B’.C.D + A.B.C’.D’ + A.B.C.D

Comparing
Y with F4

D = I0 =
I1 = I5 = I7

D’
= I2 = I6

0 = I3 =
I4

Question: 4 (b) (10
Marks)

Use two 3-to-8 Active Low Decoders and an
inverter to obtain an Active Low 4-to-16 Decoder. Assume that each of the two
3-to-8 Active Low Decoders has an Active Low Enable input.

Solution:

Question: 4 (c) (10
Marks)

Use the Active Low 4-to-16 Decoder, along
with two gates to obtain an
implementation for the following two functions:

(i)  F4(A, B,
C, D) = Σ ( m(1, 3, 4, 11, 12, 15)

(ii) F5(A, B,
C, D) = Σ ( m(1, 3, 4, 5, 9, 10, 11, 12, 13, 14, 15).

For implementing each of the two functions F4(A,
B, C, D) and F5(A, B, C, D), choose a gate with as small a value of fan-in as possible.

Solution:

*              *             *             *             *             *             *             *             *             *