(b) Draw a Truth Table for the function indicating when the computer
tape drive should be running.(10pts)
Your task is to construct a synchronous finite state machine (FSM) for SETI that can perform this pattern matching automatically.
The input data to the FSM is a serial bitstream which represents the data being received from the radar telescope. That is, the input is a binary digit (0/1) which can change on every tick of the machine's clock. On the first clock cycle, the first bit from the telescope is received, then on the second clock cycle, the second bit is received, and so on.
The output of the FSM should be a single bit which indicates a pattern match. The desired pattern is 011, repeated twice; that is, the FSM should indicate a match (1 out) any time the bitstream contains a 0, followed by a 1 on the next clock tick, which in turn is followed by a 1 on the subsequent clock cycle, then a 0 on the next cycle, followed by a 1 on the next, then finally a 1 again.
Your boss at SETI suggests a Mealy machine be used for simplicity, although this is not required.
Hand in the following:
(a) A state diagram for the FSM. Assume a single state transistion
will happen at each clock tick. Be sure to indicate the reset state
on your diagram. (25 pts)
(b) The state transition table corresponding to the state diagram.
Try to perform some state assignment (that is, give each state some binary
encoding), but don't worry about deriving the ``best'' assignment. (15
pts)
Bonus: Your boss at SETI wants you to come up with a circuit
which performs the same task which only uses one D- latch,a 2-bit shift
register and no more than 6 gates (government cutbacks have drained
SETI's research funds). Hint: the problem can be formulated as follows:
the output should indicate a match when 011 has been seen, followed by
the input from two clock cycles ago was a 0, the input from the
previous clock cycle was a 1, and the current input is a 1.
(10 bonus points; not required)