3.3Multiplexers as function generators
The idea
A multiplexer picks one of several inputs using select lines. Because it can output each data input for a particular select value, it can implement any function: this is the MUX as a function generator.
Think of it like this: A railway switch: the select lines decide which track is connected to the output.
Why it exists
GATE often says "implement this function with a 4:1 MUX, find the inputs I0 to I3".
How it works
- Choose n − 1 variables for the selects of a 2ⁿ⁻¹:1 MUX (for an n-variable function).
- For each select value look at the two truth-table rows that differ in the last variable.
- Both 0 → data input 0; both 1 → 1; (0, 1) → X; (1, 0) → X′ where X is the last variable.
- Count the extra inverter if some input is X′.
Worked example: F = Σm(1,2,6,7), selects A and B
AB = 00 has (F = 0, 1) so I0 = C; AB = 01 has (1, 0) so I1 = C′; AB = 10 has (0, 0) so I2 = 0; AB = 11 has (1, 1) so I3 = 1.
Now play with it
- →Click the minterms 3, 4, 6, 7 and read the new data inputs.
- →Switch to 2 or 4 variables to see the same rule.
Click the minterms where F = 1. The first 2 variable(s) drive the select lines of a 4:1 MUX; the last variable (C) feeds the data inputs.
| select AB | F when C=0 | F when C=1 | data input I |
|---|---|---|---|
| 00 | 0 | 1 | I0 = C |
| 01 | 1 | 0 | I1 = C' |
| 10 | 0 | 0 | I2 = 0 |
| 11 | 1 | 1 | I3 = 1 |
Rule: for each select combination look at the pair F(…,0), F(…,1). Both 0 → tie the input to 0; both 1 → tie it to 1; (0,1) → use C; (1,0) → use C'. A 2ⁿ:1 MUX can therefore implement any (n + 1)-variable function with no extra gates other than an inverter.
| Build | Needs |
|---|---|
| 4:1 MUX from 2:1 MUXes | 3 |
| 8:1 MUX from 2:1 MUXes | 7 |
| 8:1 MUX from 4:1 MUXes | 2 × 4:1 + 1 × 2:1 = 3 |
| 16:1 MUX from 4:1 MUXes | 5 |
| Any 3-variable function | 4:1 MUX + at most 1 inverter |
| Any 4-variable function | 8:1 MUX + at most 1 inverter |
Check yourself
A 4:1 MUX with selects A (MSB), B and data inputs I0 = 0, I1 = C, I2 = C′, I3 = 1 implements
Exam notes (the dense version)
A 2ⁿ:1 MUX has n select lines and implements F = Σ mᵢ·Iᵢ. To implement an (n + 1)-variable function with a 2ⁿ:1 MUX, connect n variables to the selects and set each data input to 0, 1, the last variable X or X′ (look at the pair of rows). A 4:1 MUX can be built from three 2:1 MUXes (2 + 1); a 2ⁿ:1 MUX needs 2ⁿ − 1 MUXes of 2:1. A MUX is also a universal element: with constants and inverters any function can be made. Tri-state buses are an alternative to MUXes.
Previous year questions: Combinational Circuits (10)
PYQs are grouped by topic, so this is the full set for Combinational Circuits; try the ones that match this subtopic. Open all 10 on the topic page.