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 parameter and generate.
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.

A 4:1 Mux with Its Select Wires CrossedOne select value per step. Sensor k sends a reading whose low digit is k.
0123sel0123wanted10213243got10322143asks 1, gets 2
Scroll horizontally ↔
  1. Cycle 0

    Select 0 is 00. Crossing the two wires changes nothing, so sensor 0 arrives.

  2. Cycle 1

    Select 1 is 01. Crossed, it becomes 10, and the mux passes sensor 2.

  3. Cycle 2

    Select 2 is 10. Crossed, it becomes 01, so sensor 1 arrives instead.

  4. 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.

The 2:1 Mux as Gates
sd1d0y
000
001
010
011
100
101
110
111

Minimum SOP

~s & d0 | s & d1

2 terms · 4 literals

Minimum POS

(s | d0) & (~s | d1)

2 sum terms · 4 literals

The 2:1 Mux as Gatesn2 · NOTn2=1n1 · ANDn1=0n3 · ANDn3=0n0 · ORn0=0s=0d1=0d0=0
s=0 d1=0 d0=0
n2 · NOTs=0 → n2=1
n1 · ANDn2=1, d0=0 → n1=0
n3 · ANDs=0, d1=0 → n3=0
n0 · ORn1=0, n3=0 → n0=0
Read the connections
GateKindInputsOutput
n2NOTsn2
n1ANDn2, d0n1
n3ANDs, d1n3
n0ORn1, n3n0

Outputs: n0. MUX inputs: d0, d1, select. Latch/flip-flop inputs: data, enable/clock. Unknown values are marked x; high impedance is folded into x in this model.

Click the input pins. With s at 0, y follows d0; with s at 1, y follows d1.

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.

A 4:1 Mux From Three 2:1 Muxes
A 4:1 Mux From Three 2:1 Muxes01Sg0 · MUXlo=101Sg1 · MUXhi=101Sg2 · MUXy=1d0=0d1=1d2=0d3=1s0=1s1=1
d0=0 d1=1 d2=0 d3=1 s0=1 s1=1
g0 · MUXd0=0, d1=1, s0=1 → lo=1
g1 · MUXd2=0, d3=1, s0=1 → hi=1
g2 · MUXlo=1, hi=1, s1=1 → y=1
Read the connections
GateKindInputsOutput
g0MUXd0, d1, s0lo
g1MUXd2, d3, s0hi
g2MUXlo, hi, s1y

Outputs: y. MUX inputs: d0, d1, select. Latch/flip-flop inputs: data, enable/clock. Unknown values are marked x; high impedance is folded into x in this model.

Gate delay 17. Settled after 17 gate delays from t = 0.

Output values at each gate delay01234567891011121314151617yxx0000011111000001
Scroll horizontally ↔
Every computed frame
Timey
0x
1x
20
30
40
50
60
71
81
91
101
111
120
130
140
150
160
171

  1. Step 2 · s = 00. Both first-level muxes pass d0 and d2. The last mux passes the lower pair. After two gate delays, y = d0 = 0.
  2. Step 7 · s = 01 at time 5. s0 flips both first-level muxes to d1 and d3. Two gate delays later, y = d1 = 1.
  3. Step 12 · s = 10 at time 10. s0 picks d0 and d2 again, and s1 picks the upper pair. y = d2 = 0.
  4. Step 17 · s = 11 at time 15. Now y = d3 = 1. Click a data pin and step again to see which inputs reach y.

The mux4 preset: d = 1010 (d3 d2 d1 d0), and s steps through 00, 01, 10 and 11.

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.

MuxSelect bits2:1 muxes in a treeTree levelsSynthesized: cells, levels
2:11111, 1
4:12323, 2
8:13737, 3
16:1415425, 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 = 0Row c = 1Data input
0 0f = 0f = 1c
0 1f = 1f = 0~c
1 0f = 0f = 01'b0
1 1f = 1f = 11'b1

f = Σm(1, 2, 6, 7). Each pair of rows with the same a and b becomes one data input.

f(a, b, c) on One 4:1 Muxa and b drive the select lines. The data inputs carry c, the inverted c and two constants.
  • I/O
  • Datapath
  • Neutral
  • Data
  • Control
CallValueReturnWaiting
f(a, b, c) on one 4:1 muxa and b drive the select lines. The data inputs carry c, the inverted c and two constants. io c last variable datapath Inverter c′ neutral Constants 0 and 1 io a, b select lines datapath 4:1 mux d0 = c, d1 = c′, d2 =0, d3 = 1 io f Σm(1, 2, 6, 7) d0cd1d2, d3sy
  1. io clast variable
    • d0 → 4:1 mux
    • c → Inverter
  2. datapath Inverterc′
    • d1 → 4:1 mux
  3. io a, bselect lines
    • s → 4:1 mux
  4. datapath 4:1 muxd0 = c, d1 = c′, d2 = 0, d3 = 1
    • y → f
  5. io fΣm(1, 2, 6, 7)
  6. neutral Constants0 and 1
    • d2, d3 → 4:1 mux
  1. 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
    1. data c = 1: c → Inverter
    2. data ab = 01: a, b → 4:1 mux
    3. data c′ = 0: Inverter → 4:1 mux
    4. data c′ = 0: 4:1 mux → f
  2. 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
    1. data ab = 11: a, b → 4:1 mux
    2. data 1: Constants → 4:1 mux
    3. 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.

An 8:1 mux tree of W-bit words. Two generate loops build the first two levels; one more mux2 makes the third.
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));
endmodule

The 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
  1. 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.

  2. 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.

  3. 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.

RTLIcarus Verilog · in your browser · Lint: Verilator service · Synthesize: Yosys service
Edit the design, then Run, Lint or Synthesize
Expected: 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 wrong

Original 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

Spot the bugEach option is the body of an always_comb block of a 4:1 mux of bytes. The bench tries all four selects. Which body fails?
ConceptA function of four variables must be built on one mux and at most one inverter. What is the smallest mux that always works?
ConceptA 4:1 mux has a on s1 and b on s0. Its data inputs are d0 = 0, d1 = 1, d2 = 1 and d3 = 1. Which function is it?
ConceptIn a generate loop for (genvar i = 0; i < 4; i++) that holds one mux2 instance, what does the loop do?
Predict the outputA 4:1 mux of single bits has data d = 4'b0110 (d3 on the left) and selects 0 to 3. Predict the exact line.
module tb;
  logic [3:0] d = 4'b0110;
  initial $display("%b%b%b%b", d[2'd0], d[2'd1], d[2'd2], d[2'd3]);
endmodule

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.

Before
case (s)
  2'd0: y = d0;
  2'd1: y = d1;
  2'd2: y = d2;
endcase
After
case (s)
  2'd0:    y = d0;
  2'd1:    y = d1;
  2'd2:    y = d2;
  default: y = d3;
endcase

Wrong 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.

Practice

Report a problem with this page