# Multiplexers and Demultiplexers

### Multiplexers

As we construct a CPU, one very useful combinational logic circuit is a multiplexer.

A n-1 multiplixer, or MUX, for short, is a device that allows you to pick one of n inputs and direct it to an output.

Many devices are essentially multiplexers. Think about a remote control for a TV. You select one channel, and that one channel is displayed on your screen. Similarly, you select a radio station to listen to, and it plays on your radio.

An n-1 MUX consists of the following:

• Data inputs: n
• Control inputs: ceil( log2 n )
• Outputs: 1

where ceil is the ceiling function ( ceil(x) = n for the smallest integer where n >= x).

Given n possible choices for inputs, you need log2 n bits to select it (technically, you need the ceiling of this, just in case n is not a power of 2).

For example, if you have 16 possible inputs, you need 4 bits to specify one of 16 values. If you have, say, 12 possible inputs, you still need 4 bits, even though some of the 4 bit patterns may not correspond to any of the 12 choices.

### Diagram of 2-1 MUX

Here is a black box circuit for a 2-1 MUX.

### Behavior of 2-1 MUX

Here's the behavior of the 2-1 MUX, abstractly.

If c == 0, then x0 is directed to the output z. If c == 1, then x1 is directed to the output z.

### Truth Table for 2-1 MUX

The truth table expresses the functionality of a 2-1 MUX.

 Row c x1 x0 z 0 0 0 0 0 1 0 0 1 1 2 0 1 0 0 3 0 1 1 1 4 1 0 0 0 5 1 0 1 0 6 1 1 0 1 7 1 1 1 1

The first four rows have c == 0, so they select column x0. The second four rows have c == 1, so they select column x1.

### Condensed Truth Table for 2-1 MUX

The truth table for a 2-1 MUX is not as clear as it could be. Furthermore, it has many rows (8 in total).

We can shrink the number of rows by creating a condensed truth table which modifies truth tables in the following way:

• Use only control bits for the inputs of the truth table.
• Allow data input variables to appear in the output of the truth table.

 Row c z 0 0 x0 1 1 x1

We think of the control bit as a 1 bit number. Thus, c == 0 or c == 1. The control bit selects the input with the same value as the control bit. Thus, when c == 0, we select x0 (notice the subscript has the same value as the control bit). When c == 1, we select x1 (again, the subscript has the same value as the control bit).

### Boolean Expression for 2-1 MUX

We can modify the rules for creating a Boolean expression for a condensed truth table.

• Locate all the rows with a non-zero value as output.
• Create a modified minterm for that row, by ANDing the minterm for the row, with the non-zero value (which may be a variable).
• OR the modified minterms together.

Let's apply this rule. In the truth table above, both rows have a non-zero output. Row 0 has output x0, and row 1 has output x1.

We create a modified minterm for each row:

• Row 0: \cx0
• Row 1: cx1

The minterm for row 0 is normally \c, but we AND that with the output x0 to get \cx0.

Then, we OR the two modified minterms to get the output:

```  z = \cx0 + cx1
```

This is not the same result you would get if you were simply doing sum of products on the non-condensed truth table.

However, I think this version is easier to understand. Remember the one fact about minterms. Given a specific set of values, at most one minterm is true. Thus, either \c == 1 (equivalently, c == 0) or c == 1. When one minterm is 1, the other minterms are 0.

Thus, when c == 0, we get:

```  z = \cx0 + cx1
= 1 x0 + 0 x1
= x0
```

When c == 1, we get:

```  z = \cx0 + cx1
= 0 x0 + 1 x1
= x1
```

So, you can see that we select one of x0 or x1 and zero out the other term.

### Condensed Truth Table for 4-1 MUX

To see if you understand condensed truth tables, let's consider a 4-1 MUX. This MUX has the following attributes:

• Data inputs: 4 (x3, x2 x1, x0)
• Control inputs: 2 (c1, c0)
• Outputs: 1 (z)

This time, we think of c1c0 as a 2 bit number. When c1c0 = 00, we select x0 (since 002 is 0 in base 10). When c1c0 = 01, we select x1 (since 012 is 1 in base 10). When c1c0 = 10, we select x2 (since 102 is 2 in base 10). When c1c0 = 11, we select x3 (since 112 is 3 in base 10).

Here's the condensed truth table.

 Row c1 c0 z 0 0 0 x0 1 0 1 x1 2 1 0 x2 3 1 1 x3

Again, create a modified minterm for each row with a non-zero output.

• Row 0: \c1\c0x0
• Row 1: \c1c0x1
• Row 2: c1\c0x2
• Row 3: c1c0x3

The Boolean expression for a 4-1 MUX is:

```  z = \c1\c0x0 + \c1c0x1 + c1\c0x2 + c1c0x3
```

### Constructing a 2-1 2-bit MUX from 2-1 1 bit MUXes

Suppose you want to have a MUX where you select 2 bits at a time, instead of 1 bit. For example, you might want to select either x1x0 or y1y0.

Since you're only selecting one of two inputs, you use only one control bit, even though each input is more than one bit.

