Sequence detector FSM in VHDL - Practice Problems & Coding Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of a simple sequence detector FSM

What is the output of this VHDL sequence detector FSM when the input sequence is 110110?

VHDL

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;

entity seq_detector is
    Port ( clk : in STD_LOGIC;
           rst : in STD_LOGIC;
           din : in STD_LOGIC;
           dout : out STD_LOGIC);
end seq_detector;

architecture Behavioral of seq_detector is
    type state_type is (S0, S1, S2, S3);
    signal state, next_state : state_type;
begin
    process(clk, rst)
    begin
        if rst = '1' then
            state <= S0;
        elsif rising_edge(clk) then
            state <= next_state;
        end if;
    end process;

    process(state, din)
    begin
        dout <= '0';
        case state is
            when S0 =>
                if din = '1' then
                    next_state <= S1;
                else
                    next_state <= S0;
                end if;
            when S1 =>
                if din = '1' then
                    next_state <= S2;
                else
                    next_state <= S0;
                end if;
            when S2 =>
                if din = '0' then
                    next_state <= S3;
                else
                    next_state <= S2;
                end if;
            when S3 =>
                dout <= '1';
                if din = '1' then
                    next_state <= S1;
                else
                    next_state <= S0;
                end if;
        end case;
    end process;
end Behavioral;

A Output sequence: 000000

B Output sequence: 000010

C Output sequence: 000100

D Output sequence: 000001

💡 Hint

Trace the FSM states step-by-step for each input bit and note when dout becomes '1'.

The FSM detects the sequence '110' and sets dout to '1' when the sequence is detected at the last input bit. For input 110110, the output is '000010' because the sequence '110' appears starting at the first bit and again starting at the fourth bit, but only the second occurrence triggers dout at the fifth input bit.

🧠 Conceptual

intermediate

Understanding state transitions in sequence detector FSM

In the given FSM, what is the purpose of state S2?

A To confirm the second '1' in the sequence before detecting '0'

B To detect the first '1' in the sequence

C To output '1' when the sequence is detected

D To reset the FSM to initial state

💡 Hint

Look at the transitions from S1 to S2 and from S2 to S3.

State S2 is reached after detecting two consecutive '1's. It waits for a '0' to complete the sequence '110'.

🔧 Debug

advanced

Identify the error causing incorrect output in FSM

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

VHDL

process(state, din)
begin
    dout <= '0';
    case state is
        when S0 =>
            if din = '1' then
                next_state <= S1;
            else
                next_state <= S0;
            end if;
        when S1 =>
            if din = '1' then
                next_state <= S2;
            else
                next_state <= S0;
            end if;
        when S2 =>
            if din = '0' then
                next_state <= S3;
            else
                next_state <= S2;
            end if;
        when S3 =>
            dout <= '1';
            if din = '1' then
                next_state <= S1;
            else
                next_state <= S0;
            end if;
    end case;
end process;

A Missing reset condition for next_state signal

B State S3 does not transition back to S0 correctly

C dout is assigned inside the combinational process causing it to reset every cycle

D The clock signal is not used in the process

💡 Hint

Consider how dout is assigned in the process and when it might be reset.

Assigning dout to '0' at the start of the combinational process resets it every time the process runs, so dout never stays '1'.

📝 Syntax

advanced

Identify the syntax error in FSM code snippet

Which option contains the syntax error preventing this FSM from compiling?

VHDL

process(clk, rst)
begin
    if rst = '1' then
        state <= S0;
    elsif rising_edge(clk) then
        state <= next_state;
    end if;
end process;

A Missing semicolon after 'state <= S0'

B Incorrect use of 'elsif' instead of 'else if'

C Missing 'begin' keyword after process declaration

D Using '=' instead of ':=' for signal assignment

💡 Hint

Check each line for missing punctuation.

In VHDL, each statement must end with a semicolon. The line 'state <= S0' is missing a semicolon.

🚀 Application

expert

Number of states in a sequence detector FSM for '1011'

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

A 6 states

B 4 states

C 7 states

D 5 states

💡 Hint

Count states for each prefix of the sequence including the initial state.

For sequence '1011', the FSM needs one initial state plus one state for each prefix: '', '1', '10', '101', '1011' totaling 5 states.

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