CS61C Summer 2012 Homework 4

Due Wednesday, July 25, 2012 @ 11:59pm

Updates

Goals

This assignment will check your understanding of synchronous digital systems, state elements, combinational logic, and CPU control and datapath.

Submission

Submit your solution by creating a directory named hw4 that contains hw4.txt and hw4fsm.circ. (File names are case-sensitive and the submission program will not accept your submission if your file names differ at all from those specified) From within that directory, type submit hw4. Partners are not allowed on this assignment.

Copy the contents of ~cs61c/hw/4 to a suitable location in your home directory to obtain files you will want for this homework.

	$  cp -r ~cs61c/hw/04/ ~/hw4 

Exercises

Problem 1: Waveform Diagrams - 2 pts


waveform circuit.jpg

Consider the circuit of Flip-Flops (FF) shown here. Assume that input X alternates between 1 and 0, 25ns after every rising edge. Initially, X is 0 (so 25ns after the first rising edge it should be 1) while A, B, C, and D are unknown. Assume one clock cycle is 75 ns. Given the clock signal, draw the wave for input X, and the signals at points A, B, C, and D in the circuit for the first 6 clock cycles. Assume that the clk-to-q delay is 10 ns and a hold time of 5ns. Assume that Flip-Flops take their new value on the rising edge of the clock cycle. Assume time = 0 on the first rising edge. Note the NOT gate that precedes B (you may ignore propagation delay for this problem).

Answer the following questions. You would want to fill out the waveform diagram below to help though you don't have to submit it. Consider six clock cycles (so six rising edges) as shown in the diagram. Assume the diagram is cut off 5ns after the last rising edge.
Assume A,B,C and D are unkown at the start of the diagram below.

waveform.gif
  1. How many times does the value at B change (changing from undetermined to 1 or 0 counts as one)?
  2. How many times does the value at D change (changing from undetermined to 1 or 0 counts as one)?
  3. At which time(s) does the value at A becomes stable at 1 (changes from 0/undetermined to 1)?
  4. At which time(s) does the value at C becomes stable at 0 (changes from 1/undetermined to 0)?

Problem 2: Clock Frequency - 2 pts

Consider this circuit. It accumulates two arguments at a time. You are given the following: the adder propagation delay is 4 ns, the register setup time is 2 ns, the register clk-to-q delay is 1 ns, and the clock frequency is 50 MHz.

clock frequency circuit.jpg
  1. Would this accumulator work properly? Show your work.
  2. Describe change(s) that would allow the circuit to work with double the clock rate. You may not change the timing characteristics of the adders or register.

Problem 3: Simple FSM and Truth Tables - 2 pts

Design an FSM that would take an infinite stream of bits and output 1 only if it has seen both a 1 and a 0 ever before including the last input bit. Then convert it into a truth table mapping each state and input to a next state and an output. Name the states meaningfully so that it is easily understandable (for example, Seen0). You should have four states only. You only need to submit the truth table; you do not need to submit your drawing of the FSM.

Problem 4: Truth Tables, Boolean Algebra, FSMs, Logic Circuits - 3 pts

Consider the following finite state machine.
  1. Come up with the MOST simplified boolean expressions for determining bits for the next state and the output bit given the current state and the input bit. You should have 3 expressions. (You might want to first construct a truth table.)
  2. Complete the circuit hw4fsm.circ. The circuit should model the given FSM. It should have one output bit that depends on one input bit (and the state which you'll have to keep track of). You'll need a register to keep track of state. The clock input should be tied to the register. It's a simple FSM so you can test it by using the 'Poke' tool to toggle the clock and the input bit. To make the circuit simpler, instead of having the state machine start at state 01 as shown, you may assume it starts at state 00 for this part.
  3. fsmCompute takes one bit at a time as input. Fill in the blank below so that it returns the same bits as what the FSM would output given a series of input bits.
    	/*
    		Assume x is either a 0 or a 1.
    	*/
    	int fsmCompute(int x) {
      		static unsigned int numState = 0xFFFFFFFF;
      		numState = (numState << 1) + x;
      		return _________________________;
    	}
    	

Problem 5: Datapath+Control - 3 pts

Consider the simple single-cycle datapath . The following table describes the control signals for several instructions: (See the textbook or lecture slides for more detailed descriptions of the signals.)

Instruction RegDst ALUSrc MemToReg RegWrite MemRead MemWrite Branch
addu 1 0 0 1 0 0 0
lw 0 1 1 1 1 0 0
sw X 1 X 0 0 1 0
beq X 0 X 0 0 0 1

Suppose we wish to add the instructions

  1. jr (jump register) and
  2. sll (shift left logical)
to the datapath.
  1. List any necessary additional signals and muxes in the current single-cycle datapath. Be brief for each signal; include from where it comes from, to where it goes, and what it is for.
  2. Then expand the table above to include a jr row and a sll row as well as additional columns for any control signals that you might have added.
  3. A friend is proposing to modify this single-cycle datapath by eliminating the control signal MemToReg. The multiplexor that has MemtoReg as an input will instead use ALUSrc. Will your friend's modification work? What about replacing the MemToReg signal with the MemRead control signal? Explain. Make sure to consider other instructions we've seen (rather than the ones just listed here).