Two-process FSM coding style in VHDL - Time & Space Complexity

Time Complexity: Two-process FSM coding style

O(n)

Understanding Time Complexity

We want to understand how the time it takes to run a two-process FSM grows as the input changes.

Specifically, how does the number of steps change when the FSM handles more inputs or states?

Scenario Under Consideration

Analyze the time complexity of the following VHDL two-process FSM code.

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

process(state, input_signal)
begin
  case state is
    when IDLE =>
      if input_signal = '1' then
        next_state <= BUSY;
      else
        next_state <= IDLE;
      end if;
    when BUSY =>
      next_state <= IDLE;
    when others =>
      next_state <= IDLE;
  end case;
end process;

This code uses one process to update the current state on clock edges and another to decide the next state based on inputs.

Identify Repeating Operations

Look for loops or repeated steps in the FSM.

• Primary operation: The state update happens every clock cycle.
• How many times: Once per clock tick, indefinitely as the system runs.

How Execution Grows With Input

The FSM checks inputs and updates state every clock cycle, no matter how many states or inputs there are.

Input Size (n)	Approx. Operations
10	10 state updates
100	100 state updates
1000	1000 state updates

Pattern observation: The number of operations grows directly with the number of clock cycles, not with the number of states.

Final Time Complexity

Time Complexity: O(n)

This means the FSM does a fixed amount of work each clock cycle, so total work grows linearly with time.

Common Mistake

[X] Wrong: "More states mean the FSM takes longer each cycle to update."

[OK] Correct: The FSM updates state once per cycle regardless of state count; more states only affect logic complexity, not per-cycle steps.

Interview Connect

Understanding how FSMs handle inputs over time helps you explain hardware behavior clearly and shows you grasp timing and control flow concepts.

Self-Check

"What if the FSM had nested loops inside the combinational process? How would the time complexity change?"

Practice

1. In a two-process FSM coding style in VHDL, what is the main role of the first process?

easy

A. To update the current state on clock and reset signals

B. To decide the next state based on inputs

C. To generate output signals directly

D. To initialize variables outside the FSM

Solution

1. Step 1: Understand the two-process FSM structure

   The first process in a two-process FSM handles synchronous operations like updating the current state on clock edges and reset.

2. Step 2: Identify the role of the first process

   This process updates the current state register based on clock and reset signals, ensuring state changes happen synchronously.

3. Final Answer:

   To update the current state on clock and reset signals -> Option A

4. Quick Check:

   First process updates state [OK]

Hint: First process updates state on clock/reset [OK]

Common Mistakes:

• Confusing output logic with state update
• Thinking next state logic is in first process
• Assuming initialization happens in first process

2. Which of the following is the correct sensitivity list for the second process in a two-process FSM that decides next state and outputs?

easy

A. clk, reset

B. clk only

C. reset only

D. current_state, inputs

Solution

1. Step 1: Identify what triggers next state and output logic

   The second process is combinational and depends on current state and inputs to decide next state and outputs.

2. Step 2: Determine the sensitivity list

   It must include all signals that affect next state and outputs, which are current_state and inputs, not clock or reset.

3. Final Answer:

   current_state, inputs -> Option D

4. Quick Check:

   Second process sensitivity = current_state, inputs [OK]

Hint: Second process sensitive to state and inputs only [OK]

Common Mistakes:

• Including clock in second process sensitivity
• Using reset in sensitivity list incorrectly
• Leaving sensitivity list empty

3. Given the following VHDL code snippet for a two-process FSM, what will be the value of current_state after the rising edge of clk if reset is '0' and next_state is S1?

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

medium

A. S0

B. S1

C. Undefined

D. Remains previous state

Solution

1. Step 1: Analyze reset condition

   Reset is '0', so the reset block is skipped; no forced reset to S0.

2. Step 2: Analyze clock rising edge behavior

   On rising edge of clk, current_state is assigned next_state, which is S1.

3. Final Answer:

   S1 -> Option B

4. Quick Check:

   Reset '0' + rising edge = current_state = next_state [OK]

Hint: Reset '0' means state updates to next_state on clock [OK]

Common Mistakes:

• Assuming reset '0' resets state to S0
• Confusing next_state with current_state immediately
• Ignoring rising_edge condition

4. Identify the error in this two-process FSM snippet where the next state logic is incorrect:

process(current_state, input_signal)
begin
  case current_state is
    when S0 =>
      if input_signal = '1' then
        next_state <= S1;
      else
        next_state <= S0;
      end if;
    when S1 =>
      next_state <= S0;
  end case;
end process;

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

medium

A. Sensitivity list missing clk and reset

B. Next state logic should be in clocked process

C. Missing default case in case statement

D. Using '<=' in combinational process instead of ':='

Solution

1. Step 1: Check the case statement coverage

   The case(current_state is) only specifies when S0 and when S1, but omits a catch-all 'when others' clause.

2. Step 2: Understand the consequence

   In a combinational process, incomplete case coverage infers latches on next_state, which is undesirable; it should be fully combinational logic. A default like 'when others => next_state <= current_state;' is needed.

3. Final Answer:

   Missing default case in case statement -> Option C

4. Quick Check:

   Missing when others => latch inferred [OK]

Hint: Case statements in combo processes need 'when others' [OK]

Common Mistakes:

• Omitting 'when others' in case statement
• Ignoring sensitivity list completeness
• Placing next state logic in clocked process

5. You want to design a two-process FSM in VHDL that has three states (IDLE, BUSY, DONE). The FSM should reset to IDLE, move to BUSY when start='1', and then to DONE after one clock cycle. Which of the following next state process code snippets correctly implements this behavior?

hard

A. process(current_state, start)
begin
case current_state is
when IDLE =>
if start = '1' then
next_state <= BUSY;
else
next_state <= IDLE;
end if;
when BUSY =>
next_state <= DONE;
when DONE =>
next_state <= IDLE;
end case;
end process;

B. process(clk, reset)
begin
if reset = '1' then
next_state <= IDLE;
elsif rising_edge(clk) then
if start = '1' then
next_state <= BUSY;
else
next_state <= DONE;
end if;
end if;
end process;

C. process(current_state)
begin
if start = '1' then
next_state <= BUSY;
else
next_state <= IDLE;
end if;
end process;

D. process(current_state, start)
begin
if current_state = IDLE and start = '1' then
next_state <= BUSY;
elsif current_state = BUSY then
next_state <= DONE;
end if;
end process;

Solution

1. Step 1: Check reset and state transitions

   The FSM resets to IDLE (handled in clocked process), so next_state logic must handle transitions from IDLE to BUSY on start='1', BUSY to DONE, and DONE to IDLE.

2. Step 2: Analyze next state logic options

   The correct code uses a combinational process with sensitivity to current_state and start, employing a case statement that fully covers all states with proper transitions: IDLE stays or goes to BUSY based on start, BUSY to DONE, DONE to IDLE. Other codes fail by using clocked process for next_state, missing inputs in sensitivity, incomplete state handling, or unassigned paths in conditional logic leading to latches.

3. Final Answer:

   The case statement with IDLE, BUSY, DONE transitions -> Option A

4. Quick Check:

   Case statement with all states and transitions [OK]

Hint: Use case statement covering all states for next state logic [OK]

Common Mistakes:

• Placing next state logic in clocked process
• Missing transitions for all states
• Ignoring start signal conditions