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( log₂ 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 log₂ 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 x₀ is directed to the output z. If c == 1, then x₁ 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	x₁	x₀	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 x₀. The second four rows have c == 1, so they select column x₁.

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	x₀
1	1	x₁

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 x₀ (notice the subscript has the same value as the control bit). When c == 1, we select x₁ (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 x₀, and row 1 has output x₁.

We create a modified minterm for each row:

Row 0: \cx₀
Row 1: cx₁

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

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

  z = \cx₀ + cx₁

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 = \cx₀ + cx₁
    = 1 x₀ + 0 x₁
    = x₀

When c == 1, we get:

  z = \cx₀ + cx₁
    = 0 x₀ + 1 x₁
    = x₁

So, you can see that we select one of x₀ or x₁ 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 (x₃, x₂ x₁, x₀)
Control inputs: 2 (c₁, c₀)
Outputs: 1 (z)

This time, we think of c₁c₀ as a 2 bit number. When c₁c₀ = 00, we select x₀ (since 00₂ is 0 in base 10). When c₁c₀ = 01, we select x₁ (since 01₂ is 1 in base 10). When c₁c₀ = 10, we select x₂ (since 10₂ is 2 in base 10). When c₁c₀ = 11, we select x₃ (since 11₂ is 3 in base 10).

Here's the condensed truth table.

Row	c₁	c₀	z
0	0	0	x₀
1	0	1	x₁
2	1	0	x₂
3	1	1	x₃

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

Row 0: \c₁\c₀x₀
Row 1: \c₁c₀x₁
Row 2: c₁\c₀x₂
Row 3: c₁c₀x₃

The Boolean expression for a 4-1 MUX is:

  z = \c₁\c₀x₀ + \c₁c₀x₁ + c₁\c₀x₂ + c₁c₀x₃

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 x₁x₀ or y₁y₀.

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 (x₁, x₀ y₁, y₀)
Control inputs: 1 (c)
Outputs: 2 (z₁, x₀)

Here's a diagram for how to do this.

The left MUX is used to select either x₁ or y₁, while the right MUX is used to select either x₀ or y₀.

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 c₀ == 0, then the two bit number c₁c₀ is even (since even numbers in binary end in 0). If c₀ == 1, then the two bit number c₁c₀ is odd (since odd numbers in binary end in 1).

The top two MUXes have their control input hooked up to c₀. This either picks x₀ and x₂ if c₀ == 0 (it picks the inputs with even indexes). Or it picks x₁ and x₃ if c₀ == 1 (it picks the inputs with odd indexes).

The bottom MUX then uses c₁ to determine whether it should pick the larger of x₁ and x₃ or whether it should pick the larger of x₀ and x₂.

This is a circuit that you should try to trace through all four possible values of c₁c₀ 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 c₁ must be hooked to the top two MUXes while c₀ 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.

Thinking about 5-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 (x₄, x₃ x₂, x₁, x₀)
Control inputs: 3 (c₂, c₁, c₀)
Outputs: 1 (z).

Notice that we have 3 control bits. That's because ceil( log₂ 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( log₂ 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 z₀. When c == 1, the input, x, is directed to the output z₁. 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	z₀	z₁
0	0	x	0
1	1	0	x

We can write a Boolean expression for z₁ and z₀. 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,

  z₁ = c x
  z₀ = \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.

Web Accessibility