state diagram for an FSM for Overlapping Sequence Detector that detects sequence "11001" and raises a flag for two clock cycles

Question

I need to draw the state diagram for a Finite State Machine, FSM for an Overlapping Sequence Detector that detects sequence "11001" and raises a flag for two clock cycles. I can do it with two FSMs, interacting, but I'm supposed to do it with one FSM. The problem is when detecting an overlapping sequence like "110011001". Not sure how the state diagram would transition then with one FSM. Thank you for any help.

Answer 1

I assume by FSM you mean a Deterministic Finite Automaton (DFA).

This is solved classically by first constructing an Nondeterministic Finite Automaton (NFA) with that sequence to detect, then converting the NFA to a DFA using the Aho-Corasick algorithm.

In your example, the NFA can be constructed as:

{*}s0 -> {1}s1 -> {1}s2 -> {0}s3 -> {0}s4 -> {1}s5 (match)

The symbol {b}sN means state #N, if reachable, becomes active if the next input is value b (either 0 or 1). Note that s0 is always active for any input, and s5, if active, represents a match.

Given the above NFA, a DFA can be constructed following the Aho-Corasick algorithm. Note that this is a general approach that would allow you to detect not just one but multiple overlapping sequences.

Answer 2

To handle overlapping sequences you should separate detection and raising the flag. This can be done by using a shift-register with 5 bits, through which the incoming data is shifted. Your FSM (in state "idle") observes the shift-register and changes into the state "detected" when it detects your search pattern. The FSM stays in state "detected" until the search pattern disappears from the shift-register, then it changes into state "idle". Raising the flag can be done as a transition action (during transition from "idle" to "detected"). Perhaps use a tool like HDL-FSM-Editor to implement shift-register and FSM.

The shift-register solution would be universal for any pattern. If you would like to have a FSM for your fixed pattern, it could look like this: