Multiplexer design in VHDL - Time & Space Complexity

Time Complexity: Multiplexer design in VHDL

O(log n)

Understanding Time Complexity

When designing a multiplexer in VHDL, time complexity refers to the combinational propagation delay: how the critical path delay scales as the number of inputs grows.

We analyze how the hardware delay changes with multiplexer size after synthesis.

Scenario Under Consideration

Analyze the time complexity (propagation delay) of the following synthesized VHDL multiplexer code.

architecture Behavioral of mux is
  begin
    process(sel, inputs)
    begin
      case sel is
        when "00" => output <= inputs(0);
        when "01" => output <= inputs(1);
        when "10" => output <= inputs(2);
        when "11" => output <= inputs(3);
        when others => output <= '0';
      end case;
    end process;
  end Behavioral;

This behavioral description synthesizes to efficient hardware logic.

Identify Repeating Operations

The case statement synthesizes to a parallel decoder (one-hot select lines) followed by a reduction tree (OR of input-AND-select).

• Primary structure: Balanced gate trees for decoding and selection.
• Depth growth: Logarithmic levels of gates, no sequential repeats.

How Execution Grows With Input

Synthesizers implement muxes using Shannon decomposition or LUT trees, leading to logarithmic delay growth.

Input Size (n)	Approx. Gate Levels (Delay)
4	2-3 levels
8	3-4 levels
16	4-5 levels

Pattern observation: Delay grows as O(log n).

Final Time Complexity

Time Complexity: O(log n)

The propagation delay grows logarithmically with the number of inputs.

Common Mistake

[X] Wrong: "The selection happens instantly (O(1)) no matter the input count."

[OK] Correct: Larger muxes require deeper logic levels in the synthesized gate/LUT tree, increasing delay.

Interview Connect

Understanding logarithmic scaling in mux delay helps discuss synthesis optimizations and efficient hardware design in interviews.

Self-Check

"What if we implemented it as a linear chain of 2:1 muxes? How would the time complexity change?"

Practice

1. What is the main purpose of a multiplexer in VHDL design?

easy

A. To perform arithmetic operations on inputs

B. To store data temporarily

C. To select one input from multiple inputs and send it to the output

D. To generate clock signals

Solution

1. Step 1: Understand the function of a multiplexer

   A multiplexer chooses one input from many inputs based on selector signals.

2. Step 2: Identify the correct purpose

   It outputs the selected input to a single output line.

3. Final Answer:

   To select one input from multiple inputs and send it to the output -> Option C

4. Quick Check:

   Multiplexer = input selector [OK]

Hint: Multiplexer picks one input to output [OK]

Common Mistakes:

• Confusing multiplexer with arithmetic unit
• Thinking multiplexer stores data
• Assuming multiplexer generates clocks

2. Which of the following is the correct way to declare a 4-to-1 multiplexer selector signal in VHDL?

easy

A. signal sel : integer range 0 to 3;

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

C. signal sel : std_logic;

D. signal sel : std_logic_vector(1 downto 0);

Solution

1. Step 1: Determine selector size for 4 inputs

   For 4 inputs, selector needs 2 bits (log2(4) = 2).

2. Step 2: Match selector declaration

   std_logic_vector(1 downto 0) is 2 bits wide, correct for 4-to-1 mux.

3. Final Answer:

   signal sel : std_logic_vector(1 downto 0); -> Option D

4. Quick Check:

   2-bit selector for 4 inputs [OK]

Hint: Selector bits = log2(number of inputs) [OK]

Common Mistakes:

• Using 4 bits for selector of 4 inputs
• Using single bit for multiple inputs
• Using integer instead of std_logic_vector

3. Given the following VHDL code for a 2-to-1 multiplexer, what will be the output y when sel = '1' and inputs are a = '0', b = '1'?

process(sel, a, b)
begin
  if sel = '0' then
    y <= a;
  else
    y <= b;
  end if;
end process;

medium

A. '1'

B. '0'

C. 'Z'

D. No output (error)

Solution

1. Step 1: Check selector value and inputs

   Selector sel = '1', inputs a = '0', b = '1'.

2. Step 2: Follow if-else logic

   If sel = '0', output y = a; else y = b. Since sel = '1', y = b = '1'.

3. Final Answer:

   '1' -> Option A

4. Quick Check:

   sel=1 outputs b=1 [OK]

Hint: If sel=1 output b else a [OK]

Common Mistakes:

• Confusing sel '0' and '1' cases
• Assuming output is 'Z' (high impedance)
• Ignoring input values

4. Identify the error in this 4-to-1 multiplexer VHDL code snippet:

process(sel, d0, d1, d2, d3)
begin
  case sel is
    when "00" => y <= d0;
    when "01" => y <= d1;
    when "10" => y <= d2;
    when others => y <= d3;
  end case;
end process;

medium

A. Selector signal sel is not declared as 2 bits wide

B. Missing sensitivity list signals

C. Using 'when others' instead of explicit cases

D. Output y is not assigned in all cases

Solution

1. Step 1: Check selector declaration

   The code uses sel as 2-bit vector ("00", "01", "10"), so sel must be declared as std_logic_vector(1 downto 0).

2. Step 2: Identify missing or incorrect declaration

   If sel is not declared as 2 bits wide, the case statement will cause errors.

3. Final Answer:

   Selector signal sel is not declared as 2 bits wide -> Option A

4. Quick Check:

   Selector width must match case values [OK]

Hint: Selector width must match case patterns [OK]

Common Mistakes:

• Forgetting to declare selector width
• Leaving out signals in sensitivity list
• Misusing 'when others' in case

5. You want to design an 8-to-1 multiplexer in VHDL using a case statement. Which of the following selector signal declarations and case statement headers is correct?

hard

A. signal sel : std_logic;
...
case sel is
when '0' => ...
when '1' => ...

B. signal sel : std_logic_vector(2 downto 0);
...
case sel is
when "000" => ...
when "111" => ...

C. signal sel : std_logic_vector(1 downto 0);
...
case sel is
when "00" => ...
when "11" => ...

D. signal sel : std_logic_vector(3 downto 0);
...
case sel is
when "0000" => ...
when "0111" => ...

Solution

1. Step 1: Determine selector size for 8 inputs

   8 inputs require 3 bits selector (log2(8) = 3), so sel must be 3 bits wide.

2. Step 2: Match selector declaration and case values

   signal sel : std_logic_vector(2 downto 0); ... case sel is when "000" => ... when "111" => ... uses std_logic_vector(2 downto 0) which is 3 bits, and case values from "000" to "111" which is correct.

3. Final Answer:

   signal sel : std_logic_vector(2 downto 0); ... case sel is when "000" => ... when "111" => ... -> Option B

4. Quick Check:

   3-bit selector for 8 inputs [OK]

Hint: Use 3-bit selector for 8 inputs [OK]

Common Mistakes:

• Using 4 bits for 8 inputs selector
• Using 1 or 2 bits for 8 inputs
• Mismatching case values and selector width