Minimal multiplexer realization of logic functions

It is well known that any n-variable logic function can be realized by a multiplexer (selector) with no additional external logic. Thus multiplexers have come to be known as universal logic modules. This approach to logic function realization requires the use of a 2ⁿ-input multiplexer with constant data inputs, or a 2^n-1-input multiplexer whose data inputs are constants and single-variable functions; that is, each input is 0, 1, x, or x´ for some variable x. The paper deals with conditions and algorithms for realizing some logic functions using smaller multiplexers. More precisely, a computationally simple condition is formulated to determine whether a given n-variable logic function is realizable by a multiplexer having 2^n-2 or fewer inputs, and an algorithm is presented for finding the smallest subset of variables, containing n-2 or fewer members, to be used as control inputs in a minimal multiplexer realization. Once the control inputs are known, the data input functions can be readily computed.