2074 Chaitra · 4+2 marks

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

Short answer

32:1 MUX tree: eight 4:1 MUXes with S1S0, two with S3S2, one final with S4 on S0 (S1=0), total 11. F = Σ(0,1,3,8,9,13) implemented by 8:1 MUX with A,B,C as selects: I0=I4=1, I1=I6=D, others 0.

Design the 32:1 Multiplexer using 4:1 multiplexers tree concept and implement the function F = Σ(0,1,3,8,9,13) using suitable Multiplexer.

32:1 MUX using a 4:1 multiplexer tree

A 32:1 MUX has 32 data inputs and 5 select lines $S_4S_3S_2S_1S_0$ ( $2^5 = 32$ ). With 4:1 MUXes (2 selects each) the tree has three levels:

Level	4:1 MUXes	Select lines	Function
1	8 (M1–M8)	$S_1S_0$	Each picks 1 of 4 inputs
2	2 (M9, M10)	$S_3S_2$	Each picks 1 of 4 level-1 outputs
3	1 (M11)	$S_4$ (on its $S_0$ ; its $S_1 = 0$ )	Picks M9 or M10

 I0-I3   ->[M1 ]--+
 I4-I7   ->[M2 ]--+->[M9 ]--+
 I8-I11  ->[M3 ]--+  S3S2   |
 I12-I15 ->[M4 ]--+         |    S4 on S0,
                            +--->[M11]---> Y
 I16-I19 ->[M5 ]--+         |    S1 = 0
 I20-I23 ->[M6 ]--+->[M10]--+
 I24-I27 ->[M7 ]--+  S3S2
 I28-I31 ->[M8 ]--+
   (M1-M8 use S1S0)

Total: 11 MUXes of 4:1 (the last one uses only two inputs; a 2:1 MUX could replace it). Example: $S_4..S_0 = 10110$ → M6 passes $I_{22}$ , M10 ( $S_3S_2 = 01$ ) passes M6, M11 ( $S_4 = 1$ ) passes M10, so $Y = I_{22}$ .

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

The largest minterm is 13, so F is a 4-variable function $F(A,B,C,D)$ . A suitable MUX is an 8:1 MUX with $A, B, C$ as selects and $D$ on the data side.

	$I_0$	$I_1$	$I_2$	$I_3$	$I_4$	$I_5$	$I_6$	$I_7$
$D'$	0	2	4	6	8	10	12	14
$D$	1	3	5	7	9	11	13	15
Input	1	$D$	0	0	1	0	$D$	0

            +--------+
  1 ------->| I0     |
  D ------->| I1     |
  0 ------->| I2,I3  |
  1 ------->| I4 8:1 |----> F
  0 ------->| I5     |
  D ------->| I6     |
  0 ------->| I7     |
            +--------+
             A  B  C (S2 S1 S0)

Check: $ABCD = 1101$ (13): select 110 → $I_6 = D = 1$ , so $F = 1$ . $ABCD = 1100$ (12): $I_6 = 0$ , so $F = 0$ .

✓ Answer checked by Claude Opus 5.5 (high effort)

32:1 MUX tree; implement Σm(0,1,3,8,9,13,15) · Digital Logic, chapter 4
Multiplexer tree; 16:1 MUX from 4:1 · Digital Logic, chapter 4
32:1 MUX from 16:1 and 2:1 MUXes · Digital Logic, chapter 4
Σ(0,2,3,6,7,8,12,13,15) using 8×1 MUX · Digital Logic, chapter 4
8:1 MUX operation; 32:1 MUX from 8:1 · Digital Logic, chapter 4
Multiplexer and 4:1 MUX · Basic Electronics Engineering, chapter 6 · asked 2×

All Digital Logic chapter 4 questions →

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

32:1 MUX using a 4:1 multiplexer tree

Implementing F=Σm(0,1,3,8,9,13)F = \Sigma m(0,1,3,8,9,13)F=Σm(0,1,3,8,9,13)

Related questions

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