Shift register in VHDL - Time & Space Complexity

Time Complexity: Shift register in VHDL

O(n)

Understanding Time Complexity

We want to understand how the time to run a shift register changes as its size grows.

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

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

process(clk)
begin
  if rising_edge(clk) then
    shift_reg <= shift_reg(shift_reg'length-2 downto 0) & data_in;
  end if;
end process;
    

This code shifts all bits in the register to the left by one and inserts a new bit at the right on each clock.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Moving each bit one position to the left inside the shift register.
• How many times: This happens once every clock cycle, affecting all bits in the register.

How Execution Grows With Input

As the register size grows, the number of bits moved each clock grows too.

Input Size (n)	Approx. Operations
10	9 bit moves per clock
100	99 bit moves per clock
1000	999 bit moves per clock

Pattern observation: The work grows directly with the number of bits in the register.

Final Time Complexity

Time Complexity: O(n)

This means the time to shift grows in a straight line as the register gets bigger.

Common Mistake

[X] Wrong: "Shifting bits happens instantly no matter the register size."

[OK] Correct: Each bit must move one step, so more bits mean more work and more time.

Interview Connect

Understanding how operations grow with input size helps you explain hardware behavior clearly and shows you think about efficiency.

Self-Check

"What if we used parallel loading instead of shifting? How would the time complexity change?"

Practice

1. What is the main purpose of a shift register in VHDL?

easy

A. To perform arithmetic operations on numbers

B. To move bits step by step on each clock pulse

C. To store large amounts of data permanently

D. To generate random numbers

Solution

1. Step 1: Understand the function of a shift register

   A shift register moves bits through a series of flip-flops, shifting data on each clock pulse.

2. Step 2: Compare options with the function

   Only To move bits step by step on each clock pulse describes moving bits step by step on clock pulses, which matches the shift register's purpose.

3. Final Answer:

   To move bits step by step on each clock pulse -> Option B

4. Quick Check:

   Shift register = bit shifting [OK]

Hint: Shift register moves bits on clock edges [OK]

Common Mistakes:

• Confusing shift register with memory storage
• Thinking it performs arithmetic
• Assuming it generates random data

2. Which of the following is the correct way to declare a 4-bit shift register signal in VHDL?

easy

A. signal shift_reg : bit_vector(0 to 4);

B. signal shift_reg : integer range 0 to 3;

C. signal shift_reg : std_logic_vector(0 to 4);

D. signal shift_reg : std_logic_vector(3 downto 0);

Solution

1. Step 1: Understand VHDL signal declaration for vectors

   In VHDL, std_logic_vector is used for bit vectors, and ranges are usually declared with downto for descending indexes.

2. Step 2: Check each option

   signal shift_reg : std_logic_vector(3 downto 0); uses std_logic_vector(3 downto 0), which is correct for a 4-bit vector. signal shift_reg : integer range 0 to 3; uses integer, which is incorrect. signal shift_reg : bit_vector(0 to 4); uses bit_vector but with wrong range size (0 to 4 is 5 bits). signal shift_reg : std_logic_vector(0 to 4); uses std_logic_vector but with wrong range size (0 to 4 is 5 bits).

3. Final Answer:

   signal shift_reg : std_logic_vector(3 downto 0); -> Option D

4. Quick Check:

   std_logic_vector with downto for 4 bits = signal shift_reg : std_logic_vector(3 downto 0); [OK]

Hint: Use std_logic_vector(3 downto 0) for 4-bit register [OK]

Common Mistakes:

• Using integer instead of vector type
• Incorrect vector range size
• Confusing bit_vector with std_logic_vector

3. Given the following VHDL process for a 4-bit shift register, what will be the value of shift_reg after two rising clock edges if the input data_in is '1' and initial shift_reg is "0000"?

process(clk)
begin
  if rising_edge(clk) then
    shift_reg <= data_in & shift_reg(3 downto 1);
  end if;
end process;

medium

A. "1000"

B. "1110"

C. "1100"

D. "0011"

Solution

1. Step 1: Understand the shift operation

   On each rising clock edge, the new bit data_in ('1') is shifted into the leftmost bit, and the rest of the bits shift right by one.

2. Step 2: Calculate after first clock edge

   Initial shift_reg = "0000".
   After first clock: shift_reg = '1' & "000" = "1000".

3. Step 3: Calculate after second clock edge

   Now shift_reg = "1000".
   After second clock: shift_reg = '1' & "100" = "1100".

4. Final Answer:

   "1100" -> Option C

5. Quick Check:

   Shift left with input '1' twice = "1100" [OK]

Hint: Concatenate input with shifted bits each clock [OK]

Common Mistakes:

• Not shifting bits correctly
• Confusing bit order in concatenation
• Forgetting initial value

4. Identify the error in this VHDL shift register process:

process(clk)
begin
  if clk = '1' then
    shift_reg <= data_in & shift_reg(3 downto 1);
  end if;
end process;

medium

A. Incorrect clock edge detection

B. Missing reset signal

C. Wrong concatenation order

D. Signal assignment should use <= not :=

Solution

1. Step 1: Check clock condition

   The process uses if clk = '1' then which triggers whenever clk is high, not just on rising edge.

2. Step 2: Correct clock edge detection

   Proper edge detection in VHDL uses if rising_edge(clk) then to trigger only on the clock's rising edge.

3. Final Answer:

   Incorrect clock edge detection -> Option A

4. Quick Check:

   Use rising_edge(clk) for clock triggers [OK]

Hint: Use rising_edge(clk) for clock events [OK]

Common Mistakes:

• Using clk = '1' instead of rising_edge(clk)
• Ignoring reset signal importance
• Confusing signal assignment operators

5. You want to design a 4-bit shift register in VHDL that shifts right on each clock and asynchronously resets to "0000". Which code snippet correctly implements this behavior?

hard

A. process(clk, reset)
begin
if reset = '1' then
shift_reg <= (others => '0');
elsif rising_edge(clk) then
shift_reg <= shift_reg(2 downto 0) & data_in;
end if;
end process;

B. process(clk)
begin
if rising_edge(clk) then
if reset = '1' then
shift_reg <= (others => '0');
else
shift_reg <= data_in & shift_reg(3 downto 1);
end if;
end if;
end process;

C. process(reset, clk)
begin
if rising_edge(clk) then
if reset = '1' then
shift_reg <= (others => '0');
else
shift_reg <= shift_reg(3 downto 1) & data_in;
end if;
end if;
end process;

D. process(reset, clk)
begin
if reset = '1' then
shift_reg <= (others => '0');
elsif rising_edge(clk) then
shift_reg <= shift_reg(3 downto 1) & data_in;
end if;
end process;

Solution

1. Step 1: Identify asynchronous reset

   An asynchronous reset is checked first in the sensitivity list and outside the clock edge condition, so if reset = '1' then comes before elsif rising_edge(clk).

2. Step 2: Check shift direction and concatenation

   Shifting right means bits move to lower indexes, so new bit data_in is concatenated at the right end: shift_reg(2 downto 0) & data_in.

3. Step 3: Verify code snippet

   process(clk, reset) begin if reset = '1' then shift_reg <= (others => '0'); elsif rising_edge(clk) then shift_reg <= shift_reg(2 downto 0) & data_in; end if; end process; matches asynchronous reset first, then rising edge clock shift right with correct concatenation.

4. Final Answer:

   process(clk, reset) begin if reset = '1' then shift_reg <= (others => '0'); elsif rising_edge(clk) then shift_reg <= shift_reg(2 downto 0) & data_in; end if; end process; -> Option A

5. Quick Check:

   Async reset first, then shift right = process(clk, reset) begin if reset = '1' then shift_reg <= (others => '0'); elsif rising_edge(clk) then shift_reg <= shift_reg(2 downto 0) & data_in; end if; end process; [OK]

Hint: Async reset checked before clock edge [OK]

Common Mistakes:

• Placing reset inside clock edge condition
• Wrong bit concatenation order for shift direction
• Missing reset in sensitivity list