THE 2 TO 1 MULTIPLEXER
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. Its 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.
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: Shannons 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 Booles/Shannons 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.
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.
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.
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.
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.
Shannons 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:
Both you and the super smart professor answered the question. But the professors 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 Shannons formula to expand the Boolean function F = AB + AC + BC around the variable A.
As a treat for sitting thru the explanation, we show you the interactive circuit of F = A (B + C) + A (BC) 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 multiplexers 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, lets expand our function further. In the function F = A (B + C) + A (BC) 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.
Now that we have expanded G and H, we show the new implementation of the circuit in Figure 5.
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 = AB + AC + BC using only 2–to–1 multiplexers, we can stop.
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.