MUX tree

Also called: multiplexer tree, cascaded multiplexers, multiplexer cascade, cascading multiplexers

A large multiplexer built from levels of smaller ones, usually 2:1 MUXes. A 2ⁿ:1 tree of 2:1 MUXes uses 2ⁿ − 1 of them, with S0 driving the first level.

A MUX tree builds a big multiplexer out of small ones, like a knockout tournament. At each level, pairs of signals compete and one survivor moves on.

With 2:1 MUXes, a 4:1 MUX looks like this:

Level 1: two 2:1 MUXes, both with select S0. One picks between I0 and I1, the other between I2 and I3.
Level 2: one 2:1 MUX with select S1 picks between those two winners.

Why S0 goes first: I0 and I1 differ only in S0 (codes 00 and 01), and so do I2 and I3. So S0 settles each pair, and S1 then chooses the pair.

Counting: each 2:1 MUX removes exactly one candidate. Starting with 2ⁿ inputs and ending with 1, a tree needs 2ⁿ − 1 MUXes:

4:1 → 2 + 1 = 3
8:1 → 4 + 2 + 1 = 7
16:1 → 8 + 4 + 2 + 1 = 15

The select lines run from the LSB at the first level to the MSB at the last. Trees can also use bigger pieces, such as 4:1 MUXes feeding another 4:1.

Worked examples

Example

Tracing an 8:1 tree

An 8:1 MUX built from seven 2:1 MUXes: four on S0, two on S1, one on S2. Selects S2 S1 S0 = 110.

1.
Level 1 (S0 = 0): each pair passes its even input. Survivors: I0, I2, I4, I6.
2.
Level 2 (S1 = 1): from (I0, I2) pick I2; from (I4, I6) pick I6.
3.
Level 3 (S2 = 1): from (I2, I6) pick I6.
4.
Output = I6, and 110₂ = 6. ✓

Example

Cost of a 32:1 tree

How many 2:1 MUXes, and how many levels?

1.
32 = 2⁵, so 5 select lines and 5 levels.
2.
MUXes: 16 + 8 + 4 + 2 + 1 = 31 = 2⁵ − 1.

Common mistakes

Driving the first level with the MSB select. Pairs of neighboring inputs differ in S0, so S0 belongs on the first level.
Counting log₂ of the inputs as the number of MUXes. That's the number of levels; the MUX count is 2ⁿ − 1.
Giving each MUX in a level its own select line. All MUXes in one level share the same select.

Practice MUX tree

Interactive questions with instant feedback and a worked solution for every wrong answer.

Combinational Logic lesson full course

Practice exams

Learn it step by step

MUX tree is taught in Combinational Logic.

Combinational Logic →

All terms