Department of Electrical and Computer Engineering

The University of Texas at Austin

EE 306, Fall 2011
Problem Set 3 Solutions
Due: 26 September, before class
Yale N. Patt, Instructor
TAs: Faruk Guvenilir, Milad Hashemi, Jennifer Davis, Garrett Galow, Ben Lin, Taylor Morrow, Stephen Pruett, Jee Ho Ryoo

  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. Elevator Problem Revisted
    Recall the elevator controller problem on Problem Set 2. You were asked to design the combinational logic circuit for an elevator controller such that the option to move up or down by one floor is disabled. If there is a request to move only one floor, the elevator should remain on the current floor. For this problem, you will design the state machine for the sequential logic ciruit for an elevator controller which performs the same operation. You can assume that the building the elevator is in has 4 floors. The input to the state machine is the next requested floor. Each state will represent what floor the elevator is currently on. Draw a finite state machine that describes the behavior of the elevator controller. How many bits are needed for the inputs? How many bits are needed for the outputs?

    Two bits for input. There are technically no output bits, but there are 2 bits needed to represent the current state.

  5. (3.33)
    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 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.

  6. The figure below is a diagram of a 22-by-16-bit memory, similar in implementation to the memory of Figure 3.21 in the textbook. Note that in this figure, every memory cell represents 4 bits of storage instead of 1 bit of storage. This can be accomplished by using 4 Gated-D Latches for each memory cell instead of using a single Gated-D Latch. The hex digit inside each memory cell represents what that cell is storing prior to this problem.



    Figure 3: 22-by-16 bit memory
    1. What is the address space of this memory?
      22=4 memory locations.
    2. What is the addressability of this memory?
      16 bits.
    3. What is the total size in bytes of this memory?
      8 bytes.
    4. This memory is accessed during four consecutive clock cycles. The following table lists the values of some important variables just before the end of the cycle for each access. Each row in the table corresponds to a memory access. The read/write column indicates the type of access: whether the access is reading memory or writing to memory. Complete the missing entries in the table.

      WEA[1:0]Di[15:0]D[15:0]Read/Write
      001xFADEx4567Read
      110xDEADxDEADWrite
      000xBEEFx0123Read
      111xFEEDxFEEDWrite

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

  8. (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]