Multiplexers and Decoders

A multiplexer (mux) is a combinational circuit with $N$ data inputs $D_0, \dots, D_{N-1}$, $\lceil \log_2 N \rceil$ select inputs $S$, and a single output $Y$. The select lines encode an index $k$ in binary, and the circuit behaves as $Y = D_k$. It is the hardware analogue of an array-indexing expression `Y = D[S]`. When $N$ is a power of two, exactly $\log_2 N$ select lines are needed and every select pattern is used; this is the common, "clean" case this article focuses on. A decoder is the structural inverse. It takes $n$ input lines encoding a binary number and produces $2^n$ output lines, exactly one of which is asserted (driven to 1) for each input combination — a one-hot output. A decoder with enable input adds one more control: when the enable is deasserted, all outputs are forced to 0 regardless of the code, allowing multiple decoders to be composed (as in the row/column decoders of a memory array) or turning the decoder into a true demultiplexer, which routes a single data input to one of $2^n$ outputs. Both circuits are two faces of the same underlying idea: a binary code names one of a finite set of choices. In a mux the "choice" selects which input reaches the output; in a decoder the "choice" selects which output gets activated. This is why a decoder followed by AND gates driven from a shared data line implements a demultiplexer, and a decoder feeding an OR gate over the true-input lines implements a multiplexer — the two circuits share a truth-table skeleton, only the direction of data flow differs.

Deriving the 2-to-1 mux. With one select bit $S$ and two data inputs $D_0, D_1$, the truth table is:

Reading off the behavior directly (rather than expanding a full 8-row truth table) gives the sum-of-products form:

This is the canonical 2-to-1 mux equation. It needs 2 AND gates, 1 OR gate, and 1 inverter — 4 gates total, and 2 levels of gate delay (AND then OR) after the inverter.

