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

Time Complexity: Three-process FSM coding style

O(n)

Understanding Time Complexity

When we write a three-process FSM in VHDL, we want to know how the time it takes to run changes as the input size grows.

We ask: How does the number of steps grow when the FSM handles more inputs or states?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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 <= WORK;
      else
        next_state <= IDLE;
      end if;
    when WORK =>
      next_state <= DONE;
    when others =>
      next_state <= IDLE;
  end case;
end process;

process(state)
begin
  case state is
    when IDLE => output_signal <= '0';
    when WORK => output_signal <= '1';
    when DONE => output_signal <= '0';
    when others => output_signal <= '0';
  end case;
end process;

This code shows a three-process FSM: one for state update, one for next state logic, and one for output logic.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The state update happens every clock cycle.
• How many times: Once per clock tick, no loops inside processes.

How Execution Grows With Input

Each clock cycle, the FSM updates state and output based on current inputs and state.

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

Pattern observation: The number of operations grows linearly with the number of clock cycles or inputs processed.

Final Time Complexity

Time Complexity: O(n)

This means the FSM takes time proportional to how many inputs or clock cycles it processes.

Common Mistake

[X] Wrong: "The FSM runs slower if it has more states because it loops over all states each cycle."

[OK] Correct: The FSM only updates one state per cycle; it does not loop over all states each time.

Interview Connect

Understanding how FSMs scale with input size helps you design efficient hardware and explain your design choices clearly.

Self-Check

"What if we added a loop inside the next state process to check multiple inputs each cycle? How would the time complexity change?"

Practice

1. In the three-process FSM coding style in VHDL, which process is responsible for storing the current state?

easy

A. The next state logic process

B. The state register process

C. The output logic process

D. The clock generation process

Solution

1. Step 1: Understand the role of each process

   The three-process FSM style divides the FSM into state register, next state logic, and output logic processes.

2. Step 2: Identify which process stores the current state

   The state register process updates and stores the current state on clock edges.

3. Final Answer:

   The state register process -> Option B

4. Quick Check:

   State storage = state register process [OK]

Hint: State storage always happens in the state register process [OK]

Common Mistakes:

• Confusing next state logic with state storage
• Thinking output logic stores the state
• Assuming clock generation is part of FSM

2. Which of the following is the correct sensitivity list for the next state logic process in a three-process FSM?

easy

A. clk, reset

B. clk

C. outputs

D. current_state, inputs

Solution

1. Step 1: Recall what next state logic depends on

   The next state logic calculates the next state based on the current state and inputs.

2. Step 2: Determine the sensitivity list

   It must react to changes in current_state and inputs, so these go in the sensitivity list.

3. Final Answer:

   current_state, inputs -> Option D

4. Quick Check:

   Next state logic sensitivity = current_state, inputs [OK]

Hint: Next state logic sensitive to current state and inputs only [OK]

Common Mistakes:

• Including clk in next state logic sensitivity list
• Using outputs in sensitivity list
• Leaving sensitivity list empty

3. Given the following partial FSM code snippet, what will be the output value of output_signal when current_state is S1 and input_signal is '1'?

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

medium

A. Undefined

B. '0'

C. '1'

D. Signal retains previous value

Solution

1. Step 1: Analyze the output logic for state S1

   When current_state is S1, output_signal is '1' if input_signal is '1', else '0'.

2. Step 2: Apply given inputs

   current_state = S1 and input_signal = '1' means output_signal <= '1'.

3. Final Answer:

   '1' -> Option C

4. Quick Check:

   Output for S1 with input '1' = '1' [OK]

Hint: Check state and input conditions carefully for output logic [OK]

Common Mistakes:

• Ignoring input condition inside S1
• Assuming output is always '0' in S1
• Confusing output logic with next state logic

4. Identify the error in this state register process code snippet for a three-process FSM:

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

medium

A. Using next_state instead of current_state on clock edge

B. Missing sensitivity to next_state signal

C. Reset condition should be inside rising_edge(clk)

D. No error, code is correct

Solution

1. Step 1: Understand state register role

   The state register updates current_state with next_state on clock edge.

2. Step 2: Check assignment inside clock edge

   The code assigns next_state <= current_state, which is reversed and wrong.

3. Final Answer:

   Using next_state instead of current_state on clock edge -> Option A

4. Quick Check:

   State register updates current_state, not next_state [OK]

Hint: State register updates current_state from next_state [OK]

Common Mistakes:

• Assigning next_state inside state register process
• Placing reset inside clock edge condition
• Confusing current_state and next_state signals

5. You want to design a three-process FSM with states IDLE, BUSY, and DONE. Which of the following correctly describes the responsibilities of the three processes?

hard

A. Process 1: Store current state; Process 2: Compute next state from current state and inputs; Process 3: Generate outputs based on current state

B. Process 1: Generate outputs; Process 2: Store current state; Process 3: Compute next state

C. Process 1: Compute next state; Process 2: Generate outputs; Process 3: Store current state

D. Process 1: Store current state and outputs; Process 2: Compute next state; Process 3: Reset FSM

Solution

1. Step 1: Recall three-process FSM roles

   The three processes are: state register (store current state), next state logic (compute next state), output logic (generate outputs).

2. Step 2: Match roles to options

   Process 1: Store current state; Process 2: Compute next state from current state and inputs; Process 3: Generate outputs based on current state correctly assigns these roles in order.

3. Final Answer:

   Process 1: Store current state; Process 2: Compute next state from current state and inputs; Process 3: Generate outputs based on current state -> Option A

4. Quick Check:

   Three-process FSM roles = B [OK]

Hint: Remember: register stores state, logic computes next, output drives signals [OK]

Common Mistakes:

• Mixing output generation with state storage
• Assigning reset to a separate process
• Combining multiple roles in one process