Traffic light controller FSM in Verilog - Time & Space Complexity

Time Complexity: Traffic light controller FSM

O(1)

Understanding Time Complexity

We want to understand how the time it takes for a traffic light controller FSM to run changes as the system grows.

Specifically, we ask: how does the number of steps grow when the input or states increase?

Scenario Under Consideration

Analyze the time complexity of the following Verilog FSM code.

module traffic_light_controller(
  input clk, reset,
  output reg [1:0] light_state
);
  parameter RED=2'd0, GREEN=2'd1, YELLOW=2'd2;
  reg [1:0] state, next_state;

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

  always @* begin
    case(state)
      RED: next_state = GREEN;
      GREEN: next_state = YELLOW;
      YELLOW: next_state = RED;
      default: next_state = RED;
    endcase
  end

  always @* begin
    light_state = state;
  end
endmodule

This code cycles through traffic light states: RED, GREEN, YELLOW, then back to RED.

Identify Repeating Operations

The FSM updates its state on every clock cycle.

• Primary operation: State transition on each clock tick.
• How many times: Once per clock cycle, indefinitely.

How Execution Grows With Input

The FSM runs one state update per clock cycle regardless of input size.

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 time, but each update is constant work.

Final Time Complexity

Time Complexity: O(1)

This means each state update takes the same fixed time, no matter how many states or inputs there are.

Common Mistake

[X] Wrong: "The FSM takes longer as more states are added because it checks all states each time."

[OK] Correct: The FSM only moves from one state to the next directly, so each update is a simple step, not a full search.

Interview Connect

Understanding FSM time complexity helps you explain how hardware designs handle timing predictably and efficiently.

Self-Check

"What if the FSM had to check multiple inputs before deciding the next state? How would the time complexity change?"

Practice

1. What is the main purpose of a traffic light controller FSM in Verilog?

easy

A. To detect traffic jams using sensors

B. To count the number of cars passing the intersection

C. To change traffic lights in a safe and timed sequence

D. To control the speed of vehicles on the road

Solution

1. Step 1: Understand FSM role in traffic lights

   A traffic light controller FSM manages the sequence of lights (red, yellow, green) safely and in timed order.

2. Step 2: Compare options to FSM purpose

   Only To change traffic lights in a safe and timed sequence describes changing lights in a safe and timed sequence, which is the FSM's job.

3. Final Answer:

   To change traffic lights in a safe and timed sequence -> Option C

4. Quick Check:

   FSM controls light sequence = A [OK]

Hint: FSM controls states and timing for lights [OK]

Common Mistakes:

• Confusing FSM with sensor or speed control
• Thinking FSM counts cars
• Assuming FSM controls vehicle speed

2. Which Verilog code snippet correctly declares the state variable for a traffic light FSM?

easy

A. logic state; // single bit logic variable

B. wire state; // single wire for state

C. integer state = 0; // integer state variable

D. reg [1:0] state; // 2-bit state variable

Solution

1. Step 1: Identify correct state variable type

   FSM states are stored in registers (reg) because they hold values across clock cycles.

2. Step 2: Check bit width for multiple states

   Traffic light FSM usually needs multiple bits (e.g., 2 bits) to represent states, so reg [1:0] is correct.

3. Final Answer:

   reg [1:0] state; // 2-bit state variable -> Option D

4. Quick Check:

   State needs reg and multiple bits = A [OK]

Hint: Use reg with enough bits for states [OK]

Common Mistakes:

• Using wire instead of reg for state
• Using single bit for multiple states
• Using integer without clocked assignment

3. Given this Verilog snippet for a traffic light FSM state transition:

always @(posedge clk) begin
  case(state)
    2'b00: state <= 2'b01;
    2'b01: state <= 2'b10;
    2'b10: state <= 2'b00;
    default: state <= 2'b00;
  endcase
end

What will be the sequence of states after 4 clock cycles starting from 2'b00?

medium

A. 00, 01, 10, 00

B. 00, 10, 01, 00

C. 00, 01, 00, 10

D. 00, 10, 10, 01

Solution

1. Step 1: Trace state transitions step-by-step

   Start at 00, next is 01, then 10, then back to 00 on each clock.

2. Step 2: List states for 4 cycles

   Cycle 1: 00, Cycle 2: 01, Cycle 3: 10, Cycle 4: 00.

3. Final Answer:

   00, 01, 10, 00 -> Option A

4. Quick Check:

   Follow case transitions = B [OK]

Hint: Follow case transitions in order [OK]

Common Mistakes:

• Mixing up state assignments order
• Forgetting default case resets state
• Assuming states skip steps

4. Identify the error in this Verilog FSM snippet for a traffic light controller:

always @(posedge clk) begin
  if (reset) state <= 2'b00;
  else
    case(state)
      2'b00: state = 2'b01;
      2'b01: state = 2'b10;
      2'b10: state = 2'b00;
    endcase
end

medium

A. Using blocking assignment (=) inside sequential always block

B. Missing default case in case statement

C. Reset condition should be asynchronous

D. State variable declared as wire instead of reg

Solution

1. Step 1: Check assignment types in clocked always block

   Inside always @(posedge clk), non-blocking assignment (<=) must be used to avoid race conditions.

2. Step 2: Identify incorrect use of blocking assignment

   The code uses '=' (blocking) inside sequential logic, which is incorrect.

3. Final Answer:

   Using blocking assignment (=) inside sequential always block -> Option A

4. Quick Check:

   Use non-blocking (<=) in clocked blocks = C [OK]

Hint: Use <= in clocked always blocks [OK]

Common Mistakes:

• Using = instead of <= in sequential logic
• Ignoring missing default case (less critical)
• Confusing synchronous and asynchronous reset

5. You want to add a pedestrian crossing state to a traffic light FSM with states: Green (00), Yellow (01), Red (10), and Pedestrian Walk (11). Which state transition sequence correctly includes the pedestrian state after Red?

hard

A. Pedestrian Walk (11) -> Green (00) -> Yellow (01) -> Red (10) -> Pedestrian Walk (11)

B. Green (00) -> Yellow (01) -> Red (10) -> Pedestrian Walk (11) -> Green (00)

C. Green (00) -> Yellow (01) -> Pedestrian Walk (11) -> Red (10) -> Green (00)

D. Green (00) -> Pedestrian Walk (11) -> Yellow (01) -> Red (10) -> Green (00)

Solution

1. Step 1: Understand safe traffic light sequence

   Normal sequence is Green -> Yellow -> Red, then pedestrian walk should come after Red for safety.

2. Step 2: Check options for correct order

   Green (00) -> Yellow (01) -> Red (10) -> Pedestrian Walk (11) -> Green (00) correctly places Pedestrian Walk after Red, then cycles back to Green.

3. Final Answer:

   Green (00) -> Yellow (01) -> Red (10) -> Pedestrian Walk (11) -> Green (00) -> Option B

4. Quick Check:

   Pedestrian after Red before Green = D [OK]

Hint: Pedestrian walk follows Red light for safety [OK]

Common Mistakes:

• Placing pedestrian walk before Yellow or Green
• Skipping pedestrian state in sequence
• Looping pedestrian state incorrectly