Priority encoder in VHDL - Time & Space Complexity

Time Complexity: Priority encoder

O(n)

Understanding Time Complexity

We want to understand how the time it takes to find the highest priority input grows as the number of inputs increases in a priority encoder.

How does the work change when we have more input signals to check?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

architecture Behavioral of priority_encoder is
begin
  process(inputs)
  begin
    output <= (others => '0');
    for i in inputs'range loop
      if inputs(i) = '1' then
        output <= std_logic_vector(to_unsigned(i, output'length));
        exit;
      end if;
    end loop;
  end process;
end Behavioral;

This code checks each input in order to find the first one that is high and outputs its index.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that checks each input bit one by one.
• How many times: Up to n times, where n is the number of input bits.

How Execution Grows With Input

As the number of inputs grows, the process may need to check more bits before finding the first high one.

Input Size (n)	Approx. Operations
10	Up to 10 checks
100	Up to 100 checks
1000	Up to 1000 checks

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

Final Time Complexity

Time Complexity: O(n)

This means the time to find the highest priority input grows linearly as the number of inputs increases.

Common Mistake

[X] Wrong: "The priority encoder always takes the same time no matter how many inputs it has."

[OK] Correct: Because the encoder may need to check each input until it finds the first high one, so more inputs can mean more checks and more time.

Interview Connect

Understanding how the time grows with input size helps you explain how hardware or code scales, a useful skill when designing or analyzing digital circuits.

Self-Check

"What if the inputs were checked in parallel instead of one by one? How would the time complexity change?"

Practice

1.

What is the main function of a priority encoder in VHDL?

easy

A. It adds two binary numbers together.

B. It stores data temporarily.

C. It outputs the binary code of the highest priority active input.

D. It converts analog signals to digital.

Solution

1. Step 1: Understand the role of a priority encoder

   A priority encoder checks multiple inputs and finds the one with the highest priority that is active (usually '1').

2. Step 2: Identify the output behavior

   It outputs the binary code representing the position of that highest priority active input.

3. Final Answer:

   It outputs the binary code of the highest priority active input. -> Option C

4. Quick Check:

   Priority encoder = highest priority input code [OK]

Hint: Remember: priority encoder picks highest active input [OK]

Common Mistakes:

• Confusing priority encoder with adder
• Thinking it stores data like a register
• Mixing it up with analog-to-digital converter

2.

Which of the following is the correct VHDL syntax to declare a 4-to-2 priority encoder entity?

entity PriorityEncoder is
  Port (
    inputs : in std_logic_vector(3 downto 0);
    output : out std_logic_vector(1 downto 0)
  );
end PriorityEncoder;

easy

A. entity PriorityEncoder is
Port (
inputs : in std_logic_vector(3 downto 0);
output : out std_logic_vector(2 downto 0)
);
end PriorityEncoder;

B. entity PriorityEncoder is
Port (
inputs : in std_logic_vector(3 downto 0);
output : out std_logic_vector(1 downto 0)
);
end PriorityEncoder;

C. entity PriorityEncoder is
Port (
inputs : in std_logic_vector(0 to 3);
output : out std_logic_vector(1 downto 0)
);
end PriorityEncoder;

D. entity PriorityEncoder is
Port (
inputs : out std_logic_vector(3 downto 0);
output : in std_logic_vector(1 downto 0)
);
end PriorityEncoder;

Solution

1. Step 1: Check input and output directions

   Inputs should be in and outputs should be out. entity PriorityEncoder is Port ( inputs : in std_logic_vector(3 downto 0); output : out std_logic_vector(1 downto 0) ); end PriorityEncoder; correctly declares inputs as in and output as out.

2. Step 2: Verify vector ranges

   Inputs are 4 bits (3 downto 0) and output is 2 bits (1 downto 0), matching a 4-to-2 encoder. entity PriorityEncoder is Port ( inputs : in std_logic_vector(3 downto 0); output : out std_logic_vector(1 downto 0) ); end PriorityEncoder; matches this exactly.

3. Final Answer:

   Correct entity declaration with inputs as in and outputs as out, proper vector ranges. -> Option B

4. Quick Check:

   Input in, output out, correct vector sizes [OK]

Hint: Inputs are 'in', outputs are 'out' with correct vector sizes [OK]

Common Mistakes:

• Swapping input and output directions
• Using wrong vector ranges (e.g., 0 to 3 instead of 3 downto 0)
• Declaring output vector size incorrectly

3.

Given the following VHDL process for a 4-to-2 priority encoder, what will be the output when inputs = "0101"?

process(inputs)
begin
  case inputs is
    when "1000" => output <= "11";
    when "0100" => output <= "10";
    when "0010" => output <= "01";
    when "0001" => output <= "00";
    when others => output <= "00";
  end case;
end process;

medium

A. "00"

B. "11"

C. "01"

D. "10"

Solution

1. Step 1: Analyze the input pattern

   The input is "0101", which means bits 3 and 1 are active (bit 3 is MSB). The process checks exact matches only.

2. Step 2: Check case matches

   The case matches only exact inputs: "1000", "0100", "0010", "0001". "0101" does not match any, so it falls to when others.

3. Final Answer:

   Output is "00" from the when others clause. -> Option A

4. Quick Check:

   No exact match input = output "00" [OK]

Hint: Case matches exact inputs; else outputs default [OK]

Common Mistakes:

• Assuming partial matches trigger output
• Ignoring the when others clause
• Misreading input bit order

4.

Identify the error in this VHDL priority encoder process snippet:

process(inputs)
begin
  if inputs(0) = '1' then
    output <= "00";
  elsif inputs(1) = '1' then
    output <= "01";
  elsif inputs(2) = '1' then
    output <= "10";
  elsif inputs(3) = '1' then
    output <= "11";
  end if;
end process;

medium

A. The priority order is reversed; highest priority should be inputs(3).

B. The output vector size is incorrect.

C. The process is missing a sensitivity list.

D. The if-elsif structure should use case statement instead.

Solution

1. Step 1: Check priority order in conditions

   The process checks inputs starting from inputs(0) to inputs(3). This means input 0 has highest priority, which is usually incorrect for priority encoders.

2. Step 2: Understand typical priority encoder behavior

   Priority encoders usually assign highest priority to the highest index input (inputs(3) here). So the order should start checking inputs(3) first.

3. Final Answer:

   Priority order is reversed; highest priority should be inputs(3). -> Option A

4. Quick Check:

   Highest input bit checked first for priority [OK]

Hint: Check priority order: highest input bit first [OK]

Common Mistakes:

• Checking lowest bit first as highest priority
• Forgetting to include all inputs in conditions
• Confusing sensitivity list with process body

5.

You want to design a 8-to-3 priority encoder in VHDL that outputs the binary position of the highest priority input bit set to '1'. Which approach correctly implements this behavior?

process(inputs)
begin
  output <= "000";
  if inputs(7) = '1' then
    output <= "111";
  elsif inputs(6) = '1' then
    output <= "110";
  elsif inputs(5) = '1' then
    output <= "101";
  elsif inputs(4) = '1' then
    output <= "100";
  elsif inputs(3) = '1' then
    output <= "011";
  elsif inputs(2) = '1' then
    output <= "010";
  elsif inputs(1) = '1' then
    output <= "001";
  elsif inputs(0) = '1' then
    output <= "000";
  end if;
end process;

hard

A. This approach is incorrect; output should be assigned only once outside the process.

B. This approach is incorrect; it should use a case statement instead of if-elsif.

C. This approach is incorrect; inputs should be checked from lowest to highest.

D. This approach is correct; it checks inputs from highest to lowest and assigns output accordingly.

Solution

1. Step 1: Verify priority checking order

   The process checks inputs starting from inputs(7) down to inputs(0), which is correct for highest priority first.

2. Step 2: Confirm output assignment matches input position

   Output is assigned the binary code of the input bit position, matching the highest active input.

3. Step 3: Check default output assignment

   Output is initialized to "000" before checks, so if no inputs are active, output remains zero.

4. Final Answer:

   This approach is correct; it checks inputs from highest to lowest and assigns output accordingly. -> Option D

5. Quick Check:

   Highest to lowest check with matching output [OK]

Hint: Check inputs highest to lowest, assign output immediately [OK]

Common Mistakes:

• Checking inputs in wrong order
• Assigning output multiple times incorrectly
• Using case instead of if-elsif is optional, not required