THE MAGAZINE FOR COMPUTER APPLICATIONS
Circuit Cellar Online offers articles illustrating creative solutions
and unique applications through complete projects, practical
tutorials, and useful design techniques.

WHAT'S YOUR ENGINEERING QUOTIENT?

Problem 1—Show that a two-input multiplexer (MUX) is a universal gate; i.e., capable of implementing any combinatorial function.

It is sufficient to note that multiplexers of any size can be built up from a basic two-input multiplexer block, and that a multiplexer with N control inputs (and 2^N data inputs) can implement any arbitrary function of those N inputs by tying the data inputs high and low in the desired pattern.

For most common functions, however, a full lookup table is rarely necessary. For example, a 2-input NAND function can be implemented as follows.

The truth table of a NAND gate is:

The direct way to implement this table with MUXes is shown below:

Any MUX that has both data inputs tied high or both tied low can be eliminated, replacing its output withe corresponding logic level. This simplifies the above circuit as shown below.

Contributor: Naveen PN

01-02 — NEXT Q&A