Multiplexers, Decoders, and Shannon Expansion as Logic Realization

A multiplexer is usually introduced as a routing element: several inputs, one output, a select signal that chooses which input appears at the output. That description is correct and hides the reason multiplexers matter to logic design. A multiplexer is a combinational function of its select inputs, and by tying its data inputs to constants or to other signals it can be made to realize any function of those selects. The decoder is its dual, and the pair covers most of what structural logic realization does.

The 2-to-1 multiplexer as a primitive

A 2-to-1 multiplexer has two data inputs $d_0$ and $d_1$, one select $s$, and one output. Its function is

$$y = \bar s \cdot d_0 + s \cdot d_1$$

Compare that with Shannon expansion of a function $f$ on variable $s$:

$$f = \bar s \cdot f(s = 0) + s \cdot f(s = 1)$$

The two expressions have the same shape. The cofactors $f(s=0)$ and $f(s=1)$ — the function with $s$ replaced by a constant — become the data inputs, and $s$ becomes the select. A 2-to-1 multiplexer therefore computes $f$ directly if the cofactors are available as signals, and for a constant cofactor the corresponding input is tied to a rail.

This is not a curiosity. Recursing gives a complete construction: expand on one variable, then expand each cofactor on the next, until each leaf is a constant. The result is a tree of 2-to-1 multiplexers whose leaves are the truth table entries. Depth is the number of variables, and the number of multiplexers is $2^n - 1$ for $n$ variables — the same order as the number of truth table rows, which is why the naive construction is not how anything large is built. Its value is as an existence argument: any function has a multiplexer tree realization, and the tree has a fixed depth.

Real implementations use wider multiplexers. A 4-to-1 multiplexer has depth two in a tree built from 2-to-1 elements, and it can absorb two levels of Shannon expansion at once. A wide multiplexer with constant data inputs is exactly a lookup table, and lookup tables are what field-programmable fabric provides as its primitive.

Decoders and the sum-of-products reconstruction

An $n$-to-$2^n$ decoder takes an $n$-bit input and drives exactly one of its $2^n$ outputs high, the output whose index matches the input value. Functionally, output $i$ is high exactly when the input is the minterm pattern $i$. The decoder is therefore a minterm generator: each output is one minterm of the $n$ input variables.

Given a minterm generator, realizing any function is an OR over the minterms where the function is 1. A decoder plus an OR gate per output bit is a direct hardware realization of a canonical sum of products, described in canonical forms. For a read-only memory, the same structure appears as a decoder driving a matrix of OR connections programmed at manufacture. For a programmable array, the connections are fuses or floating-gate cells.

The cost is transparent. An $n$-to-$2^n$ decoder needs $2^n$ AND gates each with $n$ inputs in the abstract model, plus one OR gate per output function. For $n = 8$ that is 256 product terms before any sharing; the OR planes then select from them. This is the architecture of classic programmable logic devices, and the reason their capacity is expressed as product terms rather than gate counts.

A decoder has a second use that has nothing to do with functions: address decoding. Selecting one memory bank, one peripheral, or one register file entry from an address is exactly what a decoder does, and the requirement that exactly one output be active — no overlap, no gap — is the same one-hot invariant. Design errors in address decoding show up as aliasing, where two addresses reach the same register, or as dead space where no output responds.

Structure	Inputs	Abstract gate count	Realizes
2-to-1 mux	1 select, 2 data	1 AND-OR pair	Any 1-variable function
4-to-1 mux	2 selects, 4 data	tree of 3 2-to-1	Any 2-variable function
$n$-to-$2^n$ decoder	$n$	$2^n$ AND terms	All minterms of $n$ variables
Decoder + OR plane	$n$, $m$ outputs	$2^n$ terms + $m$ ORs	$m$ functions of $n$ variables

Decomposition and the mux as a universal element

Shannon expansion is a decomposition tool, not only a construction. Expanding on the variable that appears in the most terms and recursing produces a multiplexer tree whose data inputs are functions of the remaining variables, and if those functions turn out to be simple — often constants or single literals — the tree collapses to a small circuit.

The choice of expansion variable matters. Expanding on a variable that makes both cofactors simple produces a balanced, shallow tree; expanding on a variable that leaves both cofactors complex produces a tree that duplicates logic on both branches. The two cofactors of a function share all the variables except the expanded one, so a poor choice duplicates the entire remainder of the circuit once per branch.

