Multiplexers
Build multiplexers from the 2:1 equation up, use one as a lookup table, and write a mux tree with parameters.
You Will Be Able To
- Write the 2:1 mux equation and build wider muxes from it.
- Count the 2:1 muxes and levels in an n:1 mux tree.
- Build any function of n variables on one mux with n − 1 select lines.
- Write a bus mux and a mux tree with
parameterandgenerate.
- Lesson
- G4.2
- Time
- 25 min
- Runs on
- Your browser
- Check
- 5 questions
A camera board picks one of four sensors with a 2-bit select. During bring-up, the firmware asks for sensor 1 and receives sensor 2. The two select wires were crossed between the processor and the mux.
- Cycle 0
Select 0 is 00. Crossing the two wires changes nothing, so sensor 0 arrives.
- Cycle 1
Select 1 is 01. Crossed, it becomes 10, and the mux passes sensor 2.
- Cycle 2
Select 2 is 10. Crossed, it becomes 01, so sensor 1 arrives instead.
- Cycle 3
Select 3 is 11 either way. Half of the selects work, which is why the bug survived a quick test.
Measured on the simulator: the lab bench of this hook prints wanted and got for each select.
The 2:1 Mux
A multiplexer (mux) passes one of its data inputs to the output. The select input decides which one. A 2:1 mux has data inputs d0 and d1 and one select s.
Its equation is y = s′·d0 + s·d1. When s is 0 the first product passes d0. When s is 1 the second product passes d1. In SystemVerilog it is s ? d1 : d0.
For a bus, the same mux is copied once per bit, and every copy shares the one select line. A 2:1 mux of 8-bit words is eight 2:1 muxes side by side.
Wider Muxes, Built from Smaller Ones
A 4:1 mux has four data inputs and two select bits. Build it from three 2:1 muxes in two levels. The first level uses s0 to pick inside each pair. The second level uses s1 to pick a pair.
The same idea scales. An n:1 mux built as a tree needs n − 1 two-input muxes in log2 n levels. Each level halves the number of candidates.
| Mux | Select bits | 2:1 muxes in a tree | Tree levels | Synthesized: cells, levels |
|---|---|---|---|---|
| 2:1 | 1 | 1 | 1 | 1, 1 |
| 4:1 | 2 | 3 | 2 | 3, 2 |
| 8:1 | 3 | 7 | 3 | 7, 3 |
| 16:1 | 4 | 15 | 4 | 25, 6 |
The last column was measured on this site for a one-bit mux written as d[s]. Up to 8:1 the tool built the tree. At 16:1 it chose another structure.
A Mux as a Function Generator
A mux can build any function. Put the input variables on the select lines and the truth table on the data inputs. A 4:1 mux with selects a and b and data 0, 1, 1, 0 is an XOR of a and b.
One variable can stay off the selects. This rests on Shannon expansion: f = a′·f(0, b, c) + a·f(1, b, c). Fix every select variable and look at the rows that remain. What is left is a function of one variable: 0, 1, c or c′.
| a b (select) | Row c = 0 | Row c = 1 | Data input |
|---|---|---|---|
| 0 0 | f = 0 | f = 1 | c |
| 0 1 | f = 1 | f = 0 | ~c |
| 1 0 | f = 0 | f = 0 | 1'b0 |
| 1 1 | f = 1 | f = 1 | 1'b1 |
f = Σm(1, 2, 6, 7). Each pair of rows with the same a and b becomes one data input.
- I/O
- Datapath
- Neutral
- Data
- Control
- Row 011
a = 0, b = 1, c = 1. The select is 01, so the mux passes d1. That is c′ = 0, and f = 0.
Follow the calls, values and waits
- data c = 1: c → Inverter
- data ab = 01: a, b → 4:1 mux
- data c′ = 0: Inverter → 4:1 mux
- data c′ = 0: 4:1 mux → f
- Rows 110 and 111
a = b = 1 selects d3, which is tied to 1. f is 1 whatever c is.
Follow the calls, values and waits
- data ab = 11: a, b → 4:1 mux
- data 1: Constants → 4:1 mux
- data 1: 4:1 mux → f
Read the diagram as text
- c: last variable
- Inverter: c′
- Constants: 0 and 1
- a, b: select lines
- 4:1 mux: d0 = c, d1 = c′, d2 = 0, d3 = 1
- f: Σm(1, 2, 6, 7)
- c → 4:1 mux: d0
- c → Inverter: c
- Inverter → 4:1 mux: d1
- Constants → 4:1 mux: d2, d3
- a, b → 4:1 mux: s
- 4:1 mux → f: y
A 2^(n−1):1 mux and at most one inverter build any function of n variables.
The cost is fixed by the number of variables, not by the function. An FPGA lookup table works this way: a mux whose data inputs are configuration bits (lesson G13.3).
Bus Muxes and a Mux Tree with Parameters
A parameter is a constant that each copy of a module can set for itself. Here W is the word width. The same mux2 code then builds a one-bit mux or a 32-bit bus mux.
A for loop over a genvar at module level is a generate loop. It makes one copy of the hardware per pass, when the design is built. It does not run in time like a software loop.
module mux2 #(parameter int W = 1) (
input logic [W-1:0] d0, d1,
input logic s,
output logic [W-1:0] y
);
assign y = s ? d1 : d0;
endmodule
// mux8: eight W-bit words, a tree of seven mux2 in three levels.
module mux8 #(parameter int W = 4) (
input logic [8*W-1:0] d, // word k is d[k*W +: W]
input logic [2:0] s,
output logic [W-1:0] y
);
logic [3:0][W-1:0] lvl1; // four words after level 1
logic [1:0][W-1:0] lvl2; // two words after level 2
for (genvar i = 0; i < 4; i++) begin : level1
mux2 #(W) u (.d0(d[2*i*W +: W]), .d1(d[(2*i+1)*W +: W]), .s(s[0]), .y(lvl1[i]));
end
for (genvar i = 0; i < 2; i++) begin : level2
mux2 #(W) u (.d0(lvl1[2*i]), .d1(lvl1[2*i+1]), .s(s[1]), .y(lvl2[i]));
end
mux2 #(W) last (.d0(lvl2[0]), .d1(lvl2[1]), .s(s[2]), .y(y));
endmoduleThe tree is three levels of mux2. s[0] picks inside each pair, s[1] picks a pair of pairs, and s[2] picks a half. Each copy gets W from #(W).
Asked in interviews
Build a function with a 4:1 mux.
Put two of the variables on the select lines. For each select value, look at the two rows of the truth table that remain. Each data input is then 0, 1, the third variable or its complement.
How many 2:1 muxes make a 16:1 mux?
Fifteen, in four levels. Each 2:1 mux removes one candidate, and each level halves the candidates.
How do you make XOR from a 2:1 mux?
Put a on the select line, b on d0 and b′ on d1. When a is 0 the output is b, and when a is 1 it is b′.
Try It
The bench tries all eight rows. f matches the table, so it prints 0 of 8 rows wrong.
Press Synthesize. The Gates tab shows 2 cells, not a mux and an inverter. The tool folded the two constants into the logic.
Change the function to Σm(0, 3, 4, 5). Work out the four data inputs from the table, edit the instance, and edit want in the bench to 8'b0011_1001.
Swap the select lines to {b, a} and run. Some rows go wrong, because each data input now meets the wrong pair of rows.
Synthesize the design to measure its cells and inspect the mapped gates.
abc=000 f=0 abc=001 f=1 abc=010 f=1 abc=011 f=0 abc=100 f=0 abc=101 f=0 abc=110 f=1 abc=111 f=1 0 of 8 rows wrongOriginal design · 2 cells · 0 flip-flops · 0 latches · 2 logic levels. Synthesis uses Yosys; counts depend on the toolchain.
Read included file: tb.sv
// tb.sv: tries all eight rows and compares f with the truth table (read-only).
module tb;
logic a, b, c, f;
logic [7:0] want = 8'b1100_0110; // bit m is f for row m = {a, b, c}: minterms 1, 2, 6 and 7
int wrong = 0;
fgen dut (.a(a), .b(b), .c(c), .f(f));
initial begin
for (int m = 0; m < 8; m++) begin
{a, b, c} = m[2:0];
#1;
if (f !== want[m]) wrong++;
$display("abc=%b f=%b%s", {a, b, c}, f, f === want[m] ? "" : " wrong");
end
$display("%0d of 8 rows wrong", wrong);
end
endmodule
Check Yourself
Common Mistakes
Wrong Connect the select bits in the wrong order.
With s1 and s0 crossed, select 1 picks input 2 and select 2 picks input 1. Selects 0 and 3 still work, so a short test passes.
Fix Test every select value. Keep the most significant select bit on the last level of the tree.
Wrong Leave a select value without an arm in a case.
For that value the output keeps its old value, which needs a latch (lesson G4.1).
Fix Give the last arm as default, so every select value drives the output.
case (s)
2'd0: y = d0;
2'd1: y = d1;
2'd2: y = d2;
endcasecase (s)
2'd0: y = d0;
2'd1: y = d1;
2'd2: y = d2;
default: y = d3;
endcaseWrong Put the last input variable on a select line when you build a function on a mux.
The data inputs must hold what is left of the function. If the wrong variables select, the data values come from the wrong rows.
Fix Put the first n − 1 variables on the selects. Each data input is then 0, 1, the last variable or its complement.
Wrong Count the gates of a mux tree from the Gates tab.
The synthesizer rebuilds the logic. A 16:1 mux written as d[s] came out as 25 cells in 6 levels, not 15 muxes in 4.
Fix Count the structure from your own netlist. Use the Gates tab to see what the tool built.
Remember
- A 2:1 mux is y = s′·d0 + s·d1, written
s ? d1 : d0. - An n:1 mux tree needs n − 1 two-input muxes in log2 n levels.
- One 2^(n−1):1 mux and an inverter build any function of n variables (Shannon expansion).
- Parameters set widths per copy; a generate loop places one copy of hardware per pass.
- Test every select value: crossed select bits pass half of a short test.