Sequence detector FSM in VHDL - Step-by-Step Execution

Concept Flow - Sequence detector FSM in VHDL

Start: Idle State

↓

Input bit arrives

↓

Check current state and input

↓

Transition to next state

↓

If sequence detected?

Yes→Output=1

↓

Reset output

↓

Wait for next input

The FSM waits in an idle state, reads input bits one by one, changes states based on input and current state, and outputs 1 when the target sequence is detected.

Execution Sample

VHDL

library ieee;
use ieee.std_logic_1164.all;

entity seq_detector is
  port(clk, rst, din: in std_logic;
       dout: out std_logic);
end seq_detector;

This code defines the start of a sequence detector FSM entity with clock, reset, input, and output signals.

Execution Table

Step	Current State	Input (din)	Next State	Output (dout)	Reason
1	S0	0	S0	0	No sequence start, stay in idle
2	S0	1	S1	0	First bit of sequence detected
3	S1	1	S2	0	Second bit detected, move forward
4	S2	0	S3	0	Third bit detected, continue
5	S3	1	S4	0	Fourth bit detected, almost done
6	S4	1	S1	1	Sequence detected, output 1 and partial overlap
7	S1	0	S0	0	Input breaks sequence, reset to idle
8	S0	0	S0	0	Idle state, no sequence start
Exit	-	-	-	-	No more input or reset triggered

💡 FSM stops when no more input bits or reset is activated.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
Current State	S0	S0	S1	S2	S3	S4	S1	S0	S0
Input (din)	-	0	1	1	0	1	1	0	0
Output (dout)	-	0	0	0	0	0	1	0	0

Key Moments - 3 Insights

Why does the FSM output 1 only at step 6 and not before?

Because the FSM only outputs 1 when the full target sequence is detected, which happens at step 6 as shown in the execution_table row 6.

Why does the FSM go back to state S1 at step 6 instead of S0?

The FSM supports overlapping sequences, so after detecting the sequence, it moves to S1 to check if the next input can start a new sequence immediately, as shown in execution_table step 6.

What happens if the input breaks the sequence in the middle?

The FSM resets to the idle state S0, as seen in step 7 where input 0 breaks the sequence and state returns to S0.

Visual Quiz - 3 Questions

Look at the execution_table, what is the output (dout) at step 4?

A 1

B -

C 0

D Undefined

💡 Hint

Check the Output (dout) column in execution_table row 4.

At which step does the FSM detect the full sequence and output 1?

A Step 6

B Step 5

C Step 3

D Step 7

💡 Hint

Look for the row where Output (dout) changes to 1 in execution_table.

If the input at step 7 was '1' instead of '0', what would be the next state?

A S1

B S2

C S4

D S0

💡 Hint

Refer to the transition logic shown in variable_tracker and execution_table for input '1' at state S1.

Concept Snapshot

Sequence Detector FSM in VHDL:
- Uses states to track input bits.
- Transitions depend on current state and input bit.
- Outputs 1 when full sequence detected.
- Supports overlapping sequences by smart state transitions.
- Reset returns FSM to idle state.

Full Transcript

This visual execution shows a sequence detector FSM written in VHDL. The FSM starts in an idle state S0 and reads input bits one by one. Depending on the current state and input bit, it moves to the next state. When the full target sequence is detected, the FSM outputs 1. The FSM supports overlapping sequences by moving to an intermediate state after detection. If the input breaks the sequence, the FSM resets to idle. The execution table traces each step with current state, input, next state, and output. The variable tracker shows how states and outputs change over time. Key moments clarify why output happens only after full detection and how overlapping sequences are handled. The quiz tests understanding of output timing, detection step, and state transitions with different inputs.

Practice

1. What is the main purpose of a sequence detector FSM in VHDL?

easy

A. To perform arithmetic operations

B. To generate random numbers

C. To detect a specific pattern of bits in a serial input stream

D. To store large amounts of data

Solution

1. Step 1: Understand FSM role

   A sequence detector FSM is designed to watch input bits and identify a particular pattern.

2. Step 2: Match purpose with options

   Only To detect a specific pattern of bits in a serial input stream describes detecting a pattern in a bit stream, which matches the FSM's purpose.

3. Final Answer:

   To detect a specific pattern of bits in a serial input stream -> Option C

4. Quick Check:

   Sequence detector FSM = Pattern detection [OK]

Hint: FSMs track input patterns step-by-step [OK]

Common Mistakes:

• Confusing FSM with memory storage
• Thinking FSM generates data
• Assuming FSM does math operations

2. Which VHDL construct is typically used to represent the states in a sequence detector FSM?

easy

A. signal

B. type (enumeration)

C. process

D. variable

Solution

