

THE 2 TO 1 MULTIPLEXER

S  F 

0  D0 
1  D1 
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.
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 
S  DATA  F  

A  B  F  
0  0  1  
0  1  1  
1  0  1  
1  1  0 
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’ 
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.
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 
S  D  F  

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

0  B’ 
1  A’ 
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.
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•F_{A} + A’•F_{A’}  the Shannon formula.  
Aside: F_{A} means F evaluated at A = 1, and F_{A’} means F evaluated at A = 0. Hence both F_{A} and F_{A’} 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.
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 F_{A’} is wired into the 2–to–1 multiplexer thru the data line that is active when A = 0, and the cofactor F_{A} 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 = BG_{B} + B’G_{B’} H = BH_{B} + B’H_{B’} 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) ) 
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.
For a bit of foretaste, here are two 4–to–1 multiplexers. The second one, Figure 8, implements a two input NAND gate.