Computer Science 150 Homework Assignment 3
Spring 1997

Due: Thursday, February 27, 5:00 pm

The numbers in brackets [ ] denote the relative marks assigned for each question.


Your boss (at SETI) wants you to analyze an electronic device she found in her backyard last week. She thinks it might be a piece of an alien spaceship which fell out of the sky, and she wants you to find out exactly what the device does. An x-ray scan of the device shows the following circuit:

Your boss points out the similarity between the unearthly device and a typical (human-built) Mealy machine.

  1. Give the state transition table for the device. [20]
  2. Draw the corresponding state transition graph. [20]
  3. What will the bit pattern at the output of the device look like for an input serial bit sequence of 0100011101? Assume each input bit is available at the rising edge of the clock signal, and the FSM (er, alien device) starts with 0 in both flip-flops. Also, what will be the contents of the flip-flops after this sequence? [20]
  4. Suppose you had a cutting laser which can destroy a gate so that it constantly outputs a 0 (independent of the gate inputs). How could you use this to modify the circuit so that the output is 0 for the case when both flip-flops contain 0? That is, the modified circuit should behave exactly the same as the original circuit, except for when the state is 00. When the state is 00, the output should be 0 for the modified circuit. [20]
  5. Suppose you were not allowed to destroy the existing circuit in any way or modify any of the existing gates; you may only add additional gates at the output. How could you modify it to behave as described in the previous part? Assume you have access to the signals S0 and S1. [20]

pchong@cory.eecs.berkeley.edu