Multiplexers are also functionally complete on their own, provided constants are available. Tying $d_1$ to 1 and $d_0$ to 0 makes the multiplexer’s output equal to the select, so it inverts nothing but passes a signal. Tying $d_1$ to 0 and $d_0$ to 1 makes it an inverter. Feeding two signals into $d_0$ and $d_1$ with one select produces both a two-input AND and a two-input OR depending on the polarity of the select. Since a functionally complete set is enough to build anything, a fabric of multiplexers and constants is a general-purpose logic substrate. That is essentially the argument behind lookup-table-based programmable logic.

Where the depth comes from

Logic depth determines how fast a circuit can run under a given clock, so the depth of a mux or decoder structure is a first-class design property.

A tree of 2-to-1 multiplexers over $n$ variables has depth $n$ in the number of multiplexer levels, which is linear and therefore poor for large $n$. A single $2^n$-to-1 multiplexer with constant data inputs has constant depth but an input fan-in that grows exponentially and a select decoder inside it that costs a tree of its own. Real designs sit between the extremes: 4-to-1 and 6-to-1 blocks at moderate depth, combined with Boolean logic for the parts of the function that factor well.

The decoder tree has the same shape as a carry-lookahead structure in the sense that it is built from small blocks arranged hierarchically. Every output of an $n$-to-$2^n$ decoder depends on all $n$ input bits, so the depth cannot be less than the depth of an $n$-input AND function, which in a two-input gate library is about $\log_2 n$ levels when built as a balanced tree. This is the same log-depth argument that the timing budget ultimately constrains: a deeper structure leaves less of the clock period for everything else.

Multiplexers are also where the difference between a multiplexer and a set of tristate buffers becomes relevant. A tristate bus resolves contention by enabled drivers, and if two enables overlap the two drivers fight, producing a large current and a level that is neither rail. A multiplexer has no such state: exactly one data input reaches the output by construction, and glitches at the output during a select change are limited to the race between the two paths — the same hazard mechanism described in combinational hazards. This is why on-chip multiplexing increasingly replaces tristate buses as processes shrink and wire resistance grows.

A mux tree evaluated in code

The recursive construction is short and makes the relationship between expansion and multiplexing concrete. The function below builds a multiplexer tree from a truth table and evaluates it.

def build_mux_tree(table, variables):
    """Return a function of an assignment dict, implementing the truth table by Shannon expansion."""
    if not variables:
        return lambda env, value=table[()]: value
    var, rest = variables[0], variables[1:]
    # Split the table into the two cofactors on the first variable.
    low = {k[1:]: v for k, v in table.items() if k[0] == 0}
    high = {k[1:]: v for k, v in table.items() if k[0] == 1}
    f0 = build_mux_tree(low, rest)
    f1 = build_mux_tree(high, rest)

    def node(env):
        return f0(env) if env[var] == 0 else f1(env)   # the multiplexer select
    return node


from itertools import product

vars4 = ("a", "b", "c", "d")
table = {bits: int(sum(bits) % 2) for bits in product((0, 1), repeat=4)}  # parity
tree = build_mux_tree(table, vars4)
for bits in product((0, 1), repeat=4):
    env = dict(zip(vars4, bits))
    assert tree(env) == int(sum(bits) % 2)

The tree has 15 internal nodes for four variables, matching $2^n - 1$. Each node performs one Shannon expansion, and the select path from root to leaf is exactly the input assignment. The construction is correct for every function, including the parity function shown, which is notable because parity has no compact two-level form: its canonical sum of products needs $2^{n-1}$ terms for $n$ variables, and its minimized form is not smaller. Parity is cheap as a tree of exclusive-OR gates and expensive as a sum of products, which is the standard example of two-level cost diverging sharply from structural cost.

Selecting the right realization

Three structures implement the same function and differ in what they cost.

A gate network produced by two-level minimization has depth two and literal count proportional to the number of prime implicants selected. It is fast and shallow, and for functions with a compact cover it is the cheapest option.

A decoder-and-OR-plane structure has depth that grows logarithmically with the number of inputs and a cost proportional to $2^n$. It is regular, easy to lay out, and easy to test, which is why memory-like arrays use it even when the equivalent gate network would use fewer transistors.

A multiplexer or lookup table has depth proportional to the number of expanded variables, a regular structure, and a cost proportional to the number of leaves. It is the natural choice when inputs are few enough that the table fits, and it is what programmable fabric gives a designer by default.

The choice is not about which structure is better in the abstract. It is about which resource is scarce: gate count in a fixed library, depth against a clock period, or regularity against verification effort. A design partitioned around fixed lookup tables wants functions with few inputs; a design targeting a standard cell library wants functions with a compact cover; a memory-like block with many output bits wants a decoder.