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

Concept Flow - Sequence detector FSM

Start: Wait for input bit

↓

Check current bit

↓

Update FSM state

↓

Check if sequence detected?

No→Wait for next bit

Yes↓

Output: Sequence detected signal

↓

Reset or continue detecting

The FSM reads input bits one by one, updates its state based on the sequence progress, and signals when the target sequence is detected.

Execution Sample

Verilog

module seq_detector(
  input clk, reset, in_bit,
  output reg detected
);
  // FSM states and logic here
endmodule

This Verilog module detects a specific bit sequence on input 'in_bit' and sets 'detected' high when found.

Execution Table

Step	Input bit	Current State	Next State	Detected Output
1	1	S0	S1	0
2	0	S1	S2	0
3	1	S2	S3	0
4	1	S3	S1	1
5	0	S1	S2	0
6	1	S2	S3	0
7	0	S3	S0	0
8	1	S0	S1	0
Exit	-	-	-	Sequence detection ends or continues

💡 FSM continues reading bits until reset; detection output signals when sequence matched.

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	After Step 8
Current State	S0	S1	S2	S3	S1	S2	S3	S0	S1
Detected Output	0	0	0	0	1	0	0	0	0

Key Moments - 2 Insights

Why does the FSM go back to state S1 after detecting the sequence instead of resetting to S0?

The FSM returns to S1 to allow overlapping sequences detection, as shown in execution_table step 4 where next state is S1 after detection.

Why is the detected output '1' only at step 4 and not at other steps?

Detected output is '1' only when the full sequence is matched, which happens at step 4 according to the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table, what is the FSM state after input bit '0' at step 2?

A S1

B S2

C S0

D S3

💡 Hint

Check the 'Next State' column at step 2 in the execution_table.

At which step does the FSM output 'detected' signal as '1'?

A Step 4

B Step 5

C Step 3

D Step 6

💡 Hint

Look at the 'Detected Output' column in the execution_table.

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

A S0

B S2

C S1

D S3

💡 Hint

Refer to the pattern of state transitions in the execution_table and variable_tracker.

Concept Snapshot

Sequence Detector FSM in Verilog:
- Reads input bits sequentially
- Updates state based on partial sequence matched
- Outputs 'detected' when full sequence found
- Supports overlapping sequences by smart state transitions
- Uses states like S0, S1, S2, S3 to track progress

Full Transcript

This visual execution shows a sequence detector FSM in Verilog. The FSM starts at state S0 and reads input bits one by one. Each input bit causes a state update reflecting how much of the target sequence has been matched. When the full sequence is detected, the FSM outputs a 'detected' signal set to 1. The FSM then transitions to a state that allows detection of overlapping sequences. The execution table traces each step with input bit, current state, next state, and output. The variable tracker shows how the FSM state and output change after each input. Key moments clarify why the FSM returns to certain states and when the output is set. The quiz tests understanding of state transitions and output timing. This helps beginners see exactly how the FSM processes inputs and signals detection.

Practice

1.

What is the main purpose of a sequence detector FSM in Verilog?

easy

A. To perform arithmetic operations on input data

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

C. To generate random numbers

D. To store large amounts of data

Solution

1. Step 1: Understand FSM role

   A sequence detector FSM watches input bits and changes states based on the pattern seen.

2. Step 2: Identify purpose

   Its main job is to find a specific bit pattern in a stream and signal when found.

3. Final Answer:

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

4. Quick Check:

   Sequence detector FSM = pattern detection [OK]

Hint: FSMs track input patterns to signal matches [OK]

Common Mistakes:

• Confusing FSM with memory storage
• Thinking FSM generates data
• Assuming FSM does arithmetic

2.

Which of the following is the correct way to declare a state type for a sequence detector FSM in Verilog?

typedef enum logic [1:0] {S0, S1, S2, S3} state_t;

easy

A. typedef enum logic [1:0] {S0, S1, S2, S3} state_t;

B. enum state_t {S0, S1, S2, S3};

C. typedef enum {S0, S1, S2, S3} state_t;

