Department of Electrical and Computer Engineering

The University of Texas at Austin

EE 306, Fall 2009
Problem Set 3 Solutions
Due: October 12, before class
Yale N. Patt, Instructor
TAs: Aater Suleman, Chang Joo Lee, Ameya Chaudhari, Antonius Keddis, Arvind Chandrababu, Bhargavi Narayanasetty, Eshar Ben-dor, Faruk Guvenilir, Marc Kellermann, RJ Harden

  1. Moved from problem set 2.
    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:

    1. Score: 0 to 99 points for each team
    2. Down: 1, 2, 3, or 4
    3. Yards to gain: 0 to 99
    4. Quarter: 1, 2, 3, 4
    5. Yardline: any number from Home 0 to Home 49, Visitor 0 to Visitor 49, 50
    6. Possesion: Home, Visitor
    7. Time remaining: any number from 0:00 to 15:00, where m:s (minutes, seconds)
    (a) What is the minimum number of bits that we need to use to store the state required?
    (100*100)*4*100*4*101*2*901 = 2912032000000.

    2^41 < 2912032000000 < 2^42 so we need 42 bits

    (b) Suppose we make a separate logic circuit for each of the seven elements on the scoreboard, how many bits would it then take to store the state of the scoreboard?
    1. 7 x 2 bits

    2. 2 bits

    3. 7 bits

    4. 2 bits

    5. 7 bits

    6. 1 bit

    7. 4 bits for minutes 6 bits for seconds

    Total 43 bits


    (c) Why might part b be a better way to specify the state?
    The assignments in (b) are easier to decode

  2. Moved from problem set 2.
    A logic circuit consisting of 6 gated D latches and 1 inverter is shown below:


    Figure 1


    Figure 2

    Let the state of the circuit be defined by the state of the 6 D latches. Assume initially the state is 000000 and clk starts at time t = 0.
    Question: What is the state after 50 cyles. How many cycles does it take for a specific state to show up again?
    Every 6 clock cycles a pattern repeates (shown below). Because 50 = 6*8+2 after 50 cycles the state will be the same as after 2 cycles. It will be in state 111000 after 50 cycles



  3. (3.31) Moved from problem set 2.
    If a particular memory has 8 byte addressability and a 4 bit address space, how many bytes of memory does that computer have?

    Number of byes = address space x adressability. 2^4 x 2^3 = 2^7 = 128 bytes

  4. (3.33) Answer for 4a corrected on (10/14/09)
    Using Figure 3.21, the diagram of the, 22-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 read from the fourth location A[1:0] should be 11, to read from memory the WE bit should be 1 0. To write to memory the WE bit must be 1
    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. To address 60 locations you need 6 bits of address line, which means your MAR is 6 bits . However since we did not change the number of bits stored at each location the addressability is still 3 bits
    3. Suppose the minimum width (in bits) of the program counter 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?
      4. You need 6 bits for part b, which can address 64 different locations so you could add 4 more locations and not have to increase the width of the program counter.

  5. (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 in it, 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.

  6. (Adapted from 3.30)
    A comparator circuit has two 1-bit inputs, A and B, and three 1-bit outputs, G (greater), E (equal), and L (less than). Refer to figures 3.40 and 3.41 in the book for this problem.

    1. Draw the truth table for a 1-bit comparator.
      2. ABGEL
      00010
      01001
      10100
      11010

    2. Implement G, E and L for a 1-bit comparator using AND, OR, and NOT gates.
      3. G = AB' , L = A'B , E = A'B' + AB
    3. Figure 3.41 performs one-bit comparisions of the corresponding bits of two unsigned numbers A[3:0] and B[3:0].
      Using the 12 one-bit results of these four one-bit comparators, construct a logic circuit to output a 1 if unsigned number A is larger than unsigned number B.
      The inputs to your logic circuit should be labeled G[3], E[3], L[3], G[2], L[2], ... L[0]. (Hint: You do not need to use all 12 inputs if you can do it with fewer.)
    Y = G[3] + E[3]G[2] + E[3]E[2]G[1] + E[3]E[2]E[1]G[0]

  7. 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:

    RegisterValue
    IRx3001
    PCx3003
    R0x3000
    R1x3000
    R2x3002
    R3x3000
    R4x3000
    R5x3000
    R6x3000
    R7x3000
    Memory LocationValue
    x3000x62BF
    x3001x3000
    x3002x3001
    x3003x62BE

    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:

    PCIRMARMDRR0R1R2R3R4R5R6R7
    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.

    PCIRMARMDRR0R1R2R3R4R5R6R7
    Fetchx3004x62BE x3003x62BEx3000x3000x3002x3000x3000x3000x3000x3000
    Decodex3004x62BE x3003x62BEx3000x3000x3002x3000x3000x3000x3000x3000
    Evaluate Addressx3004x62BEx3003x62BEx3000x3000x3002x3000x3000x3000x3000x3000
    Fetch Operandsx3004x62BE x3000x62BFx3000x3000x3002x3000x3000x3000x3000x3000
    Executex3004x62BE x3000x62BFx3000x3000x3002x3000x3000x3000x3000x3000
    Store Resultx3004x62BE x3000x62BFx3000x62BFx3002x3000x3000x3000x3000x3000
  8. (4.8)
    Suppose a 32-bit instruction has the following format:

    OPCODEDRSR1SR2UNUSED

    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. 225 opcode, 8 bits are required to represent the OPCODE
    2. What is the minimum number of bits required to represent the Destination Register (DR)?
      3. 120 registers, 7 bits to represent the DR
    3. What is the maximum number of UNUSED bits in the instruction encoding?
      4. 3 registers and 1 opcode, 3x7 + 8 = 29 bits. So there are 3 ununsed bits

  9. Problem updated on 10/07/09.
    The memory locations x3000 to x3007 contain the values as shown in the table below. Assume the memory contents below are loaded into the simulator and the PC has been set to point to location x3000. Assume that a break point has been placed to the left of the HALT instruction (ie at location x3007 x3006 which contains 1111 0000 0010 0101). Assume that before the program is run, each of the 8 registers has the value x0000 and the NZP bits are 010.
    Memory LocationValue
    X3000 0101000000100000
    X3001 0001000000100101
    X3002 0010001000000100
    X3003 0001000000000000
    X3004 0001001001111111
    X3005 0000001111111101
    X3006 1111000000100101
    X3007 0000000000000100
    1. In no more than 15 words, summarize what this program will do when the “Run” button is pushed in the simulator. Hint: What relationship is there between the value loaded from memory and the final value in R0 after the program has completed?
      2. 5 is put in R0 and shifted left the value at location x3007 times
    2. What are the contents of the PC, the 8 general purpose registers (R0-R7), and the N, Z, and P condition code registers after the program completes?
      3. PCx3006
      R0x0050
      R1x0000
      R2x0000
      R3x0000
      R4x0000
      R5x0000
      R6x0000
      R7x0000
      N0
      Z1
      P0
    3. What is the total number of CPU clock cycles that this program will take to execute until it reaches the breakpoint? Note: You should refer to the state machine (pg 568) to determine how many cycles an instruction takes. Assume each state that access memory takes 5 cycles to complete and every other state takes 1 cycle to execute.
    Memory LocationValueInstructionCycles takes to exectue oncenumber of times executedTotal Cycles for instruction
    X3000 0101000000100000AND919
    X3001 0001000000100101ADD919
    X3002 0010001000000100LD15115
    X3003 0001000000000000ADD9436
    X3004 0001001001111111ADD9436
    X3005 0000001111111101Branch9 if not taken 10 if taken3 times taken 1 time not taken39
    Total Cycles 9+9+15+36+36+39 = 144