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.
- Give the state transition table for the device. [20]
- Draw the corresponding state transition graph. [20]
- 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]
- 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]
- 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