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

Practice

1. Which type of shift register converts serial input data into parallel output data?

easy

A. SISO (Serial-In Serial-Out)

B. PISO (Parallel-In Serial-Out)

C. PIPO (Parallel-In Parallel-Out)

D. SIPO (Serial-In Parallel-Out)

Solution

1. Step 1: Understand shift register types

   SIPO means data enters serially and exits in parallel form.

2. Step 2: Match the description

   The question asks for serial input to parallel output, which matches SIPO.

3. Final Answer:

   SIPO (Serial-In Parallel-Out) -> Option D

4. Quick Check:

   Serial input to parallel output = SIPO [OK]

Hint: Remember SIPO = Serial input, Parallel output [OK]

Common Mistakes:

• Confusing PISO with SIPO
• Thinking SISO converts to parallel output
• Mixing up input and output directions

2. Which of the following is the correct Verilog port declaration for a 4-bit PISO shift register input?

easy

A. input [3:0] parallel_in

B. output [3:0] parallel_in

C. input serial_in

D. output serial_out

Solution

1. Step 1: Identify PISO input type

   PISO shift register takes parallel input, so input must be a bus (multiple bits).

2. Step 2: Check port declaration syntax

   input [3:0] parallel_in correctly declares a 4-bit input bus.

3. Final Answer:

   input [3:0] parallel_in -> Option A

4. Quick Check:

   Parallel input uses input [3:0] [OK]

Hint: Parallel inputs use bus syntax: input [n:0] name [OK]

Common Mistakes:

• Using output instead of input for inputs
• Declaring parallel input as single bit
• Confusing serial and parallel port directions

3. Given this Verilog code snippet for a 4-bit SISO shift register, what is the value of q after 3 clock cycles if d inputs are 1, 0, 1 respectively?

reg [3:0] q;
always @(posedge clk) begin
  q <= {q[2:0], d};
end

medium

A. 4'b0101

B. 4'b0011

C. 4'b1010

D. 4'b1001

Solution

1. Step 1: Understand shifting operation

   Each clock, bits shift left and new bit d enters at LSB (rightmost).

2. Step 2: Trace each clock cycle

   Initial q=0000 (assumed).
   Cycle 1: q=0000 -> shift left + d=1 -> 0001
   Cycle 2: q=0001 -> shift left + d=0 -> 0010
   Cycle 3: q=0010 -> shift left + d=1 -> 0101

3. Final Answer:

   4'b0101 -> Option A

4. Quick Check:

   Shift left + input d = 0101 after 3 cycles [OK]

Hint: Shift left and add new bit at right each clock [OK]

Common Mistakes:

• Assuming shift right instead of left
• Not updating q each cycle
• Mixing bit order in concatenation

4. Identify the error in this Verilog code for a 4-bit PISO shift register:

module piso_shift(
  input clk,
  input [3:0] parallel_in,
  input load,
  output reg serial_out
);
  reg [3:0] shift_reg;
  always @(posedge clk) begin
    if (load)
      shift_reg <= parallel_in;
    else
      shift_reg <= shift_reg >> 1;
    serial_out <= shift_reg[0];
  end
endmodule

medium

A. Shift direction is wrong; should shift left instead of right

B. serial_out should output shift_reg[3], not shift_reg[0]

C. serial_out should be assigned before shifting

D. load signal should be asynchronous

Solution

1. Step 1: Understand PISO operation

   PISO outputs bits serially starting from the most significant bit (MSB), which is shift_reg[3] here.

2. Step 2: Check serial_out assignment

   Code assigns serial_out = shift_reg[0], which is the least significant bit (LSB), incorrect for PISO.

3. Final Answer:

   serial_out should output shift_reg[3], not shift_reg[0] -> Option B

4. Quick Check:

   PISO outputs MSB first = shift_reg[3] [OK]

Hint: PISO outputs MSB first, so serial_out = shift_reg[3] [OK]

Common Mistakes:

• Assigning serial_out to LSB instead of MSB
• Confusing shift direction for PISO
• Thinking load must be asynchronous

5. You want to design a shift register that takes 8-bit parallel data and outputs it serially one bit per clock cycle. Which type of shift register should you use and how would you implement the output logic in Verilog?

hard

A. Use a PIPO shift register; input parallel data and output parallel data

B. Use a SIPO shift register; input serial data and output parallel bits

C. Use a PISO shift register; load 8-bit data and shift out MSB serially each clock

D. Use a SISO shift register; input serial data and output serial data

Solution

1. Step 1: Identify required functionality

   The design needs to convert parallel input to serial output, which matches PISO behavior.

2. Step 2: Describe implementation

   Load 8-bit parallel data into a register on load signal, then shift right each clock cycle outputting MSB (or LSB depending on design) as serial output.

3. Final Answer:

   Use a PISO shift register; load 8-bit data and shift out MSB serially each clock -> Option C

4. Quick Check:

   Parallel to serial = PISO shift register [OK]

Hint: Parallel input to serial output means use PISO shift register [OK]

Common Mistakes:

• Choosing SIPO instead of PISO
• Confusing serial input with parallel input
• Using SISO which only shifts serial data