Building an N-to-1 mux from the general rule. For $N = 2^n$ inputs and $n$ select lines $S_{n-1}\ldots S_0$, define the minterm $m_k(S)$ as the AND of literals that is 1 exactly when the select lines encode integer $k$ (e.g., for $n=2$, $m_2(S) = \overline{S_1} S_0$… care with bit order, so let's fix $S_1S_0 = 10$ meaning $k=2$, giving $m_2 = S_1 \overline{S_0}$). Then:

Each minterm activates exactly one AND gate among $N$, gating through exactly one data input; the final OR gate merges these (only one is ever nonzero) into $Y$. This is a direct generalization of the 2-to-1 case and is provably correct because the minterms are mutually exclusive and exhaustive over $S$ — for any fixed select code, exactly one $m_k$ is 1 and all others are 0, so $Y$ collapses to exactly $D_k$.

Building a decoder. An $n$-to-$2^n$ decoder simply outputs the minterms directly instead of ANDing them with data:

Adding an enable $E$ multiplies every minterm by $E$: $\text{Out}_k = E \cdot m_k(S)$. When $E=0$ all outputs go to 0; when $E=1$ exactly one output fires, selected by $S$.

Building larger muxes/decoders from smaller ones. Large muxes are almost never built as one giant OR of $N$ AND gates in practice — instead they are built as trees of small (2-to-1) muxes, which keeps fan-in bounded and delay logarithmic. An 8-to-1 mux, for example, is built from seven 2-to-1 muxes in a 3-level binary tree: 4 muxes select pairs using the low select bit, 2 muxes combine those using the middle bit, and 1 final mux combines using the high bit. Similarly, large decoders can be built hierarchically: a large decoder is split into a coarse decoder (selecting a group) and a fine decoder within the group, with AND gates combining a coarse-select line and a fine-select line — this is exactly the row/column addressing scheme used inside memory arrays. ```pseudocode // N-to-1 MULTIPLEXER, N = 2^n, built as a balanced binary tree of 2:1 muxes function MUX_TREE(D[0..N-1], S[0..n-1]): level = D // start with the N data inputs for bit in 0 .. n-1: next_level = empty list for pair_index in 0 .. length(level)/2 - 1: d0 = level[2pair_index] d1 = level[2pair_index + 1] // 2:1 mux primitive: Y = (NOT S)d0 + Sd1 y = MUX2(d0, d1, S[bit]) next_level.append(y) level = next_level return level[0] // the single surviving wire is the output function MUX2(d0, d1, s): return (NOT s AND d0) OR (s AND d1)

// n-to-2^n DECODER with enable function DECODER(S[0..n-1], enable): outputs = array of size 2^n, all initialized to 0 if enable == 0: return outputs // all lines deasserted k = binary_value(S) // integer encoded by select lines outputs[k] = 1 return outputs

// DEMULTIPLEXER: route one data line to one of 2^n outputs function DEMUX(data_in, S[0..n-1]): sel = DECODER(S, enable = 1) outputs = array of size 2^n for i in 0 .. 2^n - 1: outputs[i] = data_in AND sel[i] return outputs ``` The pseudocode is faithful to real hardware: `MUX2` is literally the gate-level equation derived above, `MUX_TREE` is literally how wide multiplexers are laid out on silicon (a balanced binary tree, not a flat OR), and `DECODER`/`DEMUX` show the duality — a demultiplexer is a decoder whose one-hot outputs are ANDed with a shared data wire.

Gate count. A flat $N$-to-1 mux built directly from the sum-of-products form uses:

• $N$ AND gates, each with fan-in $n+1$ (the $n$ select literals plus the data input), where $n=\log_2 N$,
• 1 OR gate with fan-in $N$,
• $n$ inverters (to produce complemented select lines),

for a total of $\Theta(N)$ gates. If gates are restricted to bounded fan-in (e.g., 2-input gates only, as in real cell libraries), each $N$-input AND/OR must itself be built as a tree of 2-input gates, costing $O(N)$ additional gates and $O(\log N)$ additional depth — so the asymptotic gate count stays $\Theta(N)$, but constants grow.

Depth (delay). The flat design has depth $O(\log n) = O(\log\log N)$ for producing the fan-in-$(n{+}1)$ AND (if built from 2-input gates) plus $O(\log N)$ for the fan-in-$N$ OR — dominated by $O(\log N)$. The tree-of-2:1-muxes design (as in the pseudocode) is simpler to reason about: it has exactly $n = \log_2 N$ levels, each level being one 2:1 mux with constant depth (2 gates), giving depth $\Theta(\log N)$ and gate count $\Theta(N)$ as well, since level $i$ (counting from the data inputs) has $N/2^i$ muxes and $\sum_i N/2^i = N-1$ total 2:1 muxes, each a constant number of gates. Both designs are asymptotically equivalent; the tree form is preferred in real layouts for uniform fan-in and simpler routing.

Decoder cost. An $n$-to-$2^n$ decoder needs $2^n$ AND gates (one per output), each of fan-in $n+1$ (n select literals + enable), plus $n$ inverters — $\Theta(2^n)$ gates, $O(\log n)$ depth per AND gate if built from 2-input gates (constant depth if the AND is allowed fan-in $n+1$ directly). Since $N = 2^n$, this is $\Theta(N)$ gates for $N$ outputs, matching the mux's linear cost — expected, since they are dual circuits over the same $N$-element index space.

Correctness argument (mux). The correctness of $Y = \sum_k m_k(S)\cdot D_k$ follows from two facts about the minterms $m_k$: 1. Exhaustiveness: for every possible assignment of the select bits $S$, some $k^*$ makes $m_{k^*}(S) = 1$ (namely $k^*$ = the integer encoded by $S$), because $m_k$ is defined as the conjunction of literals matching the binary digits of $k$. 2. Mutual exclusivity: for $k \ne k^*$, $m_k(S) = 0$, because $m_k$ and $m_{k^*}$ differ in at least one literal, and that literal is set to disagree with $S$ for at least one term in the AND, forcing it to 0. Given these two facts, the sum $\sum_k m_k(S) D_k$ has exactly one nonzero term ($m_{k^*} D_{k^*} = 1 \cdot D_{k^*} = D_{k^*}$) and all other terms are 0, so the whole OR evaluates to $D_{k^*}$ — precisely the specified mux behavior $Y = D_{S}$. This is a direct instance of the general canonical sum-of-products theorem: any Boolean function equals the OR of the minterms for which it outputs 1, and here the function's value at minterm $k$ is defined to be $D_k$.

Correctness argument (decoder). Identical reasoning: $\text{Out}_k = m_k(S)$ is 1 exactly for the unique $S$ encoding $k$, by exhaustiveness and exclusivity of minterms, so the output vector is one-hot with the hot bit at position $k = \text{value}(S)$.

Correctness of the tree mux (induction on $n$). Base case $n=1$: `MUX2` implements $Y=\overline S D_0 + S D_1$ directly by definition — correct by inspection of its two rows. Inductive step: assume a tree of depth $n-1$ correctly selects among $2^{n-1}$ inputs using the low $n-1$ select bits. The final level combines two such $(n-1)$-trees (rooted at $D_{\text{low half}}[S_{low}]$ and $D_{\text{high half}}[S_{low}]$) using the top bit $S_{n-1}$ in one more `MUX2`. By the $n{=}1$ correctness of that final mux, the output equals whichever half's correctly-selected value the top bit points to — which is exactly $D_{\text{value}(S)}$. This completes the induction.

Tradeoffs. The flat sum-of-products mux minimizes logical depth at the cost of very wide gates (fan-in $N$), which in real CMOS is slow and area-hungry since wide gates need transistor stacking or extra buffering. The tree-of-2:1-muxes design uses only constant-fan-in gates uniformly, which is friendlier to standard-cell libraries, at the (mild) cost of a $\log N$-deep critical path instead of a theoretically flatter but practically slower wide-gate path. Real designs (e.g., a 32-to-1 mux in a register file read port) almost universally use the tree form, sometimes with pass-transistor-logic muxes instead of gate-logic muxes for further speed and area savings — a circuit-level optimization built on the same logical correctness argument above.

Consider a 4-to-1 mux used to pick one of four ALU result sources — say, register file, adder, shifter, memory-load — feeding the write-back stage of a simple pipeline, with $D_3 D_2 D_1 D_0 = 1,\,0,\,1,\,1$ (adder=1, shifter=1, others 0) and select $S_1 S_0 = 10$ (meaning "select index 2, the shifter").

Step 1 — minterms. With $n=2$, the four minterms are:

Step 2 — evaluate minterms at $S_1S_0 = 10$.

Exactly $m_2 = 1$, confirming exclusivity/exhaustiveness on this concrete input.

Step 3 — compute Y.

Wait — check the data assignment: we said $D_3D_2D_1D_0 = 1,0,1,1$, i.e. $D_0=1, D_1=1, D_2=0, D_3=1$. Selecting index 2 should return $D_2 = 0$. Indeed $Y=0$ — matching "shifter result happens to be logic 0 on this bit," which is a perfectly valid (if unglamorous) trace: the mux correctly forwarded $D_2$, not the more visually tempting $D_1$ or $D_3$, demonstrating the selection genuinely depends on $S$ and not on which input "looks like the answer."

Step 4 — trace through the tree implementation instead (sanity check). Using `MUX_TREE`:

• Level 0 (`bit=0`, using $S_0=0$): $M_0 = \text{MUX2}(D_0,D_1,S_0{=}0) = \overline{0}\cdot D_0 + 0\cdot D_1 = D_0 = 1$. $M_1 = \text{MUX2}(D_2,D_3,S_0{=}0) = D_2 = 0$.
• Level 1 (`bit=1`, using $S_1=1$): $M_2 = \text{MUX2}(M_0, M_1, S_1{=}1) = \overline{1}\cdot M_0 + 1\cdot M_1 = M_1 = 0$.

Output $Y = 0$, agreeing exactly with the sum-of-products computation — a second, structurally independent derivation confirming the answer, exactly as the induction proof guarantees.

Decoder companion example. Suppose this mux's select lines are themselves generated by a 2-to-4 decoder reading a 2-bit "source ID" field from an instruction, with enable tied to "write-back stage active." For source ID $=10_2$ and enable $=1$: $\text{OUT}_2 = 1\cdot S_1\overline{S_0} = 1\cdot1\cdot1=1$, all other outputs 0 — that one-hot line is precisely what would gate "shifter result valid" onto the write-back bus in a real datapath, tying the decoder and mux into one coherent control path.

The mux/decoder abstraction descends from the mathematics of Boolean algebra and the switching-circuit theory that translated logical propositions into physical relay and gate networks — the theoretical foundation that made "select one of N" and "activate exactly one of N" expressible as gate equations at all.

Multiplexers select data paths throughout a CPU datapath: choosing between the PC+4 and a branch target, selecting an ALU operand source, or picking which register-file read port feeds an execution unit — all directly foreshadow the selection logic detailed in Arithmetic Logic Units. Register files use decoders to translate a register-number field from an instruction into the one-hot write-enable signal for the correct storage cell, a mechanism developed further in Registers and Register Files. Memory chips (SRAM/DRAM) use row and column decoders — hierarchical decoders exactly like the ones described here — to activate a single word line out of millions, while a wide output mux (or sense-amp selection network) picks the correct bit line data to drive onto the data bus. Instruction decoders in a CPU's control unit are literally decoders in this technical sense: an opcode field becomes a one-hot signal enabling a specific control path. Bus arbitration and I/O address decoding on a system bus use decoders to ensure exactly one peripheral responds to a given address range. Multiplexed displays, time-division multiplexing in networking, and even simple debouncing/selection circuits in embedded systems reuse the identical logical construction.

Ask the tutor: How would you design a 16-to-1 multiplexer using only 2-to-1 mux building blocks, and what is its exact gate delay in levels?