CSE370 (Autumn 03) Assignment 4 Solution


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

 

3.24.a

Starting with the switch closed means that input to U1 is a logic 0. Therefore U1 = 1 and if a NOR has an input of 1 its output is zero. The two inverters guarantee that this is the input from U2 as well.

 

When the switch is opened, U1 switches to a 0. U2 is also 0 and 0 NOR 0 = 1. After 2 inverter delays, U2 becomes 1, so U3 = 0. This in turn drives U2 back to 0 after 2 gate delays. The process continues until the switch is closed again.

 

 

b.

The only difference here is that one inverter is missing. With the switch closed, U3 is 0 and U2 is 1. When the switch is opened, U1 becomes 0 but U3 does not change because 1 NOR X = 0 and U2 = 1. Therefore U3 will never be 1.

 

 

2. CLD-II, Chapter 4, problem 4.2 (Let F = ABCD' + AB'D + B'D' + BCD' + BDE instead of the one given in the chapter 4 handout).

 

4.2 Implement the function F using a 4:1 multiplexer and no other logic. The constants logic 1, logic 0, and the variables, but not their complements are available.

 

There are 2 select bits, and B and D appear in each term, so choose them as selection inputs.

 

F = BCD(A+1)+ABD+BD+BDE = BD(1)+BD(A)+BD(C)+BD(E)

 

B

D

F

0

0

1

0

1

A

1

0

C

1

1

E

 

 

3. CLD-II, Chapter 4, problem 4.7 (use the chips in your lab kit for part b).

4.7.a Implement F = ABD+ABD+ACD+ACD using one 4:16 decoder and a very large fan-in OR gate.

 

 

b. Compare the resulting number of gates with a solution using discrete gates only.

 

Decoder Implementation: Naively, 9 ICs

8 2-4 input NAND

1 2-4 input NOR

 

The diagram shown to the right implements F using gates found in your lab kit.

 

 

Total Cost: 3 ICs

1 3-3 input NAND

1 2-4 input NAND

1 6 inverter

 

Alternative: put F in minimal form before implementing.

 

ABD+ABD+ACD+ACD = AD(B+B) + AD(C+C)

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

 

Total Cost: 1 IC

1 4-2 input XOR

 

4. CLD-II, Chapter 4, problem 4.8

4.8 Show how to implement the BCD-to-seven-segment LED decoder shown below using a PAL with 10 inputs, 8 OR gate outputs, and 7 product terms per OR gate. Use the shorthand notation developed in Section 4.2.

 

 

 

 

C0 = A+BD+C+BD

C1 = A+CD+CD+B

C2 = B+C+D

C3 = BD+CD+BCD+BC

C4 = BD+CD

C5 = A + CD+BD+BC

C6 = A+CD+BC+BC

 

 

5. CLD-II, Chapter 4, problem 4.10, all parts.

 

4.10. Given a 4-input Boolean Function f =m(0,3,5,7,11,12,13,15)

 

a. Implement f using a 16:1 multiplexer

Connect inputs for all min-terms to logic 1, others to logic 0.

 

 

b. Implement using an 8:1 multiplexer (Use D,D as inputs, A,B,C as selection inputs).

 

A

B

C

D

F

8:1

0

0

0

0

1

D

0

0

0

1

0

0

0

1

0

0

D

0

0

1

1

1

0

1

0

0

0

D

0

1

0

1

1

0

1

1

0

0

D

0

1

1

1

1

1

0

0

0

0

0

1

0

0

1

0

1

0

1

0

0

D

1

0

1

1

1

1

1

0

0

1

1

1

1

0

1

1

1

1

1

0

0

D

1

1

1

1

1

 

c. Implement using a 4:1 multiplexer (Place A,C on the select inputs, Assume B, D are available and use an XOR gate to form one of the inputs to the multiplexer.

Reorder the truth table so A,C are the first two columns.

 

 

A

B

C

D

F

8:1

4:1

0

0

0

0

1

D

B XOR D

0

0

0

1

0

0

1

0

0

0

D

0

1

0

1

1

0

0

1

0

0

D

D

0

0

1

1

1

0

1

1

0

0

D

0

1

1

1

1

1

0

0

0

0

0

B

1

0

0

1

0

1

1

0

0

1

1

1

1

0

1

1

1

0

1

0

0

D

D

1

0

1

1

1

1

1

1

0

0

D

1

1

1

1

1

 

 

d. Implement the function using a 4:16 decoder and an OR gate

 

 

 

 

6. CLD-II, Chapter 4, problem 4.17, a-d.

4.17 Implement a 7-input majority function that outputs 1 whenever 4 or more of its inputs are asserted.

Find the minimized sum of products form for circuit #1 (circuit #2 is

identical). The functions V and W should look familiar. What do they implement?

A

B

C

W

V

0

0

0

0

0

0

0

1

0

1

0

1

0

0

1

0

1

1

1

0

1

0

0

0

1

1

0

1

1

0

1

1

0

1

0

1

1

1

1

1

 

 

W = AB+AC+BC

V = ABC+ABC+ABC+ABC

 

Consequently,

 

Z = EF+EG+FG

Y = EFG+EFG+EFG+EFG

b. Complete a 5-Variable Truth Table for circuit #3

 

V

W

X

Y

Z

Q

 

V

W

X

Y

Z

Q

0

0

0

0

0

0

 

1

0

0

0

0

0

0

0

0

0

1

0

 

1

0

0

0

1

0

0

0

0

1

0

0

 

1

0

0

1

0

1

0

0

0

1

1

0

 

1

0

0

1

1

1

0

0

1

0

0

0

 

1

0

1

0

0

0

0

0

1

0

1

0

 

1

0

1

0

1

1

0

0

1

1

0

0

 

1

0

1

1

0

1

0

0

1

1

1

1

 

1

0

1

1

1

1

0

1

0

0

0

0

 

1

1

0

0

0

0

0

1

0

0

1

0

 

1

1

0

0

1

1

0

1

0

1

0

0

 

1

1

0

1

0

1

0

1

0

1

1

1

 

1

1

0

1

1

1

0

1

1

0

0

0

 

1

1

1

0

0

1

0

1

1

0

1

0

 

1

1

1

0

1

1

0

1

1

1

0

1

 

1

1

1

1

0

1

0

1

1

1

1

1

 

1

1

1

1

1

1

 

 

c. Find the minimum sum of products form for Q using the K-map method.

 

This is one way to represent a 5-variable K-Map. Groupings with only right angles are for a single V value. Those with the diagonal lines represent groupings across the two planes

 

Q = VY + VWX+VXZ+VWZ+WXY+XYZ+WYZ

 

d. Find the minimum product of sums form for Q using the K-map method.

 

Q = VY+VWX+VXZ+VWZ+WXY+WYZ+XYZ

= (V+Y)(V+W+X)(V+X+Z)(V+W+Z)(X+W+Y)(W+Y+Z)(X+Y+Z)

 


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