MUX-based functions

Table of contents

1. Mathematical formulation of the Multiplexer
2. Shannon theorem with MUX
3. Interactive MUX based logic gates
4. References

Mathematical formulation of the Multiplexer

An MUX of order $p$, $M(p)$ is formulated as:

$ \begin{equation}F(\underbrace{x_1,\ldots,x_p}_{\text{inputs}}, \underbrace{y_0,\ldots,y_k}_{\text{control}})= \sum_{i=0}^{2^p-1}\underbrace{\left(\dot{x_1}\dot{x_2}\cdots\dot{x_p}\right)_i}_{i^{th}\text{ Miniterm of }F}\cdot y_i \end{equation}$

where $k=2^p-1$ and $\dot{x_j} \in \{x_j, \overline{x_j}\}$

More examples can be found in [1] (Section on Data Selectors).

Shannon theorem with MUX

Shannon decomposition theorem can also be implemented using MUXs:

$ f(x_1,x_2,x_3,\ldots, x_n) = x_1 \cdot f_1(1,x_2,x_3,\ldots,x_n) + \overline{x_1} \cdot f_0(0,x_2,x_3,\ldots,x_n) $

See [2] for a more general description.

Interactive MUX based logic gates

The set $\{M(1),0,1\}$ is functionally complete (See section Functionally Complete *Operation Sets in [3] or Wikipedia:Functional completeness). Therefore, any logic function can be implemented using multiplexers, check the interactive circuit below, which implements the basic logic gates using MUXs:

• MUX-based AND gate
• MUX-based OR gate
• MUX-based NAND gate
• MUX-based NOR gate
• MUX-based NOT gate

References

• [1]Z. Kohavi and N. K. Jha, Switching and Finite Automata Theory. Cambridge University Press, 2010 [Online]. Available at: https://books.google.cl/books?id=jZIxam8Rb9AC
• [2]Cerny, Mange, and Sanchez, “Synthesis of Minimal Binary Decision Trees,” IEEE Transactions on Computers, vol. C-28, no. 7, pp. 472–482, 1979, doi: 10.1109/TC.1979.1675391.
• [3]B. J. LaMeres, Introduction to Logic Circuits & Logic Design with Verilog. Springer International Publishing, 2019 [Online]. Available at: https://books.google.cl/books?id=1OORDwAAQBAJ

1. Can one MUX block be said an universal logic block ?
   1. Yes
      • No
2. Can one DEMUX block be said an universal logic block ?
   1. Yes
      • No
3. Select the MUX-based gates which is/are possible ?
   • MUX-based XOR gate
   • MUX-based XNOR gate
     1. XOR and XNOR both gates

---