? 2003 by Charles C. Lin. All rights reserved.
Introduction
- In the last set of notes, we talked about a combinational logic device abstractly. Now we're going to look at a specific example of a combinational logic circuit, perhaps one of the most useful ones we'll see: the multiplexer (or MUX, for short).
The word "multiplexer" probably doesn't mean much to you. If anything, it sounds like a place where you can go watch movies. A better name for a multiplexer might be input selector.
A multiplexer picks one of several inputs and directs it to the output. We'll see this in more detail.
A 2-1 MUX
- Let's start off with a 2-1 MUX. A 2-1 MUX has two data inputs, which we'll call x1 and x0. It has one output, which we'll call z.
We want to pick either x1 or x0 and direct its value to the output.
How do well tell the MUX which input we want? We need to have control inputs.
How many control inputs are needed? We have two possible inputs, and basically the idea is to label these two choices with as few bits as possible. We've already discussed how to label N items with as few bits as possible.
The answer is: ceil( lg 2 ) = 1.
Thus, we need a single bit for a control input. We'll call this bit, c (which is short for "control").
The following chart describes the behavior of a 2-1 MUX.
When c = 0, x0 is directed to the output, z. When c = 1, x1 is directed to the output, z. Notice that we treat c as a 1-bit UB number, and that this number specifies the subscript of the input we want to direct to the output.
Diagram of 2-1 MUX
The diagram above illustrates how the 2-1 MUX behaves when c = 0 (see upper left diagram) and when c = 1 (upper right.
A 4-1 MUX
- Now we consider a 4-1 MUX. A 4-1 MUX has four data inputs, which we'll call x3, x0, x1 and x0. A 4-1 MUX still has one output, which we'll call z.
We want to pick one of x3, x0, x1 or x0 and direct its value to the output.
How many control inputs are needed? We have four possible inputs, and we want to label these fourc choices with as few bits as possible. How many bits are needed?
The answer is: ceil( lg 4 ) = 2.
We call these two bits c1..0. We're going to treat c1..0 as a 2-bit UB number. There are four possible bitstring patterns: 00, 01, 10, and 11. They correspond to the following values 0ten, 1ten, 2ten, and 3ten. In particular, these values are going to be the values of the subscripts of the data input.
For example, if c1..0 = 10, then we want to select x2 to direct to the output since the representation 10two corresponds to the value 2ten using UB representation.
The following chart describes the behavior of a 4-1 MUX.
| c1 | c0 | z |
| 0 | 0 | x0 |
| 0 | 1 | x1 |
| 1 | 0 | x2 |
| 1 | 1 | x3 |
When c1..0 = 00
, then z = x0. When c1..0 = 01, then z = x1. When c1..0 = 10, then z = x2. When c1..0 = 11, then z = x3.
Diagram of 4-1 MUX
The diagram above illustrates how the 4-1 MUX behaves when c1..0 = 00 (see upper left diagram), when c1..0 = 01 (upper right diagram), when c1..0 = 10 (lower left diagram), and when c1..0 = 11 (lower right diagram),
Notice that when you feed 10 to the control inputs, you are really feeding two bits of input to the 4-1 MUX, i.e., c1 = 1 and c0 = 0. However, for brevity we write it as c1..0 = 10.
A 3-1 MUX
- Usually MUXes are of the form 2k-1 MUX where k >= 1. That is, the number of inputs for a typical MUX is a power of 2. However, occasionally, you may wish to have number of inputs be some other choice.
What happens then? For example, supposed you want to have a 3-1 MUX. How many control bits are needed?
We use the same formula as before: ceil( lg 3 ) = 2.
lg 3 evaluates to a value that is greater than 1, but less than 2. When we take the ceiling of that value, we get 2.
With 2 controls bits, we can specify up to four different inputs. The problem? We only have three inputs. What do we do when the user tries to specify input c1..0 = 11? This would normally specify that you want z = x3, but with only 3 inputs, z = x3 doesn't exist.
The answer is simply not to care. Ideally, if a 3-1 MUX is being used in a circuit, the rest of the circuit does not set the control bits, c1..0 = 11.
However, since we can't prevent that from happening, we simply let the actual designer of the 3-1 MUX pick any value for that.
| c1 | c0 | z |
| 0 | 0 | x0 |
| 0 | 1 | x1 |
| 1 | 0 | x2 |
| 1 | 1 | don't care |
This solution of placing a don't care value for MUXes with k inputs, where k is not a power of 2, is fairly common. If you want, just set the value to x0.
A 2-bit 2-1 MUX
- Most information in a 32-bit CPU are grouped into 32 bits. Generally, you want to move 32 bits at a time. So, even a MUX is likely to choose from one of N 32-bit quantities.
The following is an implementation of a 2-bit 2-1 MUX. In this MUX, you can choose between x1..0 and y1..0 using a control bit c. You can implement this kind of MUX using 2 1-bit 2-1 MUXes. In general, you can create a k-bit m-1 MUX, using k 1-bit m-1 MUX, using a similar strategy as shown below.
As you can see there are two sets of data inputs: x1x0 (which we abbreviate as x1..0) and y1y0 (which we abbreviate as y1..0). There is one control bit since this is still a 2-1 MUX. There are two bits of output: z1..0. Inside the black box is the implementation, which include two 1-bit 2-1 MUX.
We could have called this a 4-2 MUX, but it doesn't make it nearly as clear that you have 2 choices to pick from. 2-bit 2-1 MUX indicates that there are 2 choices.
An Exercise
To see if you understand how the MUXes were constructed, try implementing a 2-bit 4-1 MUX, then a 4-bit 4-1 MUX using 1-bit 4-1 MUXes.
A 1-4 DeMUX
- If a multiplexer is an input selector that chooses from one of N inputs and directs it to the output, then a demultiplexer is an output selector which has a single input and directs it to one of N outputs.
Even though a DeMUX appears to be the opposite of a MUX (an output selector versus an input selector), surprisingly, it's not used nearly as often as MUXes. MUXes seem to find more uses than a DeMUXes.
Suppose you have a 1-4 DeMUX. You want to pick one of four possible outputs. How many control inputs do you need? Again, it's the same idea of labelling one of four items. You need ceil( lg 4 ) = 2 bits.
The following is a diagram of a 1-4 DeMUX.
Chart for 1-4 DeMUX
- This is the chart that describes the behavior of a 1-4 DeMUX.
| c1 | c0 | z 0 | z 1 | z 2 | z 3 |
| 0 | 0 | x | 0 | 0 | 0 |
| 0 | 1 | 0 | x | 0 | 0 |
| 1 | 0 | 0 | 0 | x | 0 |
| 1 | 1 | 0 | 0 | 0 | x |
As you can see, x is directed to one of the outputs. The choice of which output it is directed to is basically the same as it is for the MUX. We treat c1..0 as a 2-bit UB number, which specifies the subscript of the output we want the input to be directed to.
What happens to the remaining outputs? For example, if we decide to direct x to z2, what values should the other 3 outputs have? Our solution is to have all of the remaining outputs set to 0.
This means that a DeMUX can have, at most one output that is 1. The remaining outputs are 0. This may not always be the behavior you want, but it's easy enough to design a DeMUX such that the remaining outputs are, say, 1.
Summary
- A MUX is an input selector. It allows you to select from 1 of N inputs and direct it to the output using ceil( lg N ) control bits.
A MUX is also a combinational logic device meaning that once the input to the MUX changes, then after a small delay, the output changes. Unlike a register, a MUX does not use a clock to control it.
A MUX is very handy in a CPU because there are many occasions where you need to select one of several different inputs to some device. Usually, these MUXes are 32-bit m-1 MUX for some value of m.
A DeMUX is an output selector, letting you pick one of N outputs to direct an input to.