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(A[1:0])?
   2. What is the maximum value that can be represented in 2 bits for B(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.
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 entries 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. (3.41)

   The IEEE 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. If at least 35 cents has been put in the controller, it will output a soda and proper change (if applicable). Draw a finite state machine that describes the behavior of the soda controller. Each state will represent how much money has been put in (Hint: There will be seven of those states). Once enough money has been put int, the controller will go to a final state where the person will receive a soda and proper change (Hint: There are five such final states). From the final state, the next coin that is put in will start the process again.

4. (3.44) modified

   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. The frequency of a computer is inversely proportional to its clock cycle time. That is to say, Frequency = 1/Cycletime, e.g.: a 1GHz computer has a clock cycle time of 1 nanosecond (10^-9 seconds).

   Instructions may broadly be divided into those that access memory (loads and stores), those that perform arithmetic/logic operations(ADD, AND, OR etc) and other instructions such as branch and jump instructions (these determine what is known as control flow). An instruction can take multiple clock cycles to execute. Let us assume that in a particular computer memory access instructions take 12 clock cycles to execute, arithmetic instructions take 9 clock cycles to execute, while other instructions take 10 clock cycles to execute.

   The approximate percentages of occurrence of these instructions in a given program, on an average, are:

   Type of Instruction	Percentage of Occurence
   Memory Access instructions	40%
   Arithmetic and Logic instructions	40%
   Other Instructions	20%

   On a 3.2 GHz machine, assuming everything goes smoothly, estimate how long will this 650,000 instruction program take to execute?

6. (4.4)

   What is the word length of a computer? How does the word length of a computer affect what the computer is able to compute? That is, is it a valid argument, in light of what you learned in Chapter 1, to say that a computer with a larger word size can process more information and therefore is capable of computing more than a computer with a smaller word size?

7. (4.7)

   Suppose a 32-bit instruction takes the following format:

   OPCODE

   DR

   SR1

   SR2

   UNUSED

   If there are 255 opcodes and 120 registers,

   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?
8. (4.10)

   Examples 4.1, 4.2, and 4.5 illustrate the processing of the ADD, LDR, and JMP instructions. The PC, IR, MAR, and MDR are written in various phases of the instruction cycle, depending on the opcode of the particular instruction. In each location of the table below, enter the opcodes which write to the corresponding register (row) during the corresponding phase (column) of the instruction cycle.

   	Fetch Instruction	Decode	Evaluate Address	Fetch Data	Execute	Store Result
   PC
   IR
   MAR
   MDR

9. (4.15)

   If a HALT instruction can clear the RUN latch, thereby stopping the instruction cycle, what instruction is needed to set the RUN latch, thereby reinitiating the instruction cycle?

10. Suppose that an instruction cycle of the LC-3 has just finished and another one is about to begin. The following table describes the values in select LC-3 registers and memory locations:

    Register	Value
    IR	x3001
    PC	x3003
    R1	x3000
    R2	x3002
    Memory Location	Value
    x3000	x62BF
    x3001	x3000
    x3002	x6280
    x3003	x62BE

    For each phase of the new instruction cycle, specify the values that PC, IR, MAR, MDR, R1, and R2 will have at the end of the phase in the following table:

    	PC	IR	MAR	MDR	R1	R2
    Fetch
    Decode
    Evaluate Address
    Fetch Operands
    Execute
    Store Result

    Hint: Example 4.2 illustrates the LDR instruction of the LC-3. Notice that values of memory locations x3000, 3002, and 3003 can be interpreted as LDR instructions.



11. Added September 21.
    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 from 0:00 to 15:00, where m:s (minutes, seconds)
    
    What is the minimum number of bits that we need to use to store the state required?