Resource inference rules in VHDL - Time & Space Complexity

Time Complexity: Resource inference rules

O(n)

Understanding Time Complexity

When VHDL code is turned into hardware, the resources used depend on how the code is written.

We want to understand how the amount of hardware resources grows as the input size changes.

Scenario Under Consideration

Analyze the time complexity of the following VHDL code snippet.

process(clk)
  begin
    if rising_edge(clk) then
      for i in 0 to N-2 loop
        output(i) <= input(i) and input(i+1);
      end loop;
    end if;
end process;

This code uses a loop to combine pairs of input bits and assign them to output bits on each clock cycle.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that runs from 0 to N-2.
• How many times: It runs N-1 times each clock cycle.

How Execution Grows With Input

As the input size N grows, the number of operations grows in a straight line with N.

Input Size (n)	Approx. Operations
10	9 operations
100	99 operations
1000	999 operations

Pattern observation: Doubling the input size roughly doubles the number of operations.

Final Time Complexity

Time Complexity: O(n)

This means the work grows directly in proportion to the input size.

Common Mistake

[X] Wrong: "The loop runs a fixed number of times, so the resource use is constant."

[OK] Correct: The loop count depends on N, so as N grows, the hardware needed grows too.

Interview Connect

Understanding how loops in VHDL affect resource use helps you design efficient hardware and explain your design choices clearly.

Self-Check

"What if the loop was nested inside another loop of size M? How would the time complexity change?"

Practice

1. Which VHDL construct typically causes the compiler to infer a register (flip-flop)?

easy

A. A clocked process with a rising_edge(clock) condition

B. A simple concurrent signal assignment

C. A combinational process without clock sensitivity

D. A constant declaration

Solution

1. Step 1: Understand what infers registers

   Registers (flip-flops) are inferred when signals are assigned inside a process triggered by a clock edge, such as rising_edge(clock).

2. Step 2: Identify the correct construct

   A clocked process with rising_edge(clock) matches this condition, so it infers registers.

3. Final Answer:

   A clocked process with a rising_edge(clock) condition -> Option A

4. Quick Check:

   Clocked process = register inference [OK]

Hint: Registers come from clocked processes with edge checks [OK]

Common Mistakes:

• Confusing combinational assignments with registers
• Thinking constants infer registers
• Ignoring the clock edge condition

2. Which of the following VHDL code snippets correctly infers combinational logic?

easy

A. q <= a and b;

B. signal r : std_logic_vector(3 downto 0);

C. constant c : integer := 5;

D. process(clk) begin if rising_edge(clk) then q <= d; end if; end process;

Solution

1. Step 1: Identify combinational logic inference

   Combinational logic is inferred from concurrent signal assignments or processes without clock edges.

2. Step 2: Check each option

   q <= a and b; is a concurrent assignment using logical AND, which infers combinational logic.

3. Final Answer:

   q <= a and b; -> Option A

4. Quick Check:

   Concurrent assignment = combinational logic [OK]

Hint: Combinational logic comes from simple concurrent assignments [OK]

Common Mistakes:

• Choosing clocked processes for combinational logic
• Confusing constants or signals with logic inference
• Ignoring the absence of clock edges

3. Given the following VHDL code, what hardware resource is inferred?

process(clk, a, b)
begin
  if rising_edge(clk) then
    q <= a or b;
  end if;
end process;

medium

A. Combinational logic only

B. Register (flip-flop) with combinational logic inside

C. Constant value

D. Latch

Solution

1. Step 1: Analyze the process sensitivity and clock usage

   The process is sensitive to clk, a, and b, but the assignment happens only on rising_edge(clk), indicating a clocked process.

2. Step 2: Determine inferred hardware

   Because the assignment is inside a clock edge condition, a register (flip-flop) is inferred. The expression 'a or b' is combinational logic feeding the register input.

3. Final Answer:

   Register (flip-flop) with combinational logic inside -> Option B

4. Quick Check:

   Clock edge + logic = register with combinational input [OK]

Hint: Clock edge inside process means register inferred [OK]

Common Mistakes:

• Ignoring the clock edge and thinking it's pure combinational
• Confusing latch with register
• Assuming constants are inferred

4. Identify the error in this VHDL code that prevents correct resource inference:

process(clk)
begin
  if clk = '1' then
    q <= d;
  end if;
end process;

medium

A. Signal q is not declared

B. Process sensitivity list is empty

C. Missing rising_edge(clk) condition for clocked process

D. Constant d is used instead of signal

Solution

1. Step 1: Check clock condition usage

   The process uses 'if clk = '1'' instead of 'if rising_edge(clk)', which is the standard way to infer registers.

2. Step 2: Understand impact on resource inference

   Without rising_edge(clk), the compiler may infer a latch or incorrect hardware instead of a register.

3. Final Answer:

   Missing rising_edge(clk) condition for clocked process -> Option C

4. Quick Check:

   Use rising_edge(clk) for registers [OK]

Hint: Always use rising_edge(clk) for registers [OK]

Common Mistakes:

• Using level-sensitive clock check instead of edge
• Ignoring sensitivity list correctness
• Assuming signal declarations cause inference errors

5. You want to infer a 4-bit register with asynchronous reset in VHDL. Which code snippet correctly follows resource inference rules?

hard

A. process(reset) begin if reset = '1' then q <= (others => '0'); end if; end process;

B. process(clk) begin if rising_edge(clk) then if reset = '1' then q <= (others => '0'); else q <= d; end if; end if; end process;

C. q <= d when reset = '0' else (others => '0');

D. process(clk, reset) begin if reset = '1' then q <= (others => '0'); elsif rising_edge(clk) then q <= d; end if; end process;

Solution

1. Step 1: Identify asynchronous reset structure

   An asynchronous reset requires the reset signal in the sensitivity list and a separate if condition before the clock edge check.

2. Step 2: Check each option for correct inference

   process(clk, reset) begin if reset = '1' then q <= (others => '0'); elsif rising_edge(clk) then q <= d; end if; end process; has reset and clk in sensitivity list, checks reset first, then rising_edge(clk), correctly inferring a register with async reset.

3. Final Answer:

   process(clk, reset) begin if reset = '1' then q <= (others => '0'); elsif rising_edge(clk) then q <= d; end if; end process; -> Option D

4. Quick Check:

   Async reset in sensitivity + if reset first = correct [OK]

Hint: Async reset must be checked before clock edge in process [OK]

Common Mistakes:

• Placing reset check inside clock edge condition (sync reset)
• Missing reset in sensitivity list for async reset
• Using conditional assignments outside process for registers