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?"