Think of the input selector on a TV: several sources (HDMI 1, HDMI 2, antenna) are connected, but only one of them reaches the screen, and a button decides which. A multiplexer is exactly that switch, built from logic gates. It is one of the most used blocks in digital design: it chooses operands in a processor's datapath, sends several signals over one wire, and, as we will see, it can implement any Boolean function by itself.
A multiplexer (MUX, or data selector) is a combinational circuit with 2n data inputs, n select inputs and one output. The binary value on the select inputs decides which data input is connected to the output.
A MUX with N data inputs is called an N-to-1 (or N × 1) MUX and needs log2N select lines: 2-to-1 needs 1, 4-to-1 needs 2, 8-to-1 needs 3, 16-to-1 needs 4.
+---------+
I0 ---->| |
I1 ---->| 4-to-1 |
I2 ---->| MUX |----> Y
I3 ---->| |
+---------+
^ ^
S1 S0 (S1 S0 = 10 connects I2 to Y)
2-to-1 Multiplexer
S | Y |
|---|---|
0 | I0 |
1 | I1 |
Y = S′·I0 + S·I1
This compact table hides a full truth table with 3 inputs (S, I0, I1) and 8 rows; the compact form simply says "Y copies the selected input". The circuit is two AND gates, one OR gate and an inverter:
S ──┬──[NOT]── S′ ──┐
│ [AND]── S′·I0 ──┐
│ I0 ─────────┘ ├──[OR]── Y
└───────────────┐ │
[AND]── S·I1 ───┘
I1 ─────────┘
The AND gates act as gates in the everyday sense: S′ opens the top one, S opens the bottom one, and exactly one is open at any time.
4-to-1 and 8-to-1 Multiplexers
4-to-1 MUX
S1 | S0 | Y |
|---|---|---|
0 | 0 | I0 |
0 | 1 | I1 |
1 | 0 | I2 |
1 | 1 | I3 |
Y = S1′S0′·I0 + S1′S0·I1 + S1S0′·I2 + S1S0·I3
The General Pattern
For a 2n-to-1 MUX: Y = Σ mk · Ik (k = 0 to 2n − 1), where mk is the k-th minterm of the select variables.
For the 8-to-1 MUX with selects S2 S1 S0:
Y = S2′S1′S0′·I0 + S2′S1′S0·I1 + S2′S1S0′·I2 + S2′S1S0·I3
+ S2S1′S0′·I4 + S2S1′S0·I5 + S2S1S0′·I6 + S2S1S0·I7
Gate-level cost: 3 inverters, 8 four-input AND gates, one 8-input OR gate.
Hold on to this formula: the whole "implement a function with a MUX" technique below follows directly from it.
Enable Input
Most MUX chips have an enable (strobe) input E. When E is inactive, the output is forced to 0 regardless of the selects; when active, the MUX works normally. Mathematically, every AND term gets an extra E:
Y = E · (S1′S0′·I0 + S1′S0·I1 + S1S0′·I2 + S1S0·I3)
On real chips the enable is usually active-low (written with a bar or a prime, for example E′ or G′), meaning the MUX works when that pin is 0. The enable is what lets you combine small MUXes into larger ones.
Standard MUX ICs
Chip (74HC / 74LS series) | Contents | Notes |
|---|---|---|
74x151 | One 8-to-1 MUX | 3 selects, active-low enable, both Y and Y′ outputs |
74x153 | Two 4-to-1 MUXes | Common select lines, a separate active-low enable for each half |
74x157 | Four 2-to-1 MUXes | Common select and active-low enable: selects one of two 4-bit words |
Building Larger Multiplexers from Smaller Ones
Method 1: A MUX Tree
An 8-to-1 MUX from 2-to-1 MUXes: the first level picks within pairs using S0, the second level using S1, the last using S2.
I0 ─┐
[2:1]─┐
I1 ─┘ S0 │
[2:1]─┐
I2 ─┐ │ S1 │
[2:1]─┘ │
I3 ─┘ S0 │
[2:1]──── Y
I4 ─┐ │ S2
[2:1]─┐ │
I5 ─┘ S0 │ │
[2:1]─┘
I6 ─┐ │ S1
[2:1]─┘
I7 ─┘ S0
Level 1: 4 MUXes (S0) Level 2: 2 MUXes (S1) Level 3: 1 MUX (S2) Total 7
Notice the order: the least significant select bit goes to the first level. Check with S2S1S0 = 101: level 1 picks I1, I3, I5, I7; level 2 (S1 = 0) picks I1 and I5; level 3 (S2 = 1) picks I5. Correct.
Counting rule: an N-to-1 MUX from 2-to-1 MUXes needs N/2 + N/4 + ... + 1 = N − 1 MUXes. From k-to-1 MUXes, count level by level, rounding up at each level; when N is a power of k this equals (N − 1)/(k − 1).
Build | Levels | Total |
|---|---|---|
8-to-1 from 2-to-1 | 4 + 2 + 1 | 7 |
16-to-1 from 4-to-1 | 4 + 1 | 5 |
64-to-1 from 4-to-1 | 16 + 4 + 1 | 21 |
32-to-1 from 4-to-1 | 8 + 2 + 1 (the last one used as a 2-to-1) | 11 |
32-to-1 from 8-to-1 | 4 + 1 (a 4-to-1 job, done by an 8-to-1) | 5 |
The delay of a tree is (number of levels) × (delay of one MUX). An N-to-1 tree of 2-to-1 MUXes has log2N levels.
Method 2: Using the Enable Inputs
A 16-to-1 MUX from two 8-to-1 MUXes with enables: give both the same S2 S1 S0, enable the first when S3 = 0 and the second when S3 = 1, and OR their outputs. Since the disabled MUX outputs 0, the OR gate passes the selected one.
MUX A: I0..I7, enabled by S3′ ┐
MUX B: I8..I15, enabled by S3 ├──[OR]── Y
┘
Implementing Boolean Functions with a Multiplexer
Compare the MUX equation Y = Σ mk · Ik with the canonical SOP form from Canonical Forms: SOP & POS, F = Σ mk · F(k). They have the same shape. So:
Method 1: n Variables on a 2n-to-1 MUX
Connect the n variables to the select lines and put the truth-table column on the data inputs: Ik = 1 if mk is a minterm of F, else 0. Easy, but wasteful.
Method 2: n Variables on a 2n−1-to-1 MUX
Use n − 1 variables as selects. For each select combination, two rows of the truth table remain (the leftover variable = 0 and = 1), and F restricted to those rows can only be one of four things:
F when leftover variable X = 0 | F when X = 1 | Data input |
|---|---|---|
0 | 0 | 0 |
1 | 1 | 1 |
0 | 1 | X |
1 | 0 | X′ |
This is Shannon's expansion in action: F = X′·F(X = 0) + X·F(X = 1), applied to every select combination at once.
Worked Example 1: Full Adder Sum with a 4-to-1 MUX
F(A, B, C) = Σm(1, 2, 4, 7), which is A ⊕ B ⊕ C. Use A, B as selects (S1 = A, S0 = B) and C as the data variable:
AB rows F (C=0, C=1) data input
00 m0, m1 0, 1 I0 = C
01 m2, m3 1, 0 I1 = C′
10 m4, m5 1, 0 I2 = C′
11 m6, m7 0, 1 I3 = C
One 4-to-1 MUX and an inverter give the 3-input XOR. Sanity check: A = 1, B = 0, C = 0 selects I2 = C′ = 1, and 1 ⊕ 0 ⊕ 0 = 1. Correct.
Worked Example 2: A 4-variable Function with an 8-to-1 MUX
Implement F(A, B, C, D) = Σm(1, 3, 4, 11, 12, 13, 14, 15). We do it twice, to show that the choice of data variable matters.
(a) Selects A, B, C; data variable D (the LSB). Each select value k covers minterms 2k and 2k + 1:
ABC minterms (D=0, D=1) F values data input
000 0, 1 0, 1 I0 = D
001 2, 3 0, 1 I1 = D
010 4, 5 1, 0 I2 = D′
011 6, 7 0, 0 I3 = 0
100 8, 9 0, 0 I4 = 0
101 10, 11 0, 1 I5 = D
110 12, 13 1, 1 I6 = 1
111 14, 15 1, 1 I7 = 1
(b) Selects B, C, D; data variable A (the MSB). Now select value k covers minterms k (A = 0) and k + 8 (A = 1). This is the "implementation table" method from Morris Mano's textbook: write the minterms in two rows, A′ (0 to 7) and A (8 to 15), circle the ones in F, and read each column:
I0 I1 I2 I3 I4 I5 I6 I7
A′ 0 (1) 2 (3) (4) 5 6 7
A 8 9 10 (11) (12) (13) (14) (15)
--- --- --- --- --- --- --- ---
0 A′ 0 1 1 A A A
Rule per column: none circled → 0; both → 1; only A′ row → A′; only A row → A
Both answers are correct; they are just different wirings. Exam questions specify which variables go to the select lines, so read carefully. The simulation below checks version (a).
Worked Example 3: Analysing a MUX Circuit
A favourite GATE pattern is the reverse: given MUXes wired together, find the function. Two 2-to-1 MUXes are connected as follows: MUX1 has select B, I0 = C, I1 = C′; its output X feeds I0 of MUX2, which has select A and I1 = B.
MUX1: X = B′·C + B·C′ = B ⊕ C
MUX2: Y = A′·X + A·B = A′(B ⊕ C) + AB
Truth table → Y = Σm(1, 2, 6, 7)
Minimal SOP: Y = AB + BC′ + A′B′C
The method is always the same: write each MUX's output with Y = S′·I0 + S·I1 (or the 4-to-1 formula), substitute, and simplify or tabulate.
The MUX Is a Universal Logic Element
With constant 0 and 1 available, a single 2-to-1 MUX (Y = S′I0 + SI1) gives every basic gate:
Gate | S | I0 | I1 | Check |
|---|---|---|---|---|
NOT A | A | 1 | 0 | A′·1 + A·0 = A′ |
A AND B | A | 0 | B | A′·0 + A·B = AB |
A OR B | A | B | 1 | A′B + A = A + B |
A XOR B | A | B | B′ | A′B + AB′ (needs B′: one more MUX as NOT) |
Since {NOT, AND, OR} is functionally complete, so is the 2-to-1 MUX. This is not just theory: the look-up table (LUT) at the heart of every FPGA is a 2k-to-1 MUX whose data inputs come from configuration memory bits, so one k-input LUT can be programmed to be any function of k variables (Method 1 above).
Using Method 2 with a tree of 2-to-1 MUXes, any function of n variables needs at most 2n−1 − 1 two-to-1 MUXes, if the last variable and its complement are available as data inputs (for example 3 MUXes for any 3-variable function).
Describing a MUX in Verilog
The same 4-to-1 MUX can be written in three styles, all of which synthesise to a multiplexer. The testbench checks all three on every combination of data and select values, prints one example, and then tests the 8-to-1 implementation of F from Worked Example 2(a):
// Style 1: conditional operator (dataflow)
module mux4_dataflow (input logic [3:0] i, input logic [1:0] s,
output logic y);
assign y = s[1] ? (s[0] ? i[3] : i[2])
: (s[0] ? i[1] : i[0]);
endmodule
// Style 2: case statement (behavioural)
module mux4_case (input logic [3:0] i, input logic [1:0] s,
output logic y);
always @(*) // re-evaluate whenever any input changes
case (s)
2'b00: y = i[0];
2'b01: y = i[1];
2'b10: y = i[2];
default: y = i[3];
endcase
endmodule
// Style 3: the sum-of-products equation (gate level)
module mux4_sop (input logic [3:0] i, input logic [1:0] s,
output logic y);
assign y = (~s[1] & ~s[0] & i[0]) | (~s[1] & s[0] & i[1])
| ( s[1] & ~s[0] & i[2]) | ( s[1] & s[0] & i[3]);
endmodule
// F(A,B,C,D) = sum of m(1,3,4,11,12,13,14,15) using an 8-to-1 MUX:
// selects = A B C, data inputs taken from {0, 1, D, D'}
module f_with_mux8 (input logic a, b, c, d, output logic f);
logic [7:0] in;
assign in = {1'b1, 1'b1, d, 1'b0, 1'b0, ~d, d, d}; // I7 ... I0
assign f = in[{a, b, c}];
endmodule
module tb;
logic [3:0] i; logic [1:0] s; logic y1, y2, y3;
logic a, b, c, d, f;
int errors = 0;
mux4_dataflow u1 (i, s, y1);
mux4_case u2 (i, s, y2);
mux4_sop u3 (i, s, y3);
f_with_mux8 u4 (a, b, c, d, f);
initial begin
// all 4-bit data patterns x all 4 select values
for (int k = 0; k < 64; k++) begin
{i, s} = k; #1;
if (y1 !== i[s] || y2 !== i[s] || y3 !== i[s]) errors++;
end
$display("4-to-1 MUX, 3 styles, 64 cases: %0d errors", errors);
i = 4'b1010;
for (int k = 0; k < 4; k++) begin
s = k; #1;
$display("I3..I0 = %b S1S0 = %b -> Y = %b", i, s, y1);
end
$write("F = 1 for minterms:");
for (int m = 0; m < 16; m++) begin
{a, b, c, d} = m; #1;
if (f) $write(" %0d", m);
end
$display("");
end
endmodule
Output (Icarus Verilog with -g2012):
4-to-1 MUX, 3 styles, 64 cases: 0 errors
I3..I0 = 1010 S1S0 = 00 -> Y = 0
I3..I0 = 1010 S1S0 = 01 -> Y = 1
I3..I0 = 1010 S1S0 = 10 -> Y = 0
I3..I0 = 1010 S1S0 = 11 -> Y = 1
F = 1 for minterms: 1 3 4 11 12 13 14 15
The last line lists exactly Σm(1, 3, 4, 11, 12, 13, 14, 15), confirming the implementation table. Notice in[{a, b, c}]: indexing a vector with a variable is how Verilog expresses "a multiplexer".
Applications of Multiplexers
Datapath selection: choosing the ALU's second operand (register or immediate), the next PC value (PC + 4 or a branch target), or the value written back to a register.
Time-division multiplexing: by stepping the select lines through 0, 1, 2, ... with a counter, a MUX sends several signals one after another over a single line (and a demultiplexer at the other end separates them, as the next chapter, Demultiplexers, shows).
Parallel-to-serial conversion: the same counter trick sends the bits of a parallel word out one at a time.
Logic implementation: any function, as shown above; FPGA LUTs.
Fast adders: the carry-select adder (mentioned in Ripple-Carry & Carry Look-Ahead Adders) uses MUXes to pick between two precomputed sums.
Shifters: a barrel shifter is built from layers of 2-to-1 MUXes.
Common Mistakes
Wrong number of select lines. An N-to-1 MUX has log2N selects: an 8-to-1 MUX has 3, not 8.
Swapping the select order. S1 is the MSB of the select value: S1S0 = 10 picks I2, not I1. In a function implementation, the variable on the MSB select must be the MSB of the minterm numbering you used.
Counting a MUX tree as N/2. 16-to-1 from 2-to-1 needs 8 + 4 + 2 + 1 = 15 MUXes, not 8.
Feeding the wrong select bit to the first level of a tree. The first level must use the LSB (S0); otherwise inputs come out in the wrong order.
Mixing up MUX and DEMUX. A MUX has many data inputs and one output; a DEMUX has one data input and many outputs.
Reading the implementation table from the wrong row. If only the A′ row is circled, the input is A′ (not A).
Ignoring the enable. On chips such as the 74x151 the enable is active-low: tie it to 0 (not 1) for normal operation.
GATE and Interview Questions
Q1. How many 2-to-1 MUXes are needed to build a 32-to-1 MUX?
16 + 8 + 4 + 2 + 1 = 31 (N − 1).
Q2. How many 4-to-1 MUXes are needed to build a 32-to-1 MUX?
Level 1: 32/4 = 8. Level 2: 8/4 = 2. Level 3: 2 outputs remain, so 1 more MUX (used as a 2-to-1). Total 11.
Q3. Implement F(A, B, C) = Σm(0, 1, 5, 6) using a 4-to-1 MUX with A, B on the select lines.
AB = 00: m0 = 1, m1 = 1 → I0 = 1. AB = 01: m2 = 0, m3 = 0 → I1 = 0. AB = 10: m4 = 0, m5 = 1 → I2 = C. AB = 11: m6 = 1, m7 = 0 → I3 = C′.
Q4. A 2-to-1 MUX has select A, I0 = B and I1 = 1. What gate is it?
Y = A′B + A·1 = A + A′B = A + B, an OR gate.
Q5. In a 4-to-1 MUX, S1 = A, S0 = B, I0 = 0, I1 = 1, I2 = 1, I3 = 0. What is Y?
Y = A′B·1 + AB′·1 = A ⊕ B.
Q6. Why is a multiplexer called a universal logic circuit?
A 2n-to-1 MUX can realise every function of n variables (put the truth table on the data inputs), and even a 2-to-1 MUX with constants can make NOT, AND and OR, which form a complete set.
Q7. What is the minimum size of MUX needed to implement any function of 5 variables directly, without extra gates other than an inverter?
Using 4 variables as selects and the fifth (or its complement, 0, 1) as data: a 16-to-1 MUX.
Summary
A MUX routes one of 2n data inputs to a single output under control of n select lines: Y = Σ mk(selects) · Ik.
2-to-1: Y = S′I0 + SI1. 4-to-1: Y = S1′S0′I0 + S1′S0I1 + S1S0′I2 + S1S0I3. An enable input ANDs every term.
Larger MUXes: a tree (N − 1 two-to-1 MUXes for N inputs, LSB select at the first level) or small MUXes with enables plus an OR gate.
Any n-variable function fits on a 2n−1-to-1 MUX: n − 1 variables on the selects, and 0, 1, X or X′ on each data input (implementation table).
The 2-to-1 MUX is functionally complete; FPGA LUTs are multiplexers.
Next, Demultiplexers do the opposite job: one input routed to one of many outputs.