Constructing Higher MUX using lower MUX

let's talk informally :

We know that   means there are 4 input lines, 2 select lines, and 1 output line. In other words, we can say that

To map 4 input lines we need 1 MUX. Why?? because there are 4 input line and only one  MUX is enough to map those lines.

So this is the idea to implement higher MUX using lower MUX.

Example:

1. Implement   using .

Solution:-

To implement        4 input lines  we need ................... 1 MUX

"       "                 1 input line we need ......................1/4 MUX

In  there are 64 input lines

To implement       64 input lines we need ..................64*(1/4)=16 MUX    //level 1

But 16 MUX will have 16 output lines, we have to map until the total output line is 1 or less than 1, again consider these 16 output lines as input lines for next level MUX

To implement       16 input lines we need ..................16*(1/4)=4 MUX   //level 2

Again  4 MUX will have 4 output lines, we have to map until the total output line is 1 or less than 1, again consider these 4  output lines as input lines for next level MUX.

To implement       4 input lines we need .................. 4*(1/4)=1 MUX     //level3

Now we can stop. Think Why??

The total number of  MUX required to construct   =

Now we will see a formula to directly calculate the number of level and MUX.