Three-block FSM coding style in Verilog - Time & Space Complexity

Time Complexity: Three-block FSM coding style

O(n)

Understanding Time Complexity

We want to understand how the time it takes for a three-block FSM to run changes as the input size grows.

Specifically, we ask: how does the number of steps grow when the FSM processes more inputs?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

module fsm_three_block(
  input clk, reset, input_signal,
  output reg out_signal
);
  reg [1:0] state, next_state;

  // State register block
  always @(posedge clk or posedge reset) begin
    if (reset) state <= 2'b00;
    else state <= next_state;
  end

  // Next state logic block
  always @(*) begin
    case(state)
      2'b00: next_state = input_signal ? 2'b01 : 2'b00;
      2'b01: next_state = input_signal ? 2'b10 : 2'b00;
      2'b10: next_state = 2'b00;
      default: next_state = 2'b00;
    endcase
  end

  // Output logic block
  always @(*) begin
    out_signal = (state == 2'b10);
  end
endmodule
    

This code implements a simple three-block FSM: one block for state updates, one for next state logic, and one for output logic.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The FSM updates its state on every clock cycle.
• How many times: Once per clock cycle, repeating indefinitely as inputs arrive.

How Execution Grows With Input

The FSM processes one input per clock cycle, updating state and output accordingly.

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

Pattern observation: The number of operations grows directly with the number of inputs processed.

Final Time Complexity

Time Complexity: O(n)

This means the time to process inputs grows linearly with the number of inputs.

Common Mistake

[X] Wrong: "The FSM runs all states at once, so time grows exponentially with input size."

[OK] Correct: The FSM moves through states one step at a time per clock cycle, so time grows only as inputs increase, not exponentially.

Interview Connect

Understanding how FSMs process inputs step-by-step helps you explain timing and performance in hardware design clearly and confidently.

Self-Check

"What if the FSM had nested loops inside the next state logic? How would the time complexity change?"