SSC IMD SA 2017 – Question 105

The number of 2-input multiplexers required to construct a 2^10-input multiplexer is

• 1024
• 1023
• 32
• 31

Detailed Explanation:

The correct answer is b) 1023.

Problem Formulation: We need to determine the number of 2-to-1 (2-input) multiplexers required to construct a $2^{10}$-to-1 (1024-input) multiplexer tree.

Step-by-step Level Calculation:

• Level 1: $\frac{1024}{2} = 512$ MUXes
• Level 2: $\frac{512}{2} = 256$ MUXes
• Level 3: $\frac{256}{2} = 128$ MUXes
• Level 4: $\frac{128}{2} = 64$ MUXes
• Level 5: $\frac{64}{2} = 32$ MUXes
• Level 6: $\frac{32}{2} = 16$ MUXes
• Level 7: $\frac{16}{2} = 8$ MUXes
• Level 8: $\frac{8}{2} = 4$ MUXes
• Level 9: $\frac{4}{2} = 2$ MUXes
• Level 10: $\frac{2}{2} = 1$ MUX

Total Number of MUXes:$$\text{Total} = 512 + 256 + 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 1023$$

General Formula: To implement an $N$-to-1 multiplexer using 2-to-1 multiplexers, the total number of 2-to-1 MUXes needed is always:$$\text{Required MUXes} = N – 1$$Here, $N = 2^{10} = 1024$, so $\text{Total} = 1024 – 1 = 1023$.