1. Step 1: Identify how states are defined

   States in FSMs are usually defined as an enumerated type listing all possible states.

2. Step 2: Match with VHDL constructs

   Only 'type (enumeration)' fits this use, as it defines named states clearly.

3. Final Answer:

   type (enumeration) -> Option B

4. Quick Check:

   States = enumerated type [OK]

Hint: Use enumerated types to name FSM states clearly [OK]

Common Mistakes:

• Using signal or variable to define states directly
• Confusing process with state definition
• Not using enumeration for states

3. Given this VHDL snippet for a sequence detector FSM, what is the output when input sequence is 1,0,1,1?

type state_type is (S0, S1, S2, S3);
signal state: state_type := S0;
signal detected: std_logic := '0';

process(clk)
begin
  if rising_edge(clk) then
    case state is
      when S0 =>
        if input_bit = '1' then
          state <= S1;
        else
          state <= S0;
        end if;
        detected <= '0';
      when S1 =>
        if input_bit = '0' then
          state <= S2;
        else
          state <= S1;
        end if;
        detected <= '0';
      when S2 =>
        if input_bit = '1' then
          state <= S3;
        else
          state <= S0;
        end if;
        detected <= '0';
      when S3 =>
        detected <= '1';
        state <= S0;
    end case;
  end if;
end process;

medium

A. detected = '1' after the second input

B. detected = '1' after the third input

C. detected = '0' for all inputs

D. detected = '1' after the fourth input

Solution

1. Step 1: Trace FSM states with inputs

   Input sequence: 1 -> S0 to S1, detected=0; 0 -> S1 to S2, detected=0; 1 -> S2 to S3, detected=0; 1 -> S3 outputs detected=1 and resets to S0.

2. Step 2: Identify when detection occurs

   Detection signal '1' is set only in state S3, which happens after the fourth input.

3. Final Answer:

   detected = '1' after the fourth input -> Option D

4. Quick Check:

   Detection on full pattern completion = after 4th input [OK]

Hint: Trace states stepwise with inputs to find detection timing [OK]

Common Mistakes:

• Assuming detection happens too early
• Ignoring state reset after detection
• Confusing input bits with states

4. Identify the error in this VHDL FSM snippet for a sequence detector:

process(clk)
begin
  if rising_edge(clk) then
    case state is
      when S0 =>
        if input_bit = '1' then
          state <= S1;
        else
          state <= S0;
        end if;
        detected <= '0';
      when S1 =>
        if input_bit = '0' then
          state <= S2;
        else
          state <= S0; -- Error here
        end if;
        detected <= '0';
      when S2 =>
        if input_bit = '1' then
          state <= S3;
        else
          state <= S0;
        end if;
        detected <= '0';
      when S3 =>
        detected <= '1';
        state <= S0;
    end case;
  end if;
end process;

medium

A. Resetting to S0 on wrong input in S1 breaks overlapping detection

B. Missing clock sensitivity list

C. Detected signal should be '1' in all states

D. State S3 is not defined

Solution

1. Step 1: Analyze state transitions in S1

   Resetting to S0 on wrong input in S1 prevents the FSM from detecting overlapping sequences.

2. Step 2: Understand impact on sequence detection

   Proper overlapping detection requires transitioning to S1 or another state, not always S0, to catch patterns starting inside previous ones.

3. Final Answer:

   Resetting to S0 on wrong input in S1 breaks overlapping detection -> Option A

4. Quick Check:

   Overlapping detection needs careful state transitions [OK]

Hint: Check if FSM allows overlapping pattern detection [OK]

Common Mistakes:

• Ignoring overlapping sequences
• Assuming detected signal always '1'
• Forgetting clock edge sensitivity

5. You want to design a sequence detector FSM in VHDL that detects overlapping occurrences of the pattern "1011". Which approach correctly handles overlapping detection?

hard

A. After detecting full pattern, transition to the state representing the last '1' to allow overlap

B. Reset to initial state after detection to start fresh

C. Use a counter instead of states to track bits

D. Ignore overlapping sequences to simplify design

Solution

1. Step 1: Understand overlapping detection

   To detect overlapping patterns, FSM must not reset fully but keep track of partial matches.

2. Step 2: Choose correct state transition

   Transitioning to the state representing the last matched bit (here, last '1') allows the FSM to continue detecting overlapping sequences.

3. Final Answer:

   After detecting full pattern, transition to the state representing the last '1' to allow overlap -> Option A

4. Quick Check:

   Overlap detection = partial state retention [OK]

Hint: Keep FSM in partial match state after detection for overlaps [OK]

Common Mistakes:

• Resetting FSM fully after detection
• Using counters instead of states
• Ignoring overlapping patterns