Shift register (SIPO, PISO, SISO) in Verilog - Time & Space Complexity

Time Complexity: Shift register (SIPO, PISO, SISO)

O(n)

Understanding Time Complexity

We want to understand how the time it takes to run a shift register changes as the number of bits grows.

How does the number of steps grow when we increase the size of the register?

Scenario Under Consideration

Analyze the time complexity of the following Verilog code for a Serial-In Parallel-Out (SIPO) shift register.

module sipo_shift_register #(parameter N = 8) (
  input wire clk,
  input wire serial_in,
  output reg [N-1:0] parallel_out
);
  always @(posedge clk) begin
    parallel_out <= {parallel_out[N-2:0], serial_in};
  end
endmodule
    

This code shifts in one bit each clock cycle and outputs all bits in parallel after N cycles.

Identify Repeating Operations

Look for loops or repeated steps in the code.

• Primary operation: Shifting bits in the register each clock cycle.
• How many times: Once per clock cycle, repeated N times to fill the register.

How Execution Grows With Input

Each new bit requires one clock cycle to shift in, so the total time grows with the number of bits.

Input Size (n)	Approx. Operations (clock cycles)
10	10
100	100
1000	1000

Pattern observation: The time grows directly with the number of bits; doubling bits doubles the time.

Final Time Complexity

Time Complexity: O(n)

This means the time to shift in all bits grows linearly with the size of the register.

Common Mistake

[X] Wrong: "The shift register processes all bits at once, so time does not depend on size."

[OK] Correct: Each bit must be shifted in one by one, so more bits mean more steps and more time.

Interview Connect

Understanding how shift registers work and their timing helps you explain hardware design clearly and shows you can think about how systems scale.

Self-Check

"What if we changed the shift register to shift in multiple bits at once? How would the time complexity change?"