Linear Feedback Shift Register (LFSR) in Verilog - Time & Space Complexity

Time Complexity: Linear Feedback Shift Register (LFSR)

O(n)

Understanding Time Complexity

We want to understand how the time it takes for a Linear Feedback Shift Register (LFSR) to run grows as we change its size.

Specifically, how does the number of steps or operations change when the LFSR length changes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

module lfsr(
  input logic clk, reset,
  output logic [3:0] q
);
  always_ff @(posedge clk or posedge reset) begin
    if (reset) q <= 4'b0001;
    else q <= {q[2:0], q[3] ^ q[0]};
  end
endmodule

This code implements a 4-bit LFSR that shifts bits and uses XOR feedback to generate a sequence.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The shift and XOR feedback happen once every clock cycle.
• How many times: This operation repeats once per clock cycle indefinitely.

How Execution Grows With Input

The LFSR shifts bits and calculates feedback every clock cycle, regardless of its size.

Input Size (n bits)	Approx. Operations per Cycle
4	4 shifts + 1 XOR
8	8 shifts + 1 XOR
16	16 shifts + 1 XOR

Pattern observation: The number of shift operations grows linearly with the number of bits, but the XOR feedback count stays constant.

Final Time Complexity

Time Complexity: O(n)

This means the time to perform one shift and feedback step grows linearly with the number of bits in the LFSR.

Common Mistake

[X] Wrong: "The LFSR runs in constant time no matter how many bits it has."

[OK] Correct: Each bit must be shifted every cycle, so more bits mean more operations, making the time grow with size.

Interview Connect

Understanding how hardware operations scale with input size helps you explain design choices clearly and shows you can think about efficiency in real circuits.

Self-Check

"What if we changed the LFSR to update multiple bits per clock cycle? How would the time complexity change?"