Multiplexers, Shannon's Expansion & Universal Logic Synthesis

A Multiplexer (MUX) is a combinational selector that routes one of 2^n data inputs to a single output based on n select lines.

Why Multiplexers are Universal: Multiplexers are fundamentally hardware implementations of truth tables. By connecting variables to select lines, each data input I_i corresponds to a specific row (or pair of rows) of the truth table.

Synthesis Strategies:

1. n-variable function with 2^n:1 MUX: Connect all n variables to the select lines. Connect I_i = 1 if minterm m_i is in the function, and I_i = 0 otherwise.

2. (n+1)-variable function with 2^n:1 MUX: Connect n variables to the select lines. For each combination of the select variables, express the output as a function of the remaining single variable C. The value of each I_i will be one of: 0, 1, C, or C'.

3. Modular Expansion: To construct a 2^n:1 MUX using 2^k:1 MUXes (k < n), the total number of smaller multiplexers required is given by the geometric series: \sum_{i=1}^{\lceil n/k \rceil} \frac{2^n}{2^{k \cdot i}}. Specifically, to build a 2^n:1 MUX entirely from 2:1 MUXes requires exactly 2^n - 1 modules.