6.9 Multiplexer: Selecting One of Many Inputs
Explain how a multiplexer's select lines choose one of 2^n data inputs to route to its output, derive the 2:1 MUX equation, and describe how a multiplexer can implement arbitrary Boolean functions.
A multiplexer (MUX) is a combinational circuit that selects exactly one of several data inputs and routes it through to a single output, based on the binary value presented on a separate set of select lines. It functions as a digitally controlled switch: rather than mechanically flipping between input signals, a MUX uses Boolean logic to decide, instantaneously and for every combination of select-line values, which single input gets passed through — making it one of the most versatile and widely used building blocks in digital design, used for data routing, bus selection, and even implementing arbitrary logic functions.
The general 2^n : 1 structure
A multiplexer with n select lines can choose among 2^n distinct data inputs, since n binary select bits can encode exactly 2^n distinct binary codes, one for each possible data input. A 2:1 MUX (2 inputs) needs only 1 select line, a 4:1 MUX (4 inputs) needs 2 select lines, an 8:1 MUX (8 inputs) needs 3 select lines, and so on — the relationship between select-line count and input count is always this same power-of-two correspondence.
Internally, a MUX is typically built from a set of AND gates (one per data input, each gated by a unique combination of the select lines, so that only one AND gate is 'open' at a time) whose outputs all feed into a single OR gate — the OR gate's output becomes the MUX output, and because only one AND gate is active for any given select-line combination, exactly one data input passes through at a time.
Deriving the 2:1 MUX equation
For a 2:1 MUX with data inputs I0 and I1 and a single select line S, the output Y must equal I0 when S=0 and I1 when S=1. Expressed as a Boolean sum: Y = S'I0 + SI1 — the S'I0 term is active (passes I0 through) exactly when S=0 (since S'=1 then, and the AND gate for I0 is open), and the SI1 term is active (passes I1 through) exactly when S=1. Because S and S' can never both be 1 at the same time, exactly one of the two terms is ever active, guaranteeing the output always reflects a single, well-defined selected input.
This same generate-one-AND-term-per-input-then-OR-them-together pattern extends directly to wider multiplexers: a 4:1 MUX's output is Y = S1'S0'I0 + S1'S0I1 + S1S0'I2 + S1S0I3, with each AND term gated by a unique 2-bit combination of the select lines S1S0, ensuring exactly one of the four data inputs is ever selected.
A multiplexer can implement arbitrary Boolean functions
Because a MUX's select lines can be driven not just by a 'control' signal but by any Boolean function's actual input variables, and its data inputs can be tied to fixed 0s and 1s (or to other logic signals), a sufficiently large multiplexer can implement any Boolean truth table directly: route each variable combination's required output value (0 or 1) onto the data input corresponding to that combination's select-line code. A 2^n:1 MUX driven by n of a function's input variables on its select lines, with each data input tied to the correct 0 or 1 from the truth table, exactly reproduces that function — no separate AND/OR/NOT gate network is required at all.
This universality is more than a theoretical curiosity: MUX-based logic implementation is a genuinely used technique in FPGA design, since FPGA lookup tables (LUTs) are, at their core, exactly this kind of multiplexer-based structure — a small block of configuration memory bits feeding a MUX tree, selected by the LUT's input signals, is how FPGAs implement arbitrary small logic functions in reconfigurable hardware.
MUX select-line to input-count relationship and 2:1 equation
n select lines always correspond to exactly 2^n data inputs — this relationship never varies. Only one AND term in the MUX's sum-of-products output can ever be active at a time, since select-line combinations are mutually exclusive.
For 2^n inputs: n select lines
2:1 MUX equation: Y = S'I0 + SI1
S=0 -> Y = I0
S=1 -> Y = I1Code Examples
This is the spec's own worked example: S=0 routes I0 to the output, S=1 routes I1 to the output. The equation Y = S'I0 + SI1 mechanically reproduces this behavior, since exactly one of the two product terms is active depending on S's value. Expected result: Y follows I0 when S=0, I1 when S=1
S=0 → Y=I0; S=1 → Y=I1, exactly as the equation Y = S'I0 + SI1 predicts.
This demonstrates the spec's tricky problem directly: a MUX can implement arbitrary Boolean functions, not just act as a simple data selector. By wiring the function's own input variables to the select lines and hard-wiring each data input to the correct required output bit from the truth table, the MUX becomes a complete implementation of any function of that many variables with no separate logic gates needed.
Driving a MUX's select lines with a function's own inputs, and its data inputs with the truth table's output values, implements that function directly.
S | Y
0 | I0
1 | I1
Verify via the equation Y = S'I0 + SI1:
S=0: Y = (1)I0 + (0)I1 = I0 -- matches
S=1: Y = (0)I0 + (1)I1 = I1 -- matchesImplement F(A,B) = Σm(1,2) using a 4:1 MUX with select lines S1=A, S0=B:
Select code (S1 S0) | corresponding minterm | required F value | tie this MUX data input to:
00 | m0 | 0 | I0 = 0
01 | m1 | 1 | I1 = 1
10 | m2 | 1 | I2 = 1
11 | m3 | 0 | I3 = 0
Any input combination (A,B) selects the data input holding exactly the correct output value --
the MUX itself needs no additional gates; it directly reproduces F(A,B)'s truth table.2:1 and 4:1 multiplexer block diagrams
Select-line count and data-input count always follow the 2^n relationship: n lines select among 2^n inputs.
2:1 MUX: 4:1 MUX:
I0 ---\ I0 ---\
\ \
I1 ----[MUX]---- Y I1 -----[MUX]---- Y
/ /
S I2 --/
(1 select line -> 2 inputs) I3 -/
|
S1 S0 (2 select lines -> 4 inputs)Important Rules
n select lines allow selection among exactly 2^n data inputs.
2:1 MUX: Y = S'I0 + SI1 — exactly one product term is active for any value of S.
Only one data input is ever routed to the output at a time, for any given select-line combination.
A MUX with n select lines driven by a function's own variables, and data inputs tied to the correct truth-table outputs, can implement any Boolean function of those n variables.
Where multiplexers are used
Multiplexers are everywhere in digital systems: a CPU's ALU input stage uses multiplexers to select between different operand sources; register files use multiplexers to select which stored register's contents appear on a read bus; communication systems use multiplexers (time-division multiplexing) to interleave multiple data streams onto a single shared physical channel; and, as noted above, FPGA lookup tables are internally built from multiplexer trees, making the multiplexer one of the most fundamental and reused structural elements in all of digital hardware design.
Block Diagram
2ⁿ Input Channels n Control Signals A multiplexer collapses many data channels down to one: 2ⁿ input lines converge into the MUX block, and the n select (control) lines feeding its bottom edge decide, at every instant, which single input reaches the output.
Treating a multiplexer purely as a 'wire selector' for routing signals, and never considering it as a way to implement general logic functions.
Recognize that a MUX can implement arbitrary Boolean functions by driving its select lines with the function's variables and its data inputs with the correct truth-table output values — a technique used directly in FPGA lookup tables.
The spec's tricky problem states this directly: a MUX can implement arbitrary Boolean functions. Missing this generalizes poorly — MUX-based logic implementation is a standard, practically important technique, not just a textbook curiosity.
Assuming a MUX with n select lines can handle more than 2^n data inputs by 'reusing' select combinations.
Keep the 2^n relationship strict: n select lines address exactly 2^n distinct data inputs, no more, since that is the total number of distinct binary codes n bits can represent.
Each select-line combination must uniquely identify one data input for the MUX to function correctly; exceeding 2^n inputs would require additional select lines to keep every input separately addressable.
[tricky] Besides selecting between existing signals, what else can a multiplexer be used for? A. Implementing arbitrary Boolean functions, by driving its select lines with the function's variables and its data inputs with fixed 0/1 values from the truth table B. Nothing else — multiplexers can only route pre-existing signals, never implement new logic functions C. Storing state between clock cycles, functioning as a simple memory element D. Amplifying a digital signal's voltage level
A. Implementing arbitrary Boolean functions, by driving its select lines with the function's variables and its data inputs with fixed 0/1 values from the truth table — The spec's tricky problem states this directly: a MUX can implement arbitrary Boolean functions. This is the same principle FPGA lookup tables rely on internally, and it is a standard technique for building small logic functions without a dedicated gate network.
How many select lines does a multiplexer need to choose among 8 data inputs? A. 3 select lines, since 2^3 = 8 B. 8 select lines, one per input C. 4 select lines, since 8 is not itself a power of 2 D. 2 select lines, since that is the minimum for any multiplexer
A. 3 select lines, since 2^3 = 8 — The relationship between select lines and data inputs is always 2^n inputs for n select lines. Since 2^3 = 8, exactly 3 select lines are needed and sufficient to uniquely address 8 distinct data inputs.
Using a 2:1 MUX, implement the Boolean function F(A) = A' (the NOT of a single variable A), by choosing what to wire to I0, I1, and S.
Wire S = A, I0 = 1, I1 = 0. When A=0 (S=0), Y = I0 = 1, matching A'=1. When A=1 (S=1), Y = I1 = 0, matching A'=0. This shows even a simple NOT function can be implemented with a MUX and two constant inputs, with no NOT gate required.
Set the select line S = A, and choose fixed 0/1 values for I0 and I1 so that the MUX output matches A' for both values of A.