# The multiplexer as a universal logic element

*Any function, read straight out of a mux*

A multiplexer is a universal logic element: a 2^n-to-1 mux with the n input variables on its select lines implements any n-variable boolean function, because wiring each data input to that function's truth-table output makes the mux a direct truth-table lookup.

Group: Gates
URL: https://digiwleea.wleeaf.dev/learn/mux-universal/

A [multiplexer](https://digiwleea.wleeaf.dev/learn/mux/) is a data selector: its select lines choose which data input passes through to the output. So far you have used it to *route* signals, to decide which value reaches a bus. But a mux can do something more surprising: it can **compute any logic function at all**. Feed the function's input variables into the select lines and tie each data input to a fixed value, and the mux reads its answer straight out of a [truth table](https://digiwleea.wleeaf.dev/learn/truth-tables/). That makes the multiplexer, like the [universal NAND gate](https://digiwleea.wleeaf.dev/learn/nand/), a building block that can realize *any* logic.

## A mux is a truth-table lookup

Take a `2^n`-to-1 mux: it has `n` select lines and `2^n` data inputs `D0, D1, ..., D(2^n - 1)`. When the select lines hold the binary value `i`, the mux connects data input `Di` to the output. Now point the `n` select lines at the `n` variables of a function `f`. The select value `i` is exactly the truth-table **row number** for that input combination, and the mux passes whatever sits on `Di`. So if you set each `Di` to the value `f` should produce in row `i`, the output is `f` for **every** input combination. The mux is the truth table, made of wires: the select lines are the address, the data inputs are the pre-filled answers, one per row.

> **TIP:** Picture a **jukebox**. You punch in a code (the select value) and it plays the track stored in that slot (the data input). A mux used as logic is a jukebox whose slots you pre-load with `0`s and `1`s straight from the truth table's output column. The select code looks up the row; the slot hands back the pre-written answer. Nothing is computed on the fly, it is all looked up.

Here is the brute-force recipe on a 3-variable function, **odd parity** `F = A XOR B XOR C` (the sum bit of a [full adder](https://digiwleea.wleeaf.dev/learn/fulladder/)). Put `A, B, C` on the three select lines of an 8-to-1 mux, then tie each data input to that row's output:

| A | B | C | F |
| --- | --- | --- | --- |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |

_Odd parity (F = A XOR B XOR C), 1 when an odd number of inputs are 1. Wire A,B,C to the 8-to-1 mux select lines, then set D0..D7 to this F column: D0=0, D1=1, D2=1, D3=0, D4=1, D5=0, D6=0, D7=1. The mux now outputs odd parity, no gates designed at all._

> **KEY:** This is why a multiplexer is called **universal**: with `n` variables on the select lines you can build *any* of the `2^(2^n)` functions of `n` variables, just by choosing the `2^n` data values. You never reason about gates or minterms, you copy the truth table's output column onto the data inputs. The cost is one big mux that grows as `2^n`, which is the next thing to fix.

## Shannon expansion: the same function on a smaller mux

An 8-to-1 mux for three variables is wasteful. **Shannon expansion** lets you halve it. The theorem splits any function on one chosen variable `x`:

```
f(x, ...) = x' · f(0, ...) + x · f(1, ...)
```

The two pieces `f(0, ...)` and `f(1, ...)` are the **cofactors**: the function with `x` forced to `0` and to `1`. That `x'·(...) + x·(...)` shape is exactly a 2-to-1 mux selected by `x`. Generalize it: put `n-1` of the variables on the select lines of a `2^(n-1)`-to-1 mux, and on each data input put the **residue**, the function with those `n-1` variables fixed. With only one variable left free, every residue is one of just four things: `0`, `1`, the last variable, or its complement. So you need no extra gates beyond at most one inverter.

## Worked example: a 3-variable function on a 4-to-1 mux

Take the **majority** function `F = A·B + B·C + A·C` (the carry-out of a [full adder](https://digiwleea.wleeaf.dev/learn/fulladder/), `1` when at least two inputs are `1`). Choose `A` (the most significant select line) and `B` as the two select inputs of a 4-to-1 mux, leaving `C` as the free residue variable. For each combination of `A,B`, simplify `F` to a function of `C` alone:

1. `A=0, B=0` (select `D0`): `F = 0 + 0·C + 0 = 0`, so wire `D0` to `0`.
2. `A=0, B=1` (select `D1`): `F = 0 + 1·C + 0 = C`, so wire `D1` to `C`.
3. `A=1, B=0` (select `D2`): `F = 0 + 0·C + 1·C = C`, so wire `D2` to `C`.
4. `A=1, B=1` (select `D3`): `F = 1 + C + C = 1`, so wire `D3` to `1`.

| A (S1) | B (S0) | Data input | Residue (function of C) |
| --- | --- | --- | --- |
| 0 | 0 | D0 | 0 |
| 0 | 1 | D1 | C |
| 1 | 0 | D2 | C |
| 1 | 1 | D3 | 1 |

_Majority of three on a 4-to-1 mux: select lines A,B, data inputs D0=0, D1=C, D2=C, D3=1. The 8-input lookup collapsed to a 4-input mux plus two wires tied to C. The residues fell out to 0, C, C, 1._

## The shortcut: read residues off the truth table in pairs

You do not have to simplify the algebra by hand. Write the full `2^n`-row truth table with the **residue variable as the last (least-significant) column**, so the rows fall into `2^(n-1)` consecutive pairs. Inside each pair the `n-1` select variables hold still while the residue steps `0` then `1`, and that pair is exactly the two rows one data input serves. Read each pair by comparing its two outputs to the residue variable's own `0, 1` pattern:

- `0, 0`: both outputs are `0`, so that data input is a constant `0`.
- `1, 1`: both outputs are `1`, so that data input is a constant `1`.
- `0, 1`: the outputs rise with the residue variable, matching its `0, 1` pattern, so that data input is the residue variable itself.
- `1, 0`: the outputs are the residue variable inverted, so that data input is its complement, which costs one inverter.

Run it on the same **odd parity** `F = A XOR B XOR C` you put on the 8-to-1 mux at the top of this lesson. Keep `A,B` on the select lines and let `C` be the residue, then pair the eight rows into four (each pair shares an `A,B` value while `C` goes `0` then `1`):

| A (S1) | B (S0) | F at C=0 | F at C=1 | Data input |
| --- | --- | --- | --- | --- |
| 0 | 0 | 0 | 1 | C |
| 0 | 1 | 1 | 0 | C' |
| 1 | 0 | 1 | 0 | C' |
| 1 | 1 | 0 | 1 | C |

_Odd parity on a 4-to-1 mux, read straight off the paired rows: select A,B, residue C, data inputs D0=C, D1=C', D2=C', D3=C. Compare the brute-force 8-to-1 version's eight fixed data bits (0,1,1,0,1,0,0,1): each adjacent pair 0,1 / 1,0 / 1,0 / 0,1 collapsed into one residue C / C' / C' / C._

The 8-to-1 mux needed eight hard-wired data bits; the 4-to-1 mux needs just `C`, one inverter to make `C'`, and four short wires. Half the mux, and the residues carry the extra variable. That is the reduced-mux move in general: with `n-1` variables on the select lines, every data input is one of only four things (`0`, `1`, the free variable, or its complement), read directly from the paired rows, so any `n`-variable function fits a `2^(n-1)`-to-1 mux plus at most one inverter. Between the majority example (residues `0, C, C, 1`) and this parity one (residues `C, C', C', C`) you have now seen all four residue kinds a data input can take.

> **WARN:** **Common mistakes.** Keep the select-line order straight: decide which variable is the most significant select bit and number the data inputs by that same binary value, or the wrong residue lands on the wrong input. Remember the residue can be a **literal** (`C` or `C'`), not only a constant `0` or `1`, so you may still need one inverter. For the smaller-mux trick you must leave exactly one variable **off** the select lines to be the residue, do not put all `n` on select. And a mux output is purely combinational: it looks up, it does not remember, so this builds logic functions, not storage.

## The dual approach: a decoder plus an OR

There is a mirror-image way to turn a truth table into hardware. A [decoder](https://digiwleea.wleeaf.dev/learn/decoder/) takes the `n` variables and raises exactly one of its `2^n` outputs, the one whose number matches the input, which is precisely the **minterm** of that row from [canonical forms](https://digiwleea.wleeaf.dev/learn/canonical-forms/). OR together the decoder outputs for the rows where `f = 1` and you have built the canonical [sum of products](https://digiwleea.wleeaf.dev/learn/canonical-forms/) directly: the decoder generates every minterm, the OR selects the on-set. The mux and the decoder-plus-OR are two readings of the same idea, the truth table cast into silicon: the mux *selects* the stored answer, while the decoder *generates* the minterms and the OR sums the ones you want.

The selector at the heart of all this is the humble 2-to-1 mux below, built from one inverter, two [AND](https://digiwleea.wleeaf.dev/learn/and/) gates, and an [OR](https://digiwleea.wleeaf.dev/learn/or/). It passes `D0` when `SEL = 0` and `D1` when `SEL = 1`. Open it in the lab: tie `D0` and `D1` to fixed values or to a variable and watch it become a one-variable lookup, the Shannon building block.

_Circuit diagram: A 2-to-1 multiplexer from gates: Y = (D0 AND NOT SEL) OR (D1 AND SEL). SEL = 0 passes D0, SEL = 1 passes D1. This is the unit Shannon expansion stacks: feed cofactors into D0 and D1 and the select line splits the function on one variable._

> **KEY:** This is not a classroom curiosity, it is how an **FPGA** computes. The logic cell of every FPGA is a **lookup table (LUT)**, and a LUT is literally a multiplexer whose data inputs are tiny memory cells you program. A 6-input LUT is a 64-to-1 mux; loading its 64 memory bits with a truth table's output column makes the cell behave as any 6-variable function. The universal-mux idea you just saw is the working principle of reconfigurable hardware.

**Q (Try it):** Implement 2-input XOR (`F = A XOR B`, `1` when the inputs differ) two ways. First on a 4-to-1 mux with `A,B` on the select lines: what are `D0..D3`? Then on a 2-to-1 mux using Shannon expansion on `A`: what residue goes on each of its two data inputs?

**A:** XOR's truth table is `00->0, 01->1, 10->1, 11->0`. On a **4-to-1 mux** (select `A,B`) you tie the data inputs to that output column: `D0=0, D1=1, D2=1, D3=0`. On a **2-to-1 mux** split on `A`: when `A=0`, `F = B` (the residue is `B`), and when `A=1`, `F = B'` (the residue is `B'`). So `D0 = B` and `D1 = B'`, selected by `A`, with one inverter for `B'`. The smaller mux trades half its data inputs for a single literal.

### FAQ

**Q:** Why is a multiplexer a universal logic element?

**A:** Because a `2^n`-to-1 mux with the `n` function variables on its select lines passes data input `Di` whenever the inputs spell row `i` of the truth table. Set each `Di` to that row's desired output and the mux reproduces any `n`-variable function. With `n` select lines it can realize all `2^(2^n)` functions of `n` variables just by choosing the data values.

**Q:** How do you implement a logic function with a multiplexer?

**A:** Write the function's truth table, put its input variables on the mux select lines, and wire each data input to the output value of the matching truth-table row. A `2^n`-to-1 mux handles any `n`-variable function directly. To use a smaller `2^(n-1)`-to-1 mux, apply Shannon expansion: leave one variable off the select lines and put the residue (`0`, `1`, that variable, or its complement) on each data input.

**Q:** What is Shannon expansion?

**A:** Shannon expansion splits a function on one variable: `f = x'·f(0) + x·f(1)`, where `f(0)` and `f(1)` are the cofactors (the function with `x` forced to `0` and `1`). That `x'·(...) + x·(...)` form is exactly a 2-to-1 mux selected by `x`, so the theorem lets a `2^(n-1)`-to-1 mux implement an `n`-variable function by handling one variable as a residue on the data inputs.

**Q:** How does an FPGA lookup table relate to a multiplexer?

**A:** An FPGA lookup table (LUT) is a multiplexer whose data inputs are programmable memory cells. A `k`-input LUT is a `2^k`-to-1 mux driven by the `k` logic inputs; programming its `2^k` memory bits with a truth table's output column makes the cell compute any `k`-variable function. The universal-mux principle is literally how reconfigurable logic works.

A mux hands you *a* circuit for any function, but rarely the *smallest* one, and the same is true of the canonical forms it mirrors. The next step is to make those expressions small: [Karnaugh maps](https://digiwleea.wleeaf.dev/learn/karnaugh/) group a truth table's `1`s by eye to find the minimal AND-OR circuit, the cheap version of what the mux brute-forces.