CS61C Spring 2014 Homework 4

Due Sunday, April 6, 2014 @ 23:59:59

Goals

This assignment will help you cement your understanding of synchronous digital systems, state elements, and combinational logic.

Submission

Submit your solution by creating a directory named hw4 that contains hw4.txt. (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/04 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 - 4 pts


waveform circuit.jpg

Consider the circuit of Flip-Flops (FF) shown here. Assume that input X alternates between 1 and 0, 20ns after every rising edge. Initially (at the start of the timing diagram), X is 1 (so 20ns after the first rising edge it should be 0) while A, B, C, and D are unknown. Assume one clock cycle is 60 ns. Given the clock signal, draw the wave for input X, and the signals at points A, B, C, and D in the circuit. 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 only the six rising edges shown in the diagram and that the diagram is cut off 5ns after the last rising edge.

  1. How many times does the value at B become stable at 1 (in other words, transition from 0 or undetermined to 1)?
  2. How many times does the value at D become stable at 0?
  3. At which time(s) does the value at A becomes stable at 1?
  4. At which time(s) does the value at C becomes stable at 0?

waveform.gif

Problem 2: Clock Frequency - 4 pts

Consider this circuit. It accumulates two values at a time, arriving at each clock period after a clk-to-q delay. 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, the register hold time is 1ns, and the clock frequency is 50 MHz.

  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. (Hint: it'll take more than just adding a register between the adders).

clock frequency circuit.jpg

Problem 3: Simple FSM and Truth Tables - 4 pts

Design an FSM that would take an infinite stream of bits and output 1 only if it has seen the pattern '10' (including the last two input bits). 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; 00 is not meaningful enough). You should have three 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 - 10 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. s1 is the left bit and s0 is the right.
  2. fsm() takes one bit at a time as input and returns 0 or 1. Fill in the blanks below so that it behaves as according to the FSM above.

        /*
         * Assume x is either a 0 or a 1.
         */
        int fsm(int x) {
            int retval;
            static unsigned int state = 0x1;
            retval = _______________________;
            state  = _______________________;
            return retval;
        }
    	

Problem 5: Some More Boolean Algebra - 3 pts

Write a formula in Boolean algebra to define the logical function that takes as input 32 bits x0,...,x31, and evalutes to 1 if and only those bits correspond to an I-type instruction. Assume that x0 is the most significant bit of the instruction. Note that this is a different convention from the one on the Green Card. Your formula need not involve all the input bits.
(Hint: It might be easier to start off by figuring out what instructions aren't I-types, and then go from there)