We are looking for beta users for our New mobile app Prefies (pref-ies).
To participate, please go to prefies.com and use access code “Teahlab”.
This is a pre-release sneak-peak for Teahlab users only!
Puzz! Turn your photo into a puzzle!
Get Puzz! in Google Play

THE 2 TO 1 MULTIPLEXER
by Isai Damier

2 to 1 multiplexer interactive digital logic circuit built with AND, OR, NOT gates.

Introduction

A two–to–one multiplexer is a combinational circuit that uses one control switch (S) to connect one of two input data lines (D1 or D0) to a single output (F). Only one of the input data lines can be aligned to the output of the multiplexer at any given time. It’s like sharing ice–cream on a date with one spoon. At any given instant your hand is either feeding you or your partner with the spoon — but not both mouths at the same time (Unless you have some creative ideas for sharing ice–cream on a date).

Figure 1 below shows the block diagram symbol of the two–to–one multiplexer. The wedged shape is supposed to depict how the circuit funnels one of two inputs to a single output. We also show the truth table of the 2x1 mux in Table 1. The table shows how the selector switch controls which input line feeds the output. When S = 0, F = D0; when S =1, F = D1.

2 to 1 mux block diagram: interactive digital logic circuit.
Figure 1:2X1 Mux Block Diagram


S F
0 D0
1 D1

Table 1: 2x1 mux truth table

The 4–bit parallel–access shift register illustrates a straight forward application of the 2x1 mux. In that application the 2x1 mux allows a register to operate in two possible modes: parallel or serial. When the selector switch is zero (S=0) the register is in serial mode; when the switch is one (S=1) the register is in parallel mode.

A more interesting finding about the 2x1 mux is that you can use it to split any large Boolean function into two smaller parts. The implications of this discovery establish the universality of the 2x1 mux. For a bit of history, this discovery about the 2x1 mux is credited to the same guy who discovered that Boolean algebra can be implemented with electrical circuitry: Claude Shannon. And as you might guess the discovery bears his name: Shannon’s Expansion Theorem. It has been argued, however, that George Boole made the observation years before Shannon.

However it may be. Instead of boring you with a mathematical proof of Boole’s/Shannon’s expansion, we will build circuits instead. Circuits that prove the theorem is true. First we will build a NAND gate and a NOR gate using the 2x1 mux. Since the NAND gate and the NOR gate are both universal, implementing them with the 2x1 mux proves by construction the universality of the multiplexer. Afterwards, we will use the Shannon/Boole identity to split circuits using 2x1 multiplexers.

The two input NAND gate

We start by building the truth table of the NAND gate in Table 2. Then to implement the two input NAND gate with the 2x1 mux, we follow a simple procedure. First, assign the more significant input bit in the truth table to the selector switch (i.e. S = A). Second, treat the less significant bit of the NAND gate as the source of the data to the multiplexer. Table 3 shows what we mean.

A B F
0 0 1
0 1 1
1 0 1
1 1 0

Table 2: NAND gate truth table

S DATA F
A B F
0 0 1
0 1 1
1 0 1
1 1 0

Table 3: NAND mapped to multiplexer

By Table 3 we can see that when A = 0, then F = 1 no matter what B is. And when A = 1, then F = B’. If we set S = A and D = B, we can rewrite our observation in terms of S and D: when S = 0, then F =1 no matter what D is; when S =1, then F = D’.

In Table 4 we recast the information from Table 3 in multiplexer form.

A F
0 1
1 B’

Table 4: NAND in mux table form


At this point we simply take the 2x1 mux in Figure 1 and re–label it with A and B instead of S and D. We show our result in Figure 2.

NAND gate built with universal two to one multiplexer using Shannon's expansion identity.
Figure 2: Mux implementation of NAND gate

The two input NOR gate

We implement the NOR gate similarly to how we did the NAND gate. We start with the NOR gate truth table, Table 5, and from there we map the table to the 2x1 mux: S = A, D = B. We show the mapping in Table 6. Next we observe the relationship between the data inputs and the output F: when S = 0, then F = D’; when S = 1, then F = 0 regardless of the value of D. Restating our observation in terms of A and B, we get the following: when A = 0, then F = B’; when A = 1, then F = 0. In Table 7 we rewrite the information from Table 6 in a more condensed form.

