Department of Electrical and Computer Engineering

The University of Texas at Austin

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.

Questions

1. (3.28)
   Having designed a binary adder, you are now ready to design a 2-bit by 2-bit unsigned binary multiplier. The multiplier takes two 2-bit inputs A[1:0] and B[1:0] and produces an output Y which is the product of A[1:0] and B[1:0]. The standard notation for this is:
   Y = A[1:0]⋅B[1:0]
   1. What is the maximum value that can be represented in 2 bits for A[1:0]?
   2. What is the maximum value that can be represented in 2 bits for B[1:0]?
   3. What is the maximum possible value of Y?
   4. What is the number of required bits to represent the maximum value of Y?
   5. Write a truth table for the multiplier described above. You will have a four input truth table with the inputs being A[1], A[0], B[1], and B[0].
   6. Implement the third bit of output, Y[2] from the truth table using only AND, OR, and NOT gates. (We are only asking you for one bit of output in order to reduce the amount of busy work. You should be able to do all bits of output, when asked.)


2. (3.33)
   Using Figure 3.21, the diagram of the 4-entry, 2²-by-3-bit memory.
   1. To read from the fourth memory location, what must the values of A[1:0] and WE be?
   2. To change the number of locations in the memory from 4 to 60, how many address lines would be needed? What would the addressability of the memory be after this change was made?
   3. Suppose the minimum width (in bits) of the program counter (the program counter is a special register within a CPU, and we will discuss it in detail in the next chapter) is the minimum number of bits needed to address all 60 locations in our memory from part (b). How many additional memory locations could be added to this memory without having to alter the width of the program counter?


3. (Adapted from 3.41)
   The HKN campus society office sells sodas for 35 cents. Suppose they install a soda controller that only takes the following three inputs: nickel, dime, and quarter. After you put in each coin, you push a pushbutton to register the coin (this acts like a clock). If at least 35 cents has been put in the controller, it will go to a final state and output a soda and proper change (if applicable). From each of the final states, the next coin that is put in will start the process again. Draw a finite state machine that describes the behavior of the soda controller. Each state represents a unique situation. How many do you need to cover all situations? Hint 1: How much money could be in the machine already? Hint 2: How many final states do you need to represent "Dispense a soda and give n cents in change"?



4. (Adapted from 3.44)
   Prove that the NOR gate, by itself, is logically complete (see Section 3.3.5) by constructing a logic circuit that performs the AND function, a logic circuit that performs the NOT function, and a logic circuit that performs the OR function. Use only NOR gates in these three logic circuits.



5. We want to make a state machine for the scoreboard of the Texas vs. Oklahoma Football game. The following information is required to determine the state of the game:
   
   Score: 0 to 99 points for each team
   Down: 1, 2, 3, or 4
   Yards to gain: 0 to 99
   Quarter: 1, 2, 3, 4
   Yardline: any number from H0 to H49, V0 to V49, 50
   Possesion: H, V
   Time remaining: any number of minutes from 0 to 15 and any number of seconds from 00 to 59
   
   What is the minimum number of bits that we need to use to store the state required?



6. In this problem, we want you to evaluate how long it takes a particular program (let's call it program A) to perform its desired task on a particular computer (let's call it computer B).
   

   There are in general three kinds of instructions: data movement (such as loads and stores), operates (such as ADD and AND), and control flow (such as branches and jumps). Computer B takes on average 12 clock cycles to execute each data movement instruction, 9 cycles on average to execute each operate instruction, and 10 cycles on average to execute the others. The clock frequency of computer B is 3.2 GHz. (1 GHz = 10⁹ cycles/sec.)
   

   To perform its task, from beginning to end, program A has to execute 650,000 instructions, of which 40% are data movement instructions, 40% are operates, and 20% are control.
   

   Hint: to compute the time it takes to execute this program you will need to know how much time (in fraction of a second) is required for each clock cycle. Note that the frequency expresses how many clock cycles in one second. So, for example, if the frequency is 2 GHz, which is 2 billion cycles each second, the time taken by one cycle is 1/(2 billion), which is 0.5 x 10^-9 seconds.
   

   How long does program A take to carry out its task on computer B? (Since all our numbers are averages, the exact execution time you will compute is an approximation of the actual execution time of program A on computer B.)



7. (4.11)
   State the phases of the instruction cycle and briefly describe what operations occur in each phase.



8. (4.8)
   Suppose a 32-bit instruction has the following format:

   OPCODE

   DR

   SR1

   SR2

   UNUSED

   If there are 255 opcodes and 120 registers, and every register is available as a source or destination for every opcode,

   1. What is the minimum number of bits required to represent the OPCODE?
   2. What is the minimum number of bits required to represent the Destination Register (DR)?
   3. What is the maximum number of UNUSED bits in the instruction encoding?