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 and the time for the discussion section you would like the problem set turned back to you. Show your work.

1. Given one 5-bit number, n, construct a logic circuit (using two-input AND, OR, XOR and NOT gates) that returns 1 if n has an odd number of 1s.


2. (3.8) (If the logic equation in your book does not match with the following equation, please correct it in your book, or see errata sheet) - 09/18/08)
   (Please refer to the figure for problem 3.8 on page 85 of the book) The transistor level circuit implements the logic equation Y= NOT(A AND (B OR C)). Label the inputs to all the transistors.
   


3. Find a logical equation for the output of the circuit in Figure 1. Inputs are a, b and c, while z is the output.
   
   
   Figure 1
   
   
   


4. A roadway intersection consists of a main road having three lanes of traffic in each direction and a side road with one lane in each direction. Access to the intersection is controlled by a traffic light that is usually green for the main road, and usually red for the side road.
   
   Your job: design a logic circuit whose output Y is used to change the light from red to green for the side road when there are at least three cars waiting for the light to change on the access road during daylight hours, one car waiting for the light to change during non-daylight hours, or when the light has been red for 5 minutes. We will need a separate logic signal Z for changing the light from green back to red, but that is not today's problem.
   
   The logic circuit has four input variables:
   A = 1, daylight; =0, nightfall.
   B = at least one car waiting at the red light..
   C = at least three cars waiting at the red light..
   D = 1, The red light has been illuminated for more than 5 minutes; =0, < 5 min.
   
   
   Figure 2
   
   Note: in order to make this work, you will need a daylight detector that senses the degree of sunlight, and outputs a 1 if there is daylight, 0 otherwise. Also, a piece of logic that converts the number of cars that have crossed the trip wire into C=1 if the number recorded is greater than 2, and B=1 if the number registered is greater than 0. Finally a piece of logic that indicates when the red light has been on for 5 minutes.
   
   Write the logic equation for Y in terms of A,B,C,D that solves this problem.
   
   
5. Fill in the truth table for the logical expression OUT = NOT(NOT(A) AND NOT(B) AND NOT(C)). What single logic gate has this same truth table?
   
   
   
   
6. (3.11)
   
   1. 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. (These figures can be found in the book on pages 56 & 57 respectively).
      
   2. 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:
      1. A = 1, B = 0, C = 0
      2. A = 0, B = 1, C = 0
      3. A = 1, B = 1, C = 1
   
   
7. (Adapted from 3.13)
   
   1. How many output lines will a five-input decoder have?
   2. How many output lines will an eight-input decoder have?
   3. How many output lines will an n-input decoder have? (n can be any number)
   
   
8. (3.16)
   Given the following truth table, generate the gate-level logic circuit, using the implementation algorithm referred to in Section 3.3.4.
   
   
   
   
9. (3.27) For this question, refer to the figure on page 90 of the book.
   1. Describe the output of this logic circuit when the select line S is a logical 0. That is, what is the output of Z for each value of A?
   2. If the select line S is switched from a logical 0 to 1, what will the output be?
   3. Is this logical circuit a storage element?
   
   
   
10. (Adapted from 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 (A, B, C, and D), 2 control signals (S1 and S0), and 1 output (OUT). After implementing the 4-1 mux, fill in the truth table below.
    
    



11. (3.24)
    
    1. 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?
    2. 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.
    
    
12. (Adapted from 3.25)
    Say the speed of a logic structure depends on the largest number of logic gates through which any of the inputs must propagate to reach an output. Assume that a NOT, an AND, and an OR gate all count as one gate delay. For example, the propagation delay for a two-input decoder shown in Figure 3.11 is 2 because some inputs propagate through two gates.
    1. What is the propagation delay for the two-input mux shown in Figure 3.12?
    2. What is the propagation delay for the 4-bit adder shown in Figure 3.16?
    3. Can you reduce the propagation delay for the circuit shown in Figure 3 by implementing the equation in a different way? If so, how?
       
       Figure 3
       
       
    
    
13. (problem 13 has been deleted - 09/18/08)
    A logic circuit consisting of 6 gated D latches and 1 inverter is shown below:
    
    Figure 4
    
    Let the state of the circuit be defined by the state of the 6 D latches. Assume initially the state is 000000.
    Question: What is the state after 50 cyles. How many cycles does it take for a specific state to show up again?
    
    
14. (problem 14 has been updated - 09/16/08)
    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 5.
    
    
    Figure 5
    
    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 6 below).
    
    
    Figure 6
    
    
    1. Complete a truth table for the gate-level logic circuit shown in Figure 6 above.
    2. 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?