CS61C Homework 5

Synchronyous Digital Systems

Due:2006.10.25 @ 11:59pm
TA:Scott <cs61c-tb@imail.eecs.berkeley.edu>



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


Question 1

What is Moore's law? The Intel Pentium 4 Prescott (3.6 Ghz version), released in 2004, has roughly 125,000,000 transistors on the chip. This chip can perform about 7,000 MIPS (Millions of Instruction Per Second). Based on this information and your knowledge of Moore's law, how many transistors do you think the Intel 8088, which was released in 1979, had on the chip? What would you estimate the MIPS rating of this chip to be?

Question 2


Consider the circuit of Flip-Flops (FF) shown here. Assume that input X alternates between 1 and 0, changing at the falling edge of each 50 ns clock period and initializing as 0. Draw the detailed wave for the clock signal, input X, and the signals at points A, B, C, and D in the circuit for the first 5 clock cycles after startup. Assume that the clk-to-q delay is 7ns.

Question 3


Consider the accumulator discussed in the readings and presented in class. Given the following: The adder propagation delay is 2ns, the register setup time is 1 ns, the register clk-to-q is 1ns, and the clock frequency is 500MHz. Will the accumulator function correctly? If not, what would you suggest changing to fix the problem?

Question 4

Design a finite state machine (FSM) with the following behavior: Inputs arrive one bit at a time, one bit per clock cycle. The FSM outputs a 1 if the pattern '110' has been recognized and continues to output a 1 as long as bits matching that pattern continue to be input. The FSM should output 0 at all other times. (ie. '110110...' will continue to output 1 after it starts to do so, but '110111...' will start outputing 1 after the 3rd input but start outputing 0 again after the 6th . '110' will output a 1, trusting that the next input will be a '1'.) Your FSM should include a start state, but you need not worry about initialization other than that.

Do your design in three steps. First, draw the state diagram, second specify the truth table for next state and output based on present state and input, finally devise the circuit-level implementation.

Question 5


Derive the truth-table for the CL circuit shown here. (Remember, you do this by applying all possible input combinations, one at a time). What is the most simplified version of the expression that this circuit/truth-table generates?

Question 6

Write the canonical sum-of-products form of a Boolean expressions for a 3 input function whose output is 1 if and only if the number of 1's in the input is even.

Question 7

Write the most simplified Boolean expression for the function represented by the truth-table below. SHOW ALL YOUR WORK! The solution is the OR of three AND terms, each with 2 variables.

000 0
001 0
010 0
011 1
100 0
101 1
110 1
111 1

Question 8

Redraw the complete UNSIMPLIFIED circuit diagram from problem 5 using only NAND gates. You must show all the gates used (that is to say, you can not include larger structures in your diagram). Show all your work to derive this structure.

Submission Details

Create a directory named 'hw5' containing a README and any additional files needed for your submission. While in that directory, run 'submit hw5'. If you included an image, make sure to say "yes" when the submit script prompts you about it. Please only submit images in the following formats: GIF, JPG, and PDF.