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.