The Search for Extra-Terrestrial Intelligence (SETI) collects vast amounts of data from radar telescopes and compares the signals received from other planets to signals which intelligent beings might use. If a match is found between the measured signal and an ``intelligent'' pattern, then it is likely that some other life form created that signal.
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; the FSM should indicate a match 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.
Your boss at SETI suggests a Mealy machine be used for simplicity, although this is not required.
Hand in the following:
- 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]
- 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]
Bonus: Your boss at SETI wants you to come up with a circuit which performs the same task which only uses a 2-bit shift register and no more than 4 gates (government cutbacks have drained SETI's research funds). Hint: the problem can be formulated as follows: the output should indicate a match when 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]
NAND gates and NOR gates are simple to construct using today's digital circuit technology; AND and OR are more complex. As a result, modern digital circuit designers usually use NAND and NOR far more often than AND and OR.
- Show how the NOT, AND and OR functions can be implemented using just NAND gates. You may use as many NAND gates as you wish for each of these. Hand in the schematics. [15]
- Show how the NOT, AND and OR functions can be implemented using just NOR gates. You may use as many NOR gates as you wish for each of these. Hand in the schematics. [15]
Sketch the output (Q) you expect to get when the following input is applied to a positive edge-triggered J-K flip-flop. Show the inputs as well; you can print this page out and just draw on the diagram below. Assume the output begins at 0. [30]