• Data inputs: 4 (x1, x0 y1, y0)
• Control inputs: 1 (c)
• Outputs: 2 (z1, x0)

Here's a diagram for how to do this.

The left MUX is used to select either x1 or y1, while the right MUX is used to select either x0 or y0.

In order to understand this circuit more fully, you may wish to "trace" to see what happens to the inputs when c == 0 and when c == 1.

### Constructing 4-1 MUXes out of 2-1 MUXes

While you can build 4-1 MUXes from gates, it's an interesting exercise to build it from smaller MUXes. In reality, building MUXes in this way is probably a reasonably good idea. However, it is also fun as an intellectual puzzle, because it helps you to understand how to construct larger parts from smaller ones.

Here's the diagram.

This diagram is a little complicated to understand. Here's the idea. If c0 == 0, then the two bit number c1c0 is even (since even numbers in binary end in 0). If c0 == 1, then the two bit number c1c0 is odd (since odd numbers in binary end in 1).

The top two MUXes have their control input hooked up to c0. This either picks x0 and x2 if c0 == 0 (it picks the inputs with even indexes). Or it picks x1 and x3 if c0 == 1 (it picks the inputs with odd indexes).

The bottom MUX then uses c1 to determine whether it should pick the larger of x1 and x3 or whether it should pick the larger of x0 and x2.

This is a circuit that you should try to trace through all four possible values of c1c0 to see what is happening. Again, realize the upper two MUXes select even or odd indexes, and the bottom MUX selects the index greater than or equal to 2, or indexes less than 2.

To see if you really understand this, try implementing the circuit where c1 must be hooked to the top two MUXes while c0 is hooked to the bottom. Determine how the inputs must change to accomodate this.

Also, implement an 8-1 MUX out of 2-1 MUXes.

While we won't implement the 5-1 MUX, try to think about how you might do this. First, we can characterize the MUX, with respect to data and control inputs, and outputs:
• Data inputs: 4 (x4, x3 x2, x1, x0)
• Control inputs: 3 (c2, c1, c0)
• Outputs: 1 (z).

Notice that we have 3 control bits. That's because ceil( log2 5 ) = 3. However, with 3 bits, we can specify 8 possible inputs. We only have 5. What do we do with the other 3?

One reasonable answer is not to care. That is, as long as the control inputs have values 000, 001, 010, 011, and 100 and it produces the correct output for those inputs, then that's all that matters. The MUX can produce incorrect output for 101, 110, and 111 since those values are undefined.

As an exercise, build this circuit using only 2-1 MUXes and 4-1 MUXes. Trace your result to see that it works properly.

### Demultiplexers

Demultiplexers (or DeMUX for short) are basically multiplexers where the inputs and outputs have been switched.

An 1-n DeMUX consists of the following:

• Data inputs: 1
• Control inputs: ceil( log2 n )
• Outputs: n

In a MUX you have one of n inputs to choose from and direct to an output. In a DeMUX, you have a single input, but one of n outputs to choose from to direct the input.

Think of a DeMUX like a mailroom. You have many pieces of letters coming in, and you must distribute each letter to one of many different mail boxes.

Even though DeMUXes act like the opposite of MUXes, MUXes seem much more useful than DeMUXes.

### Behavior of 1-2 DeMUX

Here's a visual diagram of a 1-2 DeMUX.

When c == 0, the input, x, is directed to the output z0. When c == 1, the input, x, is directed to the output z1. Just as before, we think of c as a 1 bit number, which specifies the output we want to direct the input to.

### Condensed Truth Table for 1-2 DeMUX

Although we can describe a 1-2 DeMUX using 4 rows (since we have one data input and one control input), we can use a condensed truth table, and only use two rows.

As before, the condensed truth table only uses control bits for the input portions of the truth table, and allows data input variables to appear in the outputs.

 Row c z0 z1 0 0 x 0 1 1 0 x

We can write a Boolean expression for z1 and z0. The rules for creating Boolean expressions for condensed truth tables are the same as before:

• Create a modified minterm for all non-zero rows. This involves creating a minterm, then ANDing it with the data input variable.
• OR all the modified minterms.

This is fairly easy, because each output variable only has one non-zero row.

Thus,

```  z1 = c x
z0 = \c x
```

### Problems to Consider

Almost every problem you can do with a MUX, you can do with a DeMUX. Here's a brief list for you to try out:

• Write the condensed truth table for a 1-4 DeMUX.
• Design a 2-bit 1-2 DeMUX.
• Design a 1-4 DeMUX using 1-2 DeMUX only
• Design a 1-5 DeMUX using 1-2 DeMUX and 1-4 DeMUX only. State any assumptions.

### Summary

Other than circuits to do arithmetic, MUXes are perhaps the most important combinational logic circuit that you need to know. A MUX allows you to select from one of N inputs, using ceil( lg N ) control bits.

DeMUXes are less important, but still useful. They are essentially MUXes where the data inputs are switched with the outputs. As with a MUX, a 1 to N DeMUX uses ceil( lg N ) control bits.