Conditional assignment (when-else) in VHDL - Time & Space Complexity

Time Complexity: Conditional assignment (when-else)

O(n)

Understanding Time Complexity

We want to understand how the time to run a conditional assignment in VHDL changes as inputs change.

Specifically, does the number of conditions affect how long it takes to decide the output?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

signal a, b, c, d : std_logic;
signal sel : std_logic_vector(1 downto 0);
signal out_signal : std_logic;

out_signal <= a when sel = "00" else
              b when sel = "01" else
              c when sel = "10" else
              d;
    

This code chooses one signal to assign to out_signal based on the value of sel.

Identify Repeating Operations

• Primary operation: Checking conditions in sequence to find a match.
• How many times: At most, it checks each condition once in order until one matches.

How Execution Grows With Input

As the number of conditions grows, the checks increase linearly.

Input Size (number of conditions)	Approx. Operations (condition checks)
2	Up to 2 checks
5	Up to 5 checks
10	Up to 10 checks

Pattern observation: The number of checks grows directly with the number of conditions.

Final Time Complexity

Time Complexity: O(n)

This means the time to decide the output grows in a straight line with the number of conditions.

Common Mistake

[X] Wrong: "The conditional assignment runs in constant time no matter how many conditions there are."

[OK] Correct: Because each condition is checked in order, more conditions mean more checks, so time grows with the number of conditions.

Interview Connect

Understanding how condition checks add up helps you reason about hardware design speed and efficiency, a useful skill in many design tasks.

Self-Check

"What if we replaced the when-else chain with a case statement? How would the time complexity change?"

Practice

1. What does the VHDL when-else statement do?

easy

A. Assigns a value to a signal based on a condition

B. Defines a loop to repeat actions

C. Declares a new signal type

D. Starts a process block

Solution

1. Step 1: Understand the purpose of when-else

   The when-else statement is used to assign values conditionally to signals in VHDL.

2. Step 2: Compare with other options

   Loops, signal declarations, and process blocks serve different purposes unrelated to conditional assignment.

3. Final Answer:

   Assigns a value to a signal based on a condition -> Option A

4. Quick Check:

   when-else = conditional assignment [OK]

Hint: Think of when-else as a quick if-else for signals [OK]

Common Mistakes:

• Confusing when-else with loops
• Thinking it declares signals
• Mixing it with process blocks

2. Which of the following is the correct syntax for a conditional assignment using when-else in VHDL?

easy

A. signal_name -> value1 when condition else value2;

B. signal_name <= value1 when condition else value2;

C. signal_name = value1 when condition else value2;

D. signal_name := value1 when condition else value2;

Solution

1. Step 1: Recall VHDL assignment operator

   In VHDL, signal assignment uses the '<=' operator, not ':=' or '='.

2. Step 2: Check the full syntax

   The correct syntax is: signal_name <= value1 when condition else value2;

3. Final Answer:

   signal_name <= value1 when condition else value2; -> Option B

4. Quick Check:

   Use '<=' for signal assignment with when-else [OK]

Hint: Use '<=' for signals, not ':=' or '=' [OK]

Common Mistakes:

• Using ':=' instead of '<=' for signals
• Using '=' which is for variables
• Confusing arrow operators

3. Given the VHDL code:

signal out_signal : std_logic;

out_signal <= '1' when input_signal = '1' else '0';

What will be the value of out_signal if input_signal is '0'?

medium

A. '0'

B. '1'

C. 'Z' (high impedance)

D. Undefined

Solution

1. Step 1: Analyze the condition

   The assignment says out_signal is '1' when input_signal = '1', else '0'.

2. Step 2: Apply input value

   Since input_signal is '0', the condition is false, so out_signal gets '0'.

3. Final Answer:

   '0' -> Option A

4. Quick Check:

   Condition false -> else value '0' assigned [OK]

Hint: If condition false, value after else is assigned [OK]

Common Mistakes:

• Assigning '1' when input is '0'
• Confusing high impedance 'Z' with '0'
• Thinking output is undefined

4. Identify the error in this VHDL conditional assignment:

signal result : std_logic;

result <= '1' when input = 1 else '0';

medium

A. Using '<=' instead of ':=' for assignment

B. Missing semicolon at the end

C. Signal name cannot be 'result'

D. Input comparison uses integer instead of character

Solution

1. Step 1: Check the condition type

   The input signal is likely std_logic, so it should be compared to a character like '1', not integer 1.

2. Step 2: Identify correct comparison

   Correct comparison is input = '1' (with single quotes) for std_logic.

3. Final Answer:

   Input comparison uses integer instead of character -> Option D

4. Quick Check:

   Compare std_logic with character '1' not integer 1 [OK]

Hint: Use single quotes for std_logic values in conditions [OK]

Common Mistakes:

• Comparing std_logic to integer without quotes
• Confusing assignment operators
• Assuming signal names are restricted

5. You want to assign a 4-bit output signal y based on a 2-bit input sel using conditional assignment. If sel is "00", assign "0001"; if "01", assign "0010"; else assign "0000". Which is the correct VHDL code?

hard

A. y := "0001" when sel = "00" else "0010" when sel = "01" else "0000";

B. y <= "0001" when sel = "00" else ("0010" when sel = "01" else "0000");

C. y <= "0001" when sel = "00" else "0010" when sel = "01" else "0000";

D. y <= '0001' when sel = "00" else '0010' when sel = "01" else '0000";

Solution

1. Step 1: Recall syntax for multiple conditions

   In VHDL, chain conditional assignments as: value1 when cond1 else value2 when cond2 else value3. No parentheses needed.

2. Step 2: Compare options

   y <= "0001" when sel = "00" else "0010" when sel = "01" else "0000"; matches the correct chained syntax.

3. Final Answer:

   y <= "0001" when sel = "00" else "0010" when sel = "01" else "0000"; -> Option C

4. Quick Check:

   Chained when-else without parentheses [OK]

Hint: Chain with else when, no parentheses needed [OK]

Common Mistakes:

• Using := for signal assignment
• Adding unnecessary parentheses around conditions
• Using single quotes for std_logic_vector literals