D. state_t enum logic [1:0] {S0, S1, S2, S3};

Solution

1. Step 1: Check Verilog enum syntax

   SystemVerilog uses 'typedef enum logic [width] {states} name;' to define state types.

2. Step 2: Match correct syntax

   typedef enum logic [1:0] {S0, S1, S2, S3} state_t; matches this syntax exactly, defining 2-bit logic states with typedef.

3. Final Answer:

   typedef enum logic [1:0] {S0, S1, S2, S3} state_t; -> Option A

4. Quick Check:

   Correct enum typedef syntax = typedef enum logic [1:0] {S0, S1, S2, S3} state_t; [OK]

Hint: Use 'typedef enum logic [width]' for states in Verilog [OK]

Common Mistakes:

• Omitting 'typedef' keyword
• Missing logic width specification
• Incorrect order of keywords

3.

Given the following Verilog snippet for a sequence detector FSM that detects "101":

always_ff @(posedge clk or posedge rst) begin
  if (rst) state <= S0;
  else begin
    case(state)
      S0: state <= (in == 1) ? S1 : S0;
      S1: state <= (in == 0) ? S2 : S1;
      S2: state <= (in == 1) ? S3 : S0;
      S3: state <= S0;
    endcase
  end
end

assign detected = (state == S3);

If the input sequence is 1 0 1, what will be the value of detected after the last bit?

medium

A. Undefined

B. 0

C. 1

D. Depends on reset

Solution

1. Step 1: Trace FSM states for input 1,0,1

   Start at S0. Input 1 moves to S1. Input 0 moves to S2. Input 1 moves to S3.

2. Step 2: Check output at S3

   Detected is assigned 1 when state is S3, so after last input detected = 1.

3. Final Answer:

   1 -> Option C

4. Quick Check:

   Sequence 101 detected = 1 [OK]

Hint: Follow states step-by-step for each input bit [OK]

Common Mistakes:

• Not updating state on each clock
• Confusing output with input
• Ignoring reset effect

4.

Identify the error in this Verilog code snippet for a sequence detector FSM:

always_ff @(posedge clk or posedge rst) begin
  if (rst) state <= S0;
  else begin
    case(state)
      S0: if (in == 1) state <= S1;
      S1: if (in == 0) state <= S2;
      S2: if (in == 1) state <= S3;
      S3: state <= S0;
    endcase
  end
end

What is the main problem?

medium

A. Missing default state transition causing latch inference

B. Incorrect sensitivity list in always_ff block

C. Using blocking assignments instead of non-blocking

D. No output signal declared

Solution

1. Step 1: Analyze state transitions

   Each case only assigns state on certain conditions; no else or default to assign state otherwise.

2. Step 2: Understand latch inference

   Missing assignments in some branches cause inferred latches, which is incorrect for FSMs.

3. Final Answer:

   Missing default state transition causing latch inference -> Option A

4. Quick Check:

   All state transitions must be assigned to avoid latches [OK]

Hint: Always assign state in every case branch [OK]

Common Mistakes:

• Not assigning state in else branches
• Using blocking assignments in sequential logic
• Ignoring reset signal

5.

You want to design a sequence detector FSM in Verilog that detects overlapping sequences of "1101" in a serial input stream. Which approach correctly handles overlapping detection?

hard

A. Reset to initial state after full match to allow new detection from next bit

B. Use combinational logic only without states

C. Ignore overlapping sequences and restart detection only after full reset

D. Return to a state representing partial match of last bits to catch overlaps

Solution

1. Step 1: Understand overlapping sequences

   Overlapping means the end of one detected sequence can be the start of another.

2. Step 2: Design FSM to handle overlaps

   FSM must return to a state representing partial match of last bits, not always initial state, to detect overlaps.

3. Final Answer:

   Return to a state representing partial match of last bits to catch overlaps -> Option D

4. Quick Check:

   Partial match states enable overlapping detection [OK]

Hint: Use partial match states to detect overlaps [OK]

Common Mistakes:

• Always resetting to initial state after match
• Ignoring overlap possibility
• Trying to detect sequences without states