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+VZ+VY+WZ+VWY

 

b. F=m(0,1,4,5,12,13)

 

F= AC+BC

 

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

 

3.4.a Express F=ABC+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+CD = 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.

 

F = AC+AD = (A+C)(A+D)

 

d. Express F' in minimized sum of products form

 

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

 

F = A+CD

 

e. Implement F and F using only NAND gates

F = AD+AC = ((AD)(AC))

 

F = A+CD = (A(CD)) = (A(CD))

 

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 = AB+BCD+ACD+ABD

 

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)

ABC+ABCD+ABCD+AB

 

Next, Place 0s in the K-Map according to that function

 

 

F = ACD+ABD+ABC+ABC

 

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

 

 

G: Follow same procedure

 

 

 

 

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

 

F = AC+AD+BCD

 

G = ((A+B)D)+(A+BC) = AD+BD+A+BC

 

G = A+BD+BC

 

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

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

F = CD+AB+CA

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

G =ABC+ABD

=(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

X = AB+BC+AD

Y = ABCD

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 = BD+B+CD+AD = (B+D)(B)(C+D)(A+D)

Z = C+BC+AD = C(B+C)(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+BCD+ACD+ABC+ACD+BCD

 

Z =

ABCD+ABCD+ABCD+ABCD+ABCD+ABCD+ABCD+ABCD

 

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

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

 

Y = ABC+ACD+BCD+ABD+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+BC+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 )