Limitations of using minimum no. of MUXes for a given boolean function

Question

Given a specific Boolean function, is there any restriction on the minimum no. of multiplexers required to implement that function? Is there any theory on that?

Answer 1

First, you have to define "multiplexer". For generality, let's assume a basic 2-way multiplexer that has 2 data inputs, a select input and a data output. But when working with SSI/MSI TTL or CMOS, you can get anything up to a 16:1 multiplexer as a building block.

There's definitely a maximum number of muxes required for any N-input function: You simply construct a 2^N-way mux that has N select inputs, and you tie each of the 2^N data inputs high or low as required. This requires 2^N-1 + 2^N-2 + ... + 2⁰ = 2^N – 1 muxes.

\begin{array}{cc} N & muxes \\ 1 & 1 \\ 2 & 3 \\ 3 & 7 \\ 4 & 15 \\ ... & ... \\ N & 2^N - 1 \end{array}

However, the minimum number of muxes for any arbitrary function of N variables very much depends on the function. There are some functions that are surprisingly efficiently implemented with 2-input muxes, especially if you allow one mux to feed the select input of another. All of the early Actel (now Microsemi) FPGA families used muxes as their basic logic element, rather than the now-ubiquitous LUT (look-up table).

For example, a 2-input AND or 2-input OR just requires one mux, so an N-way AND or N-way OR can be constructed from just N – 1 muxes. A 2-input XOR or XNOR requires just two muxes, so an N-way XOR tree (parity generator) requires just 2(N – 1) muxes.

Answer 2

The theoretical method for physically implementing a Boolean function, is by a Karnaugh map. Basically, it is a graphic / mathematical method for obtaining the canonical expression of a Boolean function from its truth table.
The canonical expression is the formula that implements the Boolean function; using Karnaugh map not ensures that the expression obtained have the minimum number of terms, but is the best method (up to four/five variables, for six or more variables there is another method, more complicated). Experience of designer helps find expression with minimal number of terms.
Why look for the minimum number of terms? The reason is that up to four variables, each term of the expression is implemented with a simple gate. Furthermore, each term of the expression obtained, can be transformed by De Morgan laws, which tends to reduce the variety of gates required. Virtually, you can implement any logical function using only NAND gates or, NOR gates.

Many times, this design method offers advantages over the implementation of the Boolean function using multiplexers.

Commercially, it is easy to find Multiplexers of two and three variables (four or eight channels), so implement Boolean functions up to three variables is very simple using multiplexers (and besides, it is recommended). From four variables, should be assessed the implementation of the Boolean function by gates, it can be more simple and economical to use multiplexers.

For example, suppose you want to implement a Boolean function of four variables. Using CMOS Technology (family 4000), requires minimally two multiplexers (eg two 4051). Also need gates to link the output of the two multiplexers and get the desired function. This last step may not be direct.

In summary, to implement a logic function of \$n\$ variables, need a multiplexer of \$2^n\$ channels. This is easy to find on the market up to 8 (\$2^3\$) channels.