## CSE370 (Autumn 03) Assignment 3 Solution

1. CLD-II, Chapter 3, problem 3.1, parts a, and b.

3.1.a Use K-Maps to simplify F=M(0,4,18,19,22,23,25,29) F = WY+V’Z+V’Y+WZ’+VW’Y’

b. F=m(0,1,4,5,12,13) F= A’C’+BC’

2. CLD-II, Chapter 3, problem 3.4, all parts.

3.4.a Express F=AB’C+AD+AC in Canonical product of sums form. Use M notation

To get M notation simply state all of the 0 squares. M=(0,1,2,3,4,5,6,7,8,12)

b. Express F in minimized product of sums form

Group the zeros as shown above, then convert to PoS form.

F = A’+C’D’ = A(C+D)

c. Express F' in minimized product of sums form

F’ means 1s and 0s switch. To get the POS, group the 1s as shown

and then put the result in POS form.

d. Express F' in minimized sum of products form

Group on the 0s to get the sum of products of F'

F’ = A’+C’D’

e. Implement F and F’ using only NAND gates F’ = A’+C’D’ = (A’’(C’D’)’)’ = (A(C’D’)’)’ f. Implement F and F' using only NOR gates

F = (C’+D’)(A’) = ((C’+D’)’+A)’ F’ = (A’+C’)(A’+D’) = ((A’+C’)’+(A’+D’)’)’ 3. CLD-II, Chapter 3, problem 3.6, parts c, and e.

3.6.c Use K-map to put F’=m(2,4,5,6,7,8,10,13) into minimized Sum of  Products form F’ = A’B+BC’D+A’CD’+AB’D

e. F=(A’+B+C)(A+B+C’+D)(A+B’+C+D)(A’+B’)

First convert back to SoP form

(A’+B+C)(A+B+C’+D)(A+B’+C+D)(A’+B’)

(A’+B+C)’+(A+B+C’+D)’+(A+B’+C+D)’+(A’+B’)’

AB’C’+A’B’CD’+A’BC’D+AB

Next, Place 0s in the K-Map according to that function F = A’C’D’+A’B’D+A’BC+AB’C

4. CLD-II, Chapter 3, problem 3.11, part b.

3.11.b Draw a schematic for F=(AB+C)E+DG using only NOR and NAND gates.

First construct the F from AND and OR gates Replace ANDs with NANDs and add Bubbles on the inputs that correspond. Replace ORs with bubbled inputs with NANDs. 5. CLD-II, Chapter 3, problem 3.16, all parts.

3.16 Consider the functions:

(i) F=(A+(BC))(C’+D)

(ii) G=((A+B’)D)+(A+(BC))

a. Implement each function using only NAND Gates

F: use procedure for 3.11.b   G: use procedure from 3.11.b   b. Repeat (a) using NOR gates only

F: Implement using ANDs and ORs Replace ORs with NORs and invert inputs to all ANDs Replace ANDs with inverted inputs with NORs    c. Find the 2-level minimized Sum of Products Form

F = (A+BC)(C’+D) = A(C’+D)+BC(C’+D) = AC’+AD+BCD

Fill in and then group the 1s for the SoP  G = A+B’D+BC

d. Find the 2-level minimized Product of Sums Form

Group the 0s in the K-maps from part C

F = CD’+A’B’+C’A’

= (C’+D)(A+B)(C+A)

G =A’BC’+A’B’D’

=(A+B’+C)(A+B+D)

e. For each function what is the “simplest” implementation

F is better with the NOR implementation

G is better with the NAND implementation

6. CLD-II, Chapter 3, problem 3.25, all parts.

3.25 Develop a minimized implementation of a 2-bit combinational divider. The

system has 2 2-bit inputs A,B and C,D and generates 2 2-bit outputs, the quotient

W,X and the remainder Y,Z.

a. Draw the truth tables for W,X(A,B,C,D) and Y,Z(ABCD)

 A B C D W X Y Z 0 0 0 0 X X X X 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 X X X X 0 1 0 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 1 0 0 0 1 1 0 0 0 X X X X 1 0 0 1 1 0 0 0 1 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 1 1 0 0 X X X X 1 1 0 1 1 1 0 0 1 1 1 0 0 1 0 1 1 1 1 1 0 1 0 0

b. Minimize the functions W,X,Y,Z using 4-variable K-maps.

Write the expressions for the minimized sum of products form of each function W = AC’

Y = AB’CD

Z = BD’+CBA’

c. Repeat the minimization process, this time deriving product of sums form.

W = A’+C = AC’

X = BD+CA’ = (B’+D’)(C’+A)

Y = B’D’+B+C’D+A’D = (B+D)(B’)(C+D’)(A+D’)

7. CLD-II, Chapter 3, problem 3.27, all parts.

3.27 Develop a minimized implementation of a “ones count” circuit. The system has 4

inputs A,B,C,D and generates a 3-bit output XYZ. XYZ is 000 if 0 inputs are 1,

001 if 1 input is 1 and so on.

a. Draw the truth table for XYZ(A,B,C,D)

 A B C D X Y Z A B C D X Y Z 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 1 1 0 0 1 0 1 0 0 0 1 0 0 0 1 1 0 1 0 0 1 0 0 0 1 1 0 1 0 1 0 1 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 1 1 0 1 1 0 0 1 0 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 1 1 1 1 0 0

b. Minimize the functions X,Y,Z using 4-variable K-maps to derive minimized Sum of Products form.  X = ABCD

Y = ABC’+BC’D+AC’D+AB’C+A’CD+BCD’

Z =

A’B’C’D+A’BC’D’+AB’C’D’+ABC’D+A’BCD+AB’CD+A’B’CD’+ABCD’

c. Repeat the minimization process, this time deriving Product of Sums form.

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

Y = A’B’C’+A’C’D’+B’C’D’+A’B’D’+ABCD

Y =(A+B+C)(A+C+D)(B+C+D)(A+B+D)(A’+B’+C’+D’)

Z = (A+B+C+D)(A+B+C’+D’)(A+B’+C+D’)(A+B’C’+D)(A’+B+C+D’)

(A’+B+C’+D)(A’+B’+C+D)(A’+B’+C’+D’)

Comments to: cse370-webmaster@cs.washington.edu (Last Update: 10/23/03 )