Problem Set 2

Due: 20 September, before class

Yale N. Patt, Instructor

Siddharth Balwani, Linda Bigelow, Tommy Buell, Jeremy Carrillo, Aamir Hasan,

Danny Lynch, Rustam Miftakhutdinov, Veynu Narasiman, Vishal Parikh, Basit Sheikh, TAs

Instructions:

You are encouraged to work on the problem set in groups and turn in one
problem set for the entire group. Remember to put all your names on the
solution sheet. Also remember to put the name of the TA in whose
discussion section you would like the problem set turned back to you.

- (3.7)

(Please refer to the figure for problem 3.7 on page 84 of the book) The circuit has a major flaw. Can you identify it?*Hint*: Evaluate the circuit for all sets of inputs. - Fill in the truth table for the logical
expression NOT(NOT(A) AND
NOT(B) AND NOT(C)). What single logic gate has this same truth table?

A B C

NOT(NOT(A) AND NOT(B) AND NOT(C))

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

- (3.11)

- Draw a transistor-level diagram for a three-input AND gate and a three-input OR gate. Do this by extending the designs from Figures 3.6a and 3.7a. (Figures can be found in the book on pages 56 & 57 respectively).
- Replace the transistors in your diagrams from part (
*a*) with either a wire or no wire to reflect the circuit’s operation when the following inputs are applied:- A = 1, B = 0, C = 0
- A = 0, B = 0, C = 0
- A = 1, B = 1, C = 1

- (3.13 modified)

- How many output lines will a five-input decoder have?
- How many output lines will an eight-input decoder have?
- How many output lines will an N-input decoder have? (N can be any number)

- Suppose we wanted to build a 5-input AND
gate, but we only had 2-input AND gates available. Since AND is an
associative logical operator,
**Z = A AND B AND C AND D AND E**could be computed as**Z = ((((A AND B) AND C) AND D) AND E)**, as shown below in Figure 1.

It turns out that XOR is also an associative logical operator, and a 5-input XOR gate can be constructed using 2-input XOR gates in the same manner (see Figure 2 below).

Figure 1

Figure 2

- Complete a truth table for the gate-level logic circuit shown in Figure 2 above.
- What do you notice about the input combinations that give an output value of 1? What do you notice about the input combinations that give an output value of 0?

- (3.16)

Given the following truth table, generate the gate-level logic circuit, using the implementation algorithm referred to in Section 3.3.4.

A B C

Z

0 0 0

1

0 0 1

0

0 1 0

0

0 1 1

1

1 0 0

0

1 0 1

1

1 1 0

1

1 1 1

0

- (3.18)

Implement the following functions using AND, OR, and NOT logic gates. The inputs are A, B, and the output is F.- F has the value 1 only if A has the value 0 and B has the value 1.
- F has the value 1 only if A has the value 1 and B has the value 0.
- Use your answers from (
*a*) and (*b*) to implement a 1-bit adder. The truth table for the 1-bit adder is given below. - Is it possible to create a 4-bit adder (a circuit that will
correctly add two 4-bit quantities) using only four copies of the logic
diagram from (
*c*)? If not, what information is missing?*Hint*: When A = 1 and B = 1, a sum of 0 is produced. What information is not dropped?

A B

Sum

0 0

0

0 1

1

1 0

1

1 1

0

- (3.19)

Logic circuit 1 in Figure 3.36 (page 87 of the book) has inputs A, B, C. Logic circuit 2 in Figure 3.37 (page 87 of the book) has inputs A and B. Both logic circuits have an output D. There is a fundamental difference between the behavioral characteristics of these two circuits. What is it?*Hint*: What happens when the voltage at input A goes from 0 to 1 in both circuits? - (3.22)

Implement a 4-to-1 mux using only 2-to-1 muxes making sure to properly connect all of the terminals. Remember that you will have 4 inputs, 2 control signals, and 1 output. Write out the truth table for this circuit. - (3.24)

- Figure 3.39 (page 89 of the book) shows a logic circuit that appears in many of today’s processors. Each of the boxes is a full-adder circuit. What does the value on the wire X do? That is, what is the difference in the output of this circuit if X = 0 versus if X = 1?
- Construct a logic diagram that implements an
adder/subtracter. That is, the logic circuit will compute A + B or A –
B depending on the value of X.
*Hint*: Use the logic diagram of Figure 3.39 as a building block.

- (3.26)

Recall that the adder was built with individual "slices" that produced a sum bit and carryout bit based on the two operand bits A and B and the carryin bit. We called such an element a full-adder. Suppose we have a 3-to-8 decoder and two six-input OR gates, as shown in Figure 3 below. Can we connect them so that we have a full-adder? If so, please do. (*Hint*: If an input to an OR gate is not needed, we can simply put an input 0 on it and it will have no effect on anything. For example, see the figure below.)

Figure 3