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. 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 from 0 at the point labeled t0 (last updated - 09/26/08).
   Question: What is the state after 50 cyles. How many cycles does it take for a specific state to show up again?
   
   

2. The table below is the truth table for a digital circuit with inputs A, B, C and output Y. Prove that this circuit is logically complete by implementing AND, OR and NOT functions using this circuit. Section 3.3.5 on page 64 of your book discusses logical completeness.

   A	B	C	Y
   0	0	0	1
   0	0	1	1
   0	1	0	0
   0	1	1	1
   1	0	0	0
   1	0	1	1
   1	1	0	1
   1	1	1	0

   Hint: NOT(A) OR (A AND NOT(B)) = NOT(A AND B) Another Hint: What happens if you have two inputs, call them a and b, and apply one of them to two of the inputs to the logic circuit in question and the other one to the third input to the logic circuit. What two-input function does the logic circuit produce? (last updated - 09/24/08)

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

4. 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?
   (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?
   (c) Why might part b be a better way to specify the state?

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

6. (3.31)
   If a particular computer has 8 byte addressability and a 4 bit address space, how many bytes of memory does that computer have?

7. (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. Implement G, E and L for a 1-bit comparator using AND, OR, and NOT gates.
   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.)
      

8. 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	x3001
   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.

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