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?"

Practice

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

easy

A. The next state combinational logic block

B. The output combinational logic block

C. The state register block using always_ff

D. The reset logic block

Solution

1. Step 1: Understand the role of each FSM block

   The three-block FSM style divides the design into state storage, next state logic, and output logic.

2. Step 2: Identify the block that stores the current state

   The state register block uses always_ff to store the current state in flip-flops.

3. Final Answer:

   The state register block using always_ff -> Option C

4. Quick Check:

   State storage = always_ff block [OK]

Hint: State storage always uses always_ff block [OK]

Common Mistakes:

• Confusing next state logic with state storage
• Thinking output logic stores state
• Mixing combinational and sequential blocks

2. Which of the following is the correct syntax for the next state logic block in a three-block FSM style?

easy

A. always_comb begin next_state = ... end

B. always_ff @(posedge clk) begin next_state = ... end

C. always @(posedge clk or posedge reset) begin state <= next_state; end

D. always @(negedge clk) begin output = ... end

Solution

1. Step 1: Identify the block type for next state logic

   Next state logic is combinational and should use always_comb for clean synthesis and readability.

2. Step 2: Match the syntax with the correct block

   always_comb begin next_state = ... end uses always_comb with next_state assignment, which is correct for next state logic.

3. Final Answer:

   always_comb begin next_state = ... end -> Option A

4. Quick Check:

   Next state logic = always_comb block [OK]

Hint: Next state logic uses always_comb block [OK]

Common Mistakes:

• Using always_ff for next state logic
• Mixing sensitivity lists manually
• Assigning state in next state block

3. Given the following three-block FSM code snippet, what will be the value of state after the rising edge of clk if reset is 0 and current state is 2?

typedef enum logic [1:0] {S0=0, S1=1, S2=2} state_t;

state_t state, next_state;

// State register
always_ff @(posedge clk or posedge reset) begin
  if (reset) state <= S0;
  else state <= next_state;
end

// Next state logic
always_comb begin
  case(state)
    S0: next_state = S1;
    S1: next_state = S2;
    S2: next_state = S0;
    default: next_state = S0;
  endcase
end

// Output logic (not shown)

medium

A. S0 (0)

B. S1 (1)

C. S2 (2)

D. Reset state

Solution

1. Step 1: Analyze current state and next state logic

   Current state is S2 (2). According to next state logic, from S2 next_state = S0.

2. Step 2: Determine state after clock edge with reset=0

   Since reset=0, state updates to next_state, which is S0 (0).

3. Final Answer:

   S0 (0) -> Option A

4. Quick Check:

   From S2, next_state = S0, so state = S0 after clk [OK]

Hint: Trace next_state from current state, then update on clk [OK]

Common Mistakes:

• Confusing current and next state
• Ignoring reset condition
• Assuming state stays the same

4. Identify the error in this three-block FSM snippet:

always_ff @(posedge clk or posedge reset) begin
  if (reset) state <= S0;
  else state = next_state;
end

always_comb begin
  case(state)
    S0: next_state = S1;
    S1: next_state = S0;
    default: next_state = S0;
  endcase
end

medium

A. Incorrect case statement syntax

B. Using blocking assignment (=) instead of non-blocking (<=) in always_ff block

C. Missing sensitivity list in always_comb block

D. No reset condition in always_ff block

Solution

1. Step 1: Check assignments in always_ff block

   In sequential blocks (always_ff), non-blocking assignment (<=) must be used to avoid race conditions.

2. Step 2: Identify the incorrect assignment

   The line state = next_state; uses blocking assignment (=), which is incorrect here.

3. Final Answer:

   Using blocking assignment (=) instead of non-blocking (<=) in always_ff block -> Option B

4. Quick Check:

   always_ff requires <= for state updates [OK]

Hint: Use <= in always_ff blocks for state updates [OK]

Common Mistakes:

• Using = instead of <= in sequential blocks
• Forgetting reset condition
• Incorrect sensitivity list in always_comb

5. You want to design a three-block FSM that has an output signal flag which is high only when the FSM is in state S2. Which block should you put the flag assignment in, and what is the correct style?

hard

A. In the reset logic block, assign flag = 0; only

B. In the state register block using always_ff, assign flag <= (state == S2);

C. In the next state logic block using always_comb, assign flag = (next_state == S2);

D. In the output logic block using always_comb, assign flag = (state == S2);

Solution

1. Step 1: Identify where output signals are assigned in three-block FSM

   Output signals based on current state are assigned in the output logic block, which is combinational and uses always_comb.

2. Step 2: Write the correct assignment for flag

   Assign flag = (state == S2); inside the output logic block to reflect current state.

3. Final Answer:

   In the output logic block using always_comb, assign flag = (state == S2); -> Option D

4. Quick Check:

   Output logic uses always_comb with flag = (state == S2) [OK]

Hint: Assign outputs combinationally based on current state [OK]

Common Mistakes:

• Assigning outputs in always_ff block
• Using next_state instead of state for outputs
• Ignoring combinational output logic block