Sequence detector FSM in Verilog - Practice Problems & Coding Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of a simple sequence detector FSM

What is the output sequence of this FSM when the input sequence is 1,0,1,1,0,1?
The FSM detects the sequence '101' and outputs 1 when detected, else 0.

Verilog

module seq_detector(input clk, input reset, input in, output reg out);
  typedef enum reg [1:0] {S0, S1, S2} state_t;
  state_t state, next_state;

  always @(posedge clk or posedge reset) begin
    if (reset) state <= S0;
    else state <= next_state;
  end

  always @(*) begin
    out = 0;
    case(state)
      S0: if (in) next_state = S1; else next_state = S0;
      S1: if (!in) next_state = S2; else next_state = S1;
      S2: begin
        if (in) begin
          next_state = S1;
          out = 1;
        end else next_state = S0;
      end
      default: next_state = S0;
    endcase
  end
endmodule

A [0,0,0,1,0,1]

B [0,0,0,0,0,1]

C [0,0,1,0,0,1]

D [0,1,0,1,0,0]

💡 Hint

Trace the FSM states step-by-step for each input bit.

The FSM outputs 1 only when the sequence '101' is detected ending at the current input. For the input sequence 1,0,1,1,0,1, the output is 0 until the last input where the sequence completes.

🧠 Conceptual

intermediate

Understanding overlapping sequences in FSM

Why is it important for a sequence detector FSM to handle overlapping sequences?
Consider detecting '101' in a stream like '10101'.

A To allow the FSM to detect the sequence again immediately if it overlaps with the previous one.

B To reset the FSM after each detection to avoid false positives.

C To ignore repeated inputs and reduce output glitches.

D To increase the clock frequency for faster detection.

💡 Hint

Think about sequences that share bits between detections.

Overlapping sequences allow the FSM to detect sequences that share bits, like '101' in '10101' where the last '1' of the first sequence is the first '1' of the next.

🔧 Debug

advanced

Identify the error in this sequence detector FSM code

This FSM is supposed to detect the sequence '110'. What error causes it to never output 1?

Verilog

module seq_detector(input clk, input reset, input in, output reg out);
  typedef enum reg [1:0] {S0, S1, S2} state_t;
  state_t state, next_state;

  always @(posedge clk or posedge reset) begin
    if (reset) state <= S0;
    else state <= next_state;
  end

  always @(*) begin
    out = 0;
    case(state)
      S0: if (in) next_state = S1; else next_state = S0;
      S1: if (in) next_state = S2; else next_state = S0;
      S2: if (!in) begin
            next_state = S0;
            out = 1;
          end else next_state = S2;
      default: next_state = S0;
    endcase
  end
endmodule

A The FSM never resets to S0 on reset signal.

B The output 'out' is assigned only when transitioning from S2 to S0, missing detection.

C The output 'out' is assigned inside a combinational block causing glitches.

D The FSM stays in S2 on input 1, missing the overlapping sequence detection.

💡 Hint

Check how the FSM transitions from S2 on input 1.

The FSM stays in S2 on input 1, so it does not allow overlapping detection of sequences starting with '1' again, causing missed detections.

📝 Syntax

advanced

Identify the syntax error in this FSM Verilog code

Which option correctly fixes the syntax error in this FSM code snippet?

Verilog

always @ (posedge clk or posedge reset) begin
  if reset
    state <= S0;
  else
    state <= next_state;
end

A Change 'if reset' to 'if (reset)'

B Add semicolon after 'if reset;'

C Replace 'posedge reset' with 'negedge reset'

D Remove 'or posedge reset' from sensitivity list

💡 Hint

Check the syntax for if statements in Verilog.

In Verilog, the condition in an if statement must be enclosed in parentheses.

🚀 Application

expert

Number of states in a sequence detector FSM

How many states are required in a Moore FSM to detect the sequence '1011' with overlapping allowed?

A 4 states

B 6 states

C 5 states

D 3 states

💡 Hint

Count states representing each prefix of the sequence including the empty prefix.

For a sequence of length N, a Moore FSM detecting overlapping sequences typically needs N+1 states representing progress from no match to full match.

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