Design of a FSM two input detector sequence

Question

I'm designing a finite state machine (FSM) that detects the sequences "01011" and "00101" in a serial binary input. When either sequence is detected, the FSM should output (Y1, Y2) = (1,1).

enter image description here

Questions and Issues with the FSM

1. Where does the transition towards "001" happen?

   • In my diagram, S3 (001/010) represents both "001" and "010". However, I'm unsure if the transition from S2 (01) → S3 (001) is correctly defined.

2. How can I verify that the transitions are correct?

   • I want to test the FSM to ensure it correctly detects "01011" and "00101" without errors.
   • What’s the best way to do this? I considered manually creating a state/output table, but I’m unsure if it’s the most efficient method.
   • I also wrote a Python script to simulate it, but are there better tools for verifying FSM behavior?

3. Is this FSM implementation correct, or is there a better way to design it?

   • Is my approach correct, or are there logical errors in the states and transitions?
   • If there are mistakes, how can I improve the FSM to be more efficient and accurate?

I would appreciate any feedback or suggestions to refine the FSM design.

• PhiPhox: Which is already apparent: How does the FSM know that it should change to S5 from S3? There is also a loop to itself with the same condition. Also why are the nodes S5 & S6 needed? Furthermore if you are in S2 then you are effectively waiting for a "0" but discard all "1". So you aren’t detecting 01 but also 011111111 ...
• PhiPhox: For testing you can use e.g.: github.com/M4C4R/fsm-simulator
• Antonio51: Does a shift register make this work as well ...

Answer 1

Maybe this would do the job better?

enter image description here

The only thing that falls into the category it’s a feature not a bug is the scenario which 001011 triggers the recognition of Y2 AND Y1. But this is technically true, so?

And there is a bug, which recognizes 0101 as Y2.

If the bug isn’t acceptable, then you need two separate branches, cuz the only common sequence in both binary strings is 0101. But due to the fact that this is one time shifted to the right and padded with a 0 and the other time not shifted and appended by a 1, this makes it impossible to separate each of them distinctively by only looking at 0101. Basically i have written some kind of a 0101 detector which is the closest you can get without two branches for each binary.

FSMs are good at finding recursive patterns, but aren’t good for exact matches, then they become really big and chunky.

Answer 2

The state diagram has 2 arrows leaving state S3 when the input is 0. I only expect to see one arrow leaving it when the input is 0. You should take a closer look at that.

I expect to see arrows leaving states S5 and S6 when the input is 0, but there are none.

I also expect to see arrows leaving state S4, but there are none.

Just by visual inspection, it looks like it properly detects 01011 (assuming you get rid of the S3 self-return arc), but not 00101. The input sequence 001 gets you to S6, but there is no way to leave S6 when the next input is 0 (0010).

It does not seem like you need 2 outputs since both have the same values according to your diagram.

I do not know of a direct way to automatically verify that a bubble diagram is correct. However, a common way to verify state machine designs is to use a hardware description language, like Verilog. If you have not used Verilog, there will be a learning curve. Here is an example.

• PhiPhox: To improve it, the OP should also introduce an error node.
• PhiPhox: Could you please also include what i mentioned at the very end of my comment to the OP? Then i think your answer is very much complete.
• PhiPhox: No, i mean the other comment, that 01 is detected as well as 0111111 and so on. Because S2 is waiting to get a 0 and not terminating at a 1. This is clearly a mistake in the graph. Sorry for the confusion (i forgot, that i posted two comments).
• PhiPhox: 01011 is detected but 011011 as well and 0111011 and so on and so forth. I think, that therefore 01011 isn’t properly detected, cuz false positives are likely (due to self-return arc at state S2).