Skip to content
Tutorials Center
My learning

Topics

Lesson 23 of 37 ยท Finite State Machines

A Sequence Detector FSM

Design a serial 1011 sequence detector in VHDL as a Mealy and Moore FSM, with state diagram, overlapping detection, and runnable C stand-ins to test it.

A sequence detector watches a serial bit stream, one bit per clock edge, and raises an output when a chosen pattern has just arrived. Packet headers, start-of-frame markers and keypad codes are all found this way. It is the classic FSM exercise because it forces you to think about what the machine must remember.

We design a detector for the pattern 1011 that allows overlap: in 1011011 the pattern appears twice, and the two matches share one bit (the fourth bit ends the first match and starts the second). As usual, VHDL is read-only on this site; the C programs are runnable models of the same machine.

Deciding the states

A state answers: "how much of the pattern have I matched so far?"

  • S0: nothing useful matched yet.
  • S1: matched 1.
  • S10: matched 10.
  • S101: matched 101.
  • The final 1 completes the match (output pulse).

Transitions come from asking, "what is the longest suffix of the bits seen so far that is also a prefix of 1011?"

State Input 0 Input 1
S0 S0 S1
S1 S10 S1
S10 S0 S101
S101 S10 S1 (match!)

Check the overlap case: after 1011 the last bit leaves us with suffix 1 which is a prefix of the pattern, so we go to S1, not S0. From S101 on input 0 the bits end in 1010, whose longest matching prefix is 10, so we go to S10.

flowchart LR
  S0(["S0"]) -->|"1"| S1(["S1"])
  S0 -->|"0"| S0
  S1 -->|"0"| S10(["S10"])
  S1 -->|"1"| S1
  S10 -->|"1"| S101(["S101"])
  S10 -->|"0"| S0
  S101 -->|"0"| S10
  S101 -->|"1 / match"| S1

Mealy detector: the output is 1 on the last transition (S101 with input 1).

The Mealy VHDL

The Mealy output reads the input, so the detector reacts in the same clock cycle as the final bit.

VHDL
library ieee;
use ieee.std_logic_1164.all;

entity seq1011 is
  port (clk, rst, din : in std_logic;
        found : out std_logic);
end entity;

architecture mealy of seq1011 is
  type state_t is (S0, S1, S10, S101);
  signal state, nxt : state_t;
begin
  process (clk)
  begin
    if rising_edge(clk) then
      if rst = '1' then state <= S0; else state <= nxt; end if;
    end if;
  end process;

  process (state, din)
  begin
    nxt   <= state;
    found <= '0';
    case state is
      when S0   => if din = '1' then nxt <= S1; end if;
      when S1   => if din = '0' then nxt <= S10; end if;
      when S10  => if din = '1' then nxt <= S101; else nxt <= S0; end if;
      when S101 =>
        if din = '1' then nxt <= S1; found <= '1';
        else nxt <= S10; end if;
    end case;
  end process;
end architecture;

This is exactly the two-process style. Every branch is reached with defaults set at the top, so no latches appear.

Running the machine in C

The table above becomes an array. The program feeds a bit string through the machine and prints the position where each match ends.

C C stand-in: Mealy 1011 detector with overlap

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

You should see matches ending at the 4th, 7th (overlap), 12th and 16th bits.

Moore version

A Moore detector needs a state that means "match found". Add S1011, from which the next transitions equal those of S1 (because the trailing 1 is the start of a new pattern):

State Input 0 Input 1 Output
S0 S0 S1 0
S1 S10 S1 0
S10 S0 S101 0
S101 S10 S1011 0
S1011 S10 S1 1

Check S1011 on input 0: the bits end in 10110; the suffix 10 is a prefix of the pattern, so go to S10. On 1: suffix 1, so S1.

The Moore output asserts one clock cycle after the last bit arrives, and is a pure function of state, so it is naturally glitch-free.

C C stand-in: Moore detector, output one cycle later

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

Compare the two outputs: same matches, shifted by one position (the Moore line has no fourth mark because that match would show one edge after the stream ends).

Non-overlapping variant

If detections must not share bits (after a match, start from scratch), change the transitions out of the matching transition to go to S0 instead of S1. It is a single change in the table and a good exercise.

Testing strategy

A detector is easy to test thoroughly. Compare it against a reference that does string search: the testbench lesson (Self-Checking Testbenches) shows how to build one. Cases to cover: exact pattern, pattern at start and end of the stream, overlaps, near misses (1010, 0111), reset in the middle of a pattern.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. After the detector matches 1011, which state should it enter for overlapping detection?

    The final 1 can be the first bit of a new 1011, so the machine continues from S1.
  2. 2. In the Mealy design, when is found asserted?

    The Mealy output is a function of the state S101 and the current input 1.
  3. 3. Why does the Moore version need an extra state?

    With no dependence on the input, 'match found' has to be encoded in the state itself.
  4. 4. From S101 on input 0, the next state is S10 because

    The state records the longest suffix of the history that is still a prefix of the pattern.

Summary

  • States record how much of the pattern is matched: the longest suffix that is a prefix.
  • Mealy detectors flag the match in the same cycle; Moore detectors one cycle later.
  • Overlap means returning to the state of the matching prefix, not to the start.
  • Build a table first, then code it with the two-process style.
  • C stand-ins confirm the table before you write any VHDL.

Next: Your First Testbench