## 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)+AB’D+B’D’+BDE = B’D’(1)+B’D(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 = A’B’D+A’BD+AC’D’+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.

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+B’D’ C1 = A+C’D’+CD+B’ C2 = B+C’+D C3 = B’D’+CD’+BC’D+B’C C4 = B’D’+CD’ C5 = A + C’D’+BD’+BC’ C6 = A+CD’+BC’+B’C

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 = A’B’C+A’BC’+AB’C’+ABC

Consequently,

Z = EF+EG+FG

Y = E’F’G+E’FG’+EF’G’+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 = V’Y’+V’W’X’+V’X’Z’+V’W’Z’+W’X’Y’+W’Y’Z’+X’Y’Z’

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