Process execution semantics in VHDL - Time & Space Complexity

Time Complexity: Process execution semantics

O(N)

Understanding Time Complexity

We want to understand how the time it takes for a VHDL process to run changes as the inputs or conditions change.

Specifically, we ask: how does the process execution time grow when the signals it watches change more often or when the process has more statements?

Scenario Under Consideration

Analyze the time complexity of the following VHDL process.

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

This process copies and masks an input array to an output array on each clock rising edge.

Identify Repeating Operations

Look for loops or repeated actions inside the process.

• Primary operation: The for-loop that runs from 0 to N-1.
• How many times: It runs once every clock rising edge, repeating N times per clock.

How Execution Grows With Input

The number of operations grows directly with N, the size of the input array.

Input Size (N)	Approx. Operations per Clock
10	10
100	100
1000	1000

Pattern observation: Doubling N doubles the work done each clock cycle.

Final Time Complexity

Time Complexity: O(N)

This means the process execution time grows linearly with the size of the input array.

Common Mistake

[X] Wrong: "The process runs in constant time because it triggers only on clock edges."

[OK] Correct: Even though the process triggers once per clock, the work inside depends on N, so more inputs mean more operations each time.

Interview Connect

Understanding how process execution time scales helps you design efficient hardware and write clear VHDL code, a skill valuable in many hardware design tasks.

Self-Check

"What if the process had nested loops inside? How would that affect the time complexity?"

Practice

1. What happens when a signal in a VHDL process's sensitivity list changes?

easy

A. The entire process executes from the beginning once.

B. Only the changed signal is updated inside the process.

C. The process pauses until the signal stabilizes.

D. The process executes partially based on the changed signal.

Solution

1. Step 1: Understand sensitivity list trigger

   In VHDL, a process runs fully whenever any signal in its sensitivity list changes.

2. Step 2: Execution behavior

   The process does not partially run or pause; it executes all statements sequentially from the start.

3. Final Answer:

   The entire process executes from the beginning once. -> Option A

4. Quick Check:

   Process runs fully on sensitivity change = A [OK]

Hint: Process runs fully on any sensitivity list signal change [OK]

Common Mistakes:

• Thinking only changed signals update inside process
• Believing process pauses or partially runs
• Confusing process with concurrent statements

2. Which of the following is the correct syntax to declare a process with signals clk and reset in its sensitivity list?

easy

A. process(clk reset) begin ... end process;

B. process begin clk, reset; ... end process;

C. process(clk; reset) begin ... end process;

D. process(clk, reset) begin ... end process;

Solution

1. Step 1: Check sensitivity list syntax

   The sensitivity list must be inside parentheses, with signals separated by commas.

2. Step 2: Validate options

   process(clk, reset) begin ... end process; uses correct syntax: process(clk, reset) begin ... end process; Options A, B, and D have syntax errors (missing commas, wrong separators).

3. Final Answer:

   process(clk, reset) begin ... end process; -> Option D

4. Quick Check:

   Correct sensitivity list syntax uses commas = C [OK]

Hint: Use commas between signals in sensitivity list parentheses [OK]

Common Mistakes:

• Omitting commas between signals
• Using semicolons instead of commas
• Placing signals outside parentheses

3. Given the following VHDL process:

process(clk)
begin
  if rising_edge(clk) then
    count <= count + 1;
  end if;
end process;

What happens to count when clk changes from '0' to '1'?

medium

A. Process causes a syntax error.

B. count resets to 0.

C. count increments by 1.

D. count remains unchanged.

Solution

1. Step 1: Identify trigger condition

   The process triggers on any change of clk. The if rising_edge(clk) checks for a 0 to 1 transition.

2. Step 2: Effect on count

   When clk rises, count increments by 1 as per the assignment.

3. Final Answer:

   count increments by 1. -> Option C

4. Quick Check:

   Rising edge triggers increment = D [OK]

Hint: Rising edge on clk triggers count increment [OK]

Common Mistakes:

• Confusing rising_edge with falling_edge
• Assuming count resets instead of increments
• Thinking process syntax is incorrect

4. Consider this VHDL process:

process(clk)
begin
  if clk = '1' then
    signal_a <= '0';
  else
    signal_a <= '1';
  end if;
end process;

What is the main problem with this process?

medium

A. It will cause a syntax error due to missing sensitivity signals.

B. It may create a latch because it lacks a clock edge condition.

C. It will never execute because clk is not in sensitivity list.

D. It updates signal_a asynchronously, which is always correct.

Solution

1. Step 1: Analyze sensitivity list and conditions

   The process triggers on any clk change, but uses level check (clk = '1') instead of edge detection.

2. Step 2: Understand latch creation

   Because assignments depend on clk level without edge detection, synthesis tools may infer a latch to hold signal_a's value.

3. Final Answer:

   It may create a latch because it lacks a clock edge condition. -> Option B

4. Quick Check:

   Level check without edge causes latch = B [OK]

Hint: Use rising_edge or falling_edge to avoid latches [OK]

Common Mistakes:

• Assuming missing sensitivity signals cause syntax error
• Thinking process won't execute without edge
• Believing asynchronous updates are always safe

5. You want to design a VHDL process that increments a counter only on the rising edge of clk and asynchronously resets it to zero when reset is '1'. Which process structure correctly implements this behavior?

hard

A. process(clk, reset)
begin
if reset = '1' then
count <= 0;
elsif rising_edge(clk) then
count <= count + 1;
end if;
end process;

B. process(clk)
begin
if reset = '1' then
count <= 0;
elsif rising_edge(clk) then
count <= count + 1;
end if;
end process;

C. process(reset)
begin
if reset = '1' then
count <= 0;
elsif rising_edge(clk) then
count <= count + 1;
end if;
end process;

D. process(clk, reset)
begin
if rising_edge(clk) then
if reset = '1' then
count <= 0;
else
count <= count + 1;
end if;
end if;
end process;

Solution

1. Step 1: Identify asynchronous reset

   Asynchronous reset requires reset in sensitivity list and checked before clock edge.

2. Step 2: Check process structure

   process(clk, reset)
   begin
     if reset = '1' then
       count <= 0;
     elsif rising_edge(clk) then
       count <= count + 1;
     end if;
   end process;

   checks reset = '1' first, then rising_edge(clk), correctly implementing async reset and sync count increment.

3. Step 3: Validate other options

   process(clk)
   begin
     if reset = '1' then
       count <= 0;
     elsif rising_edge(clk) then
       count <= count + 1;
     end if;
   end process;

   misses reset in sensitivity list (wrong for async reset).

   process(reset)
   begin
     if reset = '1' then
       count <= 0;
     elsif rising_edge(clk) then
       count <= count + 1;
     end if;
   end process;

   triggers only on reset, ignoring clk.

   process(clk, reset)
   begin
     if rising_edge(clk) then
       if reset = '1' then
         count <= 0;
       else
         count <= count + 1;
       end if;
     end if;
   end process;

   treats reset synchronously inside clock edge.

4. Final Answer:

   process(clk, reset) begin if reset = '1' then count <= 0; elsif rising_edge(clk) then count <= count + 1; end if; end process; -> Option A

5. Quick Check:

   Async reset checked first with reset in sensitivity list = A [OK]

Hint: Put async reset first and include it in sensitivity list [OK]

Common Mistakes:

• Omitting reset from sensitivity list for async reset
• Checking reset inside clock edge (sync reset)
• Using wrong sensitivity list signals