Sequence Detector - Solution

The solution for the problem is given here.

Sequence Detector

Design a state machine, that outputs a '1' one and only when two of the last 3 inputs are '1'. For example, if the input sequence is 0110_1110 then the output will be 0011_1101. Assume that the input 'x' is a single bit serial line.

Counter design using FSM

Design a 3-bit counter that counts in binary or in Gray code, depending on the values of a “mode control input”. This synchronous 3-bit counter has a mode control input m. As long as m = 0, the counter steps through the binary sequence 000, 001, 010, 011, 100, 101, 110, 111 and repeats this sequence. As long as m = 1, the counter advances through the Gray code sequence 000, 001, 011, 010, 110, 111, 101, 100 and repeats this sequence. However, it is possible that the mode input changes at any time in any of these sequences.

For example, assume that the mode input is 0 for the first two clock cycles but changes to 1 in the third clock cycle and stays at 1 in the fourth clock cycle. (That is, m goes through the sequence 0, 0, 1, 1.) Then, the output will be 000, 001, 010, 110, 111. In this example, 000 is the initial state. The first two state transitions (000->001->010) occurs in the binary counting mode. Then, because m = 1 from the third clock cycle onwards, the state goes from 010->110->->111, as indicated in the Gray code sequence.

In addition to the mode control input, there is a reset input. This synchronous counter should go to the 000 state if asserted.

FSM Problem

Construct a synchronous moore state machine with two inputs, A and B, and two outputs, X and Y. The machine accepts data on two input lines synchronously with the clock. The output X is 1 if and only if the data on the two input lines have been identical (i.e. A and B are both 1, or A and B are both 0) for the last three or more consecutive clock cycles. Output Y is 1 if and only if the data on the two input lines have been complements of each other (i.e. A = 1 and B = 0, or A = 0 and B = 1) for the last three or more consecutive clock cycles.