Sequence detector which detects sequences 100 and 111

Question

I need to design a pattern detector that recognizes 100 and 111 bit patterns, even overlapping ones. I drew the state diagram as shown in the image

and created the related table

Could you tell me if it is correct? I also wanted to ask if the number of states is related to the number of bits (in this case the sequences are 3 bits, but could be for example 5) or if it comes from other data.

Answer 1

In this particular case, I recommend you to use a serial-in parallel-out register. With it you would only need to connect the serial input to the data stream, connect the shift clock to the same clock your data uses to change state and then using the first n bits of the parallel output to apply your logic.

As data is being inputted serially, every cell in the shift register is being replaced by the next one. As the logic would only check three consecutive bits it would always find all occurrences, without caring about them being overlapped.

There are other ways, like designing an automat as you are already doing; but that may not be necessary as the logic you describe does not seem to alter the states of the fsm and just generates the output (therefore doing exactly the same).

In your case with your 3-bit sequence equation would be:

Result = Bit_2 AND (Bit_1 XNOR Bit_0)

Why this equation? Assuming you need an active high output (result is true if conditions met) you will always require the higher bit to be 1. About the other two, you don't care about the exact value of them but both must be equal. Gate XOR always returns true if different, therefore using its complementary (XNOR) we will obtain a true if its inputs are equal.

To complement this wall of text, I append this schematic for refference:

^{simulate this circuit – Schematic created using CircuitLab}

Answering to your last comment in your question: if you wanted to expand the circuit and check for more bits, more stages of the shift register shall be used and logic modified. The number of stages you would be using is the number of bits of your pattern minus one, which is taken directly from the input.

I hope it helps