A B F
0 0 1
0 1 0
1 0 0
1 1 0

Table 5: NOR gate truth table

S D F
A B F
0 0 1
0 1 0
1 0 0
1 1 0

Table 6: NOR mapped to multiplexer

A F
0 B’
1 A’

Table 7: NOR in mux table form

At this point we just take the block diagram in Figure 1 and re–label it to implement the NOR function. We show the new circuit in Figure 3.

NOR gate built with universal two to one muX using Shannon's expansion formula.
Figure 3: Mux implementation of NOR gate

Shannon’s Expansion Theorem

We start this section with a little elementary algebra joke. If I told you to expand the function f = (w + x) (y + z) around the variables w and x, you would readily write f = w(y+z) + x(y+z). If I asked a super smart college professor, here is what I would get:

f(w,x,y,z) = (w + x) (y + z) the function being considered
f(w,x,y,z) = f|x=0 + f|w=0 the specific expansion formula
f = (w + 0) (y + z) + (0 + x) (y + z) after applying the formula to the function
f = w(y + z) + x(y + z) the final result.

Both you and the super smart professor answered the question. But the professor’s response is more rigorous. For instance the professor specifically tells me that f is the sum of two cofactors: one cofactor is when x = 0, f|x=0; one cofactor is when w = 0, f|w=0.

Now that we have had a laugh at the expense of a super smart professor, I need you to put up with me for a few seconds as I show you a rigorous example that uses Shannon’s formula to expand the Boolean function F = A•B + A•C + B•C around the variable A.

F(A,B,C) = A•B + A•C + B•C the function being considered.
F = A•FA + A’•FA’ the Shannon formula.
Aside: FA means F evaluated at A = 1, and FA’ means F evaluated at A = 0. Hence both FA and FA’ are cofactors of F.
F = A• (1•B+1•C+B•C) + A’• (0•B+0•C+B•C) after applying the formula to the function
F = A• (B + C + B•C) + A’• (0 + 0 + B•C) intermediate simplification.
F = A• (B + C) + A’• (B•C) the final result.


As a treat for sitting thru the explanation, we show you the interactive circuit of F = A• (B + C) + A’• (B•C) in Figure 4.

Majority function built with universal 2x1 multiplexer using Shannon's expansion theorem
Figure 4: circuit for F = A• (B + C) + A’• (B•C)

The circuit in Figure 4 shows some very important details about the Shannon expansion. First, the variable around which the Boolean function is expanded (i.e. signal A) becomes the multiplexer’s selection variable. Second, the cofactor FA’ is wired into the 2–to–1 multiplexer thru the data line that is active when A = 0, and the cofactor FA is wired thru the data line that is active when A = 1.

This is it. At this point you know all you needed to know about the Shannon formula. However, just for kicks, let’s expand our function further. In the function F = A• (B + C) + A’• (B•C) we are going to let G = B + C and we are going to let H = BC. We will expand both G and H so that each of them gets its own 2–to–1 multiplexer.

G = B + C H = BC The expression to be expanded
G = BGB + B’GB’ H = BHB + B’HB’ The formula
G = B(1 + C ) + B’( 0 + C) H = B( 1C ) + B’( 0C ) After expansion
G = B( 1 ) + B’( C ) H = B( C ) + B’( 0 ) After simplification

Now that we have expanded G and H, we show the new implementation of the circuit in Figure 5.

F = AG + A’H
F = A( B (1) + B’(C) ) + A’( B(C) + B’(0) )

Majority function built with three universal 2 to 1 mux using Shannon's expansion identity.
Figure 5: majority function with only 2x1 mux

Again, the H signal come in thru the data line activated under A = 0; the G signal come in thru the data line activated under A = 1. And the pattern repeats for the two other 2–to–1 multiplexers. Figure 6 below shows the general schematic. Now that we have implemented the function F = A•B + A•C + B•C using only 2–to–1 multiplexers, we can stop.

image of 2x1 mux with function labels Figure 6: General expansion schematic

For a bit of foretaste, here are two 4–to–1 multiplexers. The second one, Figure 8, implements a two input NAND gate.

4 to 1 mux built with universal 2*1 multiplexer using Shannon's expansion formula.
Figure 7: A 4–to–1 mux


NAND gate built with universal 2 to 1 mux using Shannon's expansion identity.
Figure 8: A two input NAND gate