Previous
Next
Constructing Higher MUX using Lower MUX derivation of formula

To construct a {\color{Red} M\times 1} using {\color{Red} N\times 1} 

 

no. of levels (K) =     \left \lceil log _{n}^{m}\right \rceil

and Total number of MUX needed(n)=   {\color{Red} \sum_{p=1}^{k}\left \lceil M/N^{p} \right \rceil}  

Prove:- 

Example:

1. Construct 32\times 1 using 2\times 1

Solution:

Total number of levels= \left \lceil log_{2}^{32} \right \rceil = 5

Total number of MUX= \left \lceil 32/2^{1} \right \rceil +\left \lceil 32/2^2 \right \rceil+\left \lceil 32/2^3 \right \rceil +\left \lceil 32/2^4 \right \rceil+\left \lceil 32/2^5 \right \rceil

                                            = 16+8+4+2+1=31

 

Contributor's Info

Created:
0Comment
+1
0
-1
Constructing Higher MUX using lower MUX

let's talk informally :

We know that  4\ast 1 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 4\ast 1 MUX is enough to map those lines.

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

Example:

1. Implement  64\times 1 using 4\times 1.

Solution:-

let's talk about  4\times 1 first

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

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

In 64\times 1 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 4\times 1 MUX required to construct 64\times 1  = 16+4+1=21

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

Contributor's Info

Created:
0Comment
+1
0
-1