Multiplexers, Decoders and Encoders

Multiplexers (MUX), decoders and encoders are standard MSI combinational blocks. A MUX selects one of many data inputs using select lines. A decoder activates exactly one of $2^n$ outputs from an $n$-bit code, so its outputs are the minterms of its inputs. An encoder (often a priority encoder) compresses one-hot or sparse inputs into a binary index.

GATE asks you to realize a Boolean function with a MUX (and find the data inputs), evaluate a cascade of MUXes, count the blocks in a MUX tree or decoder tree, realize several functions with one decoder plus OR gates, and write priority-encoder equations.

A $2^n\!:\!1$ MUX has $2^n$ data inputs $I_0..I_{2^n-1}$, $n$ select lines $S$, and one output $Y=I_S$, where the select lines are read as a binary number. Enable (active low or high) may force $Y=0$ when disabled.

Boolean form. $Y=\sum_k I_k\, m_k(S)$ where $m_k(S)$ is the minterm of the select lines. A 2:1 MUX is $Y = S'I_0 + SI_1$; a 4:1 MUX is

At gate level, a $2^n\!:\!1$ MUX is $2^n$ AND gates of $n+1$ inputs feeding one $2^n$-input OR, plus $n$ inverters for the selects.

Select order matters. $S_1$ is the more significant select. Swapping the wires on $S_1$ and $S_0$ permutes $I_1$ and $I_2$.

Shannon-expand $f$ on the variables used as selects:

where $f_k$ is the cofactor (residual function) when the selects equal $k$. Tie each data input to its cofactor.

Universality. A 2:1 MUX with constants 0 and 1 available is functionally complete: $x' = \mathrm{MUX}(S = x; I_0 = 1, I_1 = 0)$, $xy = \mathrm{MUX}(S = x; I_0 = 0, I_1 = y)$ and $x + y = \mathrm{MUX}(S = x; I_0 = y, I_1 = 1)$.

An $n\!\to\!2^n$ line decoder asserts output $O_i$ iff the input equals $i$ (and enable is on). Outputs are exactly the minterms of the inputs, so it uses $2^n$ AND gates of $n$ inputs ($n + 1$ with an enable). Any function of the same inputs is the OR of the outputs in its on-set, and one decoder serves several functions at once.

Active-low outputs. Many decoders (for example the 74x138 style) have active-low outputs $\overline{O_i} = M_i$, the maxterms. Then $f = \sum m(\ldots)$ is a NAND of the selected lines, and an AND of the lines for the off-set gives $f$ as a product of maxterms.

Decoder trees. Larger decoders come from enables. Two 2-to-4 decoders with enables $a_2'$ and $a_2$ give a 3-to-8 decoder (Figure 2). A 4-to-16 decoder takes five 2-to-4 decoders: one decodes $a_3a_2$ and its four outputs enable four decoders of $a_1a_0$.

A $2^n\!\to\!n$ encoder assumes exactly one input is 1 and outputs its index. For 8-to-3:

Each output ORs the inputs whose index has that bit set. With two inputs active the output is the bitwise OR of the two indices ($D_3$ and $D_5$ give $111$, which is neither), and "no input" gives $000$, the same as $D_0$.

A priority encoder accepts several 1s and outputs the index of the highest-priority 1, plus a valid flag $V$ that distinguishes "$D_0$ only" from "nothing active".

Routes one data input $D$ to the selected output line: $O_i = D\cdot m_i(S)$. A decoder with enable is a demultiplexer: drive the enable with $D$ and the inputs with the selects.

Each data path is AND with its select minterm; OR all paths. Transmission-gate MUXes appear in VLSI; GATE sticks to the logic model.

A $2^n\!:\!1$ MUX from 2:1 MUXes is a binary tree: $2^{n-1}$ at the first level (selected by $S_0$), then $2^{n-2}$ (by $S_1$), and so on, for $2^n - 1$ MUXes and $n$ levels. From 4:1 MUXes, a 16:1 MUX takes four on the first level (selected by $S_1S_0$) and one on the second (by $S_3S_2$): five in all. The lower select bits go to the first level; feeding them to the wrong level permutes the data inputs.

Simulate one MUX at a time: write each output as $S'I_0 + SI_1$ with the actual signals, or build the truth table row by row. A MUX whose select is driven by another MUX output still obeys $Y = I_S$ for each row.

Arrays are 0-indexed; <- is assignment.

MUX-DATA-INPUTS reads the truth table once, $\Theta(2^n)$ work. Rows $2k$ and $2k + 1$ differ only in the last variable because that variable is the least significant bit of the row index.

