32:1 MUX tree; implement Σm(0,1,3,8,9,13,15)

32:1 MUX by multiplexer tree

A 32:1 MUX needs 5 select lines $S_4$–$S_0$. A common tree uses four 8:1 MUXes and one 4:1 MUX:

• Level 1: four 8:1 MUXes with selects $S_2S_1S_0$: M1 takes $I_0$–$I_7$, M2 $I_8$–$I_{15}$, M3 $I_{16}$–$I_{23}$, M4 $I_{24}$–$I_{31}$.
• Level 2: one 4:1 MUX (M5) with selects $S_4S_3$ selects one of M1–M4.

           S2 S1 S0
 I0-I7   -->[M1 8:1]--+
 I8-I15  -->[M2 8:1]--+-->[M5 4:1]---> Y
 I16-I23 -->[M3 8:1]--+     S4 S3
 I24-I31 -->[M4 8:1]--+

Example: $S = 10101$ → M3 picks its input 5 ($I_{21}$) and M5 ($S_4S_3 = 10$) passes it, so $Y = I_{21}$. (With only 4:1 MUXes the tree would need 8 + 2 + 1 = 11 MUXes.)

Implementing $Y = \Sigma m(0,1,3,8,9,13,15)$

The largest minterm is 15, so $Y = Y(A,B,C,D)$. A suitable MUX is an 8:1 MUX with $A, B, C$ on the selects and $D$ on the data inputs.

            +--------+
  1 ------->| I0     |
  D ------->| I1     |
  0 ------->| I2     |
  0 ------->| I3 8:1 |----> Y
  1 ------->| I4 MUX |
  0 ------->| I5     |
  D ------->| I6     |
  D ------->| I7     |
            +--------+
             A  B  C

Check: $ABCD = 1111$ (15): select 111 → $I_7 = D = 1$, $Y = 1$. $ABCD = 0010$ (2): select 001 → $I_1 = D = 0$, $Y = 0$. All 16 rows match.