Software cost model. Use unpacked word arrays, unit-cost indexed lookup/write, and words wide enough for the loop bounds and packed indices. Assume $S$ and $x$ already hold packed indices: MUX-EVAL takes $\Theta(1)$ time and $O(1)$ workspace in every case, excluding its input array and scalar output. Reading $S$ from an unpacked $n$-bit array instead adds $\Theta(n+1)$ conversion work. DECODER writes all $2^n$ entries even when disabled: $\Theta(2^n)$ time and output words in best, average and worst cases, with $O(1)$ workspace beyond input/output. For $n\ge1$, constant-time truth-table access makes MUX-DATA-INPUTS read exactly $2^n$ rows and write $2^{n-1}$ fixed-size descriptors (0, 1, $x$, or NOT $x$); time is $\Theta(2^n)$ in every case and working space $O(1)$ beyond input/output. For $m\ge1$, PRIORITY-ENCODE has $\Theta(1)$ best time and $\Theta(m)$ worst time, with $O(1)$ workspace excluding its input and two-word result. Average time needs a distribution: with exactly one 1 uniformly located it examines $(m+1)/2$ entries on average, hence $\Theta(m)$. These sequential software costs are not circuit gate counts or propagation delays.

A decoder computes the standard basis of indicator functions on $\{0,1\}^n$. Any function is the OR (sum) of those indicators where the table is 1: decoder plus OR. A MUX with selects on all variables and data in $\{0,1\}$ is a ROM-like realization of one output column.

Shannon expansion. For any variable $x$,

which is exactly a 2:1 MUX with select $x$. Applying it to $k$ variables at once gives the $2^k\!:\!1$ MUX form. A function with $n$ variables has $2^{2^n}$ possibilities; a $2^{n-1}\!:\!1$ MUX with data from $\{0, 1, x, x'\}$ has $4^{2^{n-1}} = 2^{2^n}$ settings, one per function, which is another way to see that every function fits.

Priority-encoder equations (4 to 2, $D_3$ highest). $Y_1 = 1$ when the winner is $D_3$ or $D_2$: $Y_1 = D_3 + D_2$. $Y_0 = 1$ when the winner is $D_3$, or $D_1$ with $D_2$ and $D_3$ off: $Y_0 = D_3 + D_3'D_2'D_1$, which simplifies to $Y_0 = D_3 + D_2'D_1$. And $V = D_3 + D_2 + D_1 + D_0$.

Selects $a,b$; $I=(0,1,1,0)$. Output equals $a\oplus b$, the truth-table column of XOR.

OR outputs $O_1,O_2,O_4,O_7$. This $f$ is $a \oplus b \oplus c$, the full-adder sum; the same decoder gives the carry $\sum m(3,5,6,7)$ with a second OR. A full adder is one 3-to-8 decoder plus two 4-input OR gates. With active-low outputs, use two 4-input NAND gates.

Inputs $w_3..w_0$ with $w_3$ highest priority. If $w_3=1$, out $11$; else if $w_2=1$, out $10$; else if $w_1=1$, out $01$; else if $w_0=1$, out $00$; valid $= w_3+w_2+w_1+w_0$. For input $0110$ ($w_2 = w_1 = 1$) the output is $10$ with $V = 1$; a plain encoder would give $10 + 01 = 11$.

High bit $a_2$ enables one of two 2-to-4 blocks that receive $a_1 a_0$: $a_2 = 0$ enables the block for $O_0..O_3$, $a_2 = 1$ the block for $O_4..O_7$. For input $110$, only the lower (O4-O7) block is enabled and its line $10$ fires: $O_6$.

$f=\sum m(1,4,5,7)$ for $abc$, selects $a,b$. Residuals: $ab=00$ (rows 0,1) $\to c$; $ab=01$ (rows 2,3) $\to 0$; $ab=10$ (rows 4,5) $\to 1$; $ab=11$ (rows 6,7) $\to c$. Data ties $I=(c,0,1,c)$.

$f(A,B,C,D)=\sum m(0,1,3,4,8,9,15)$ with selects $A,B,C$ and data in terms of $D$. Pair rows $2k, 2k+1$:

So $I = (1, D, D', 0, 1, 0, 0, D)$.

$m_1 = \mathrm{MUX}(S = a; I_0 = b, I_1 = b')$ and $f = \mathrm{MUX}(S = c; I_0 = m_1, I_1 = a')$. Then $m_1 = a'b + ab' = a \oplus b$ and $f = c'(a \oplus b) + c\,a'$. Rows $abc$ with $c = 0$ give the on-set where $a \ne b$: 2 (010) and 4 (100). Rows with $c = 1$ give the on-set where $a = 0$: 1 (001) and 3 (011). So $f = \sum m(1,2,3,4)$.

With only $a$, $b$, 0 and 1 available (no inverters), a single 2:1 MUX reaches exactly 12 of the 16 two-variable functions: $0$, $1$, $a$, $b$, $a'$, $b'$, $ab$, $ab'$, $a'b$, $a+b$, $a+b'$ and $a'+b$. The four it misses are XOR, XNOR, NAND and NOR. Two suffice: $t = \mathrm{MUX}(S = b; 1, 0) = b'$, then $a \oplus b = \mathrm{MUX}(S = a; b, t)$.

Common misconceptions.