Data Multiplexors - CS 61C Course Notes

1Learning Outcomes¶

Draw an n-bit wide, k-to-1 mux circuit.
Explain how the mux uses its control signal to select its output from a set of data inputs.

🎥 Lecture Video

Last time we saw how to represent and design combinational logic blocks. In this section we will study a few special logic blocks; data multiplexors, a adder/subtractor circuit, and an arithmetic/logic unit.

2The Mux¶

A data multiplexor, commonly called a mux or a selector, is a circuit that selects its output value from a set of input values. Below are two mux circuits.

"TODO" — Figure 1:A 1-bit wide, 2-to-1 MUX.

Both of these muxes have two data inputs and one output. Additionally, each mux has a special control signal labeled s, for select. The s signal is also input, but it is used to control which of the two input values is directed to the output.

Figure 1 shows a 1-bit wide, 2-to-1 mux circuit:

2-to-1 because it takes two data inputs a and b and outputs one of them.
It is 1-bit wide because all data signals (a and b) are 1-bit in width.
Notice, however, that the s signal is a single bit wide. This is because it must choose between the 2 inputs.

Figure 2 shows an n-bit wide, 2-to-1 mux circuit:

2-to-1 because it takes two data inputs A and B and outputs one of them.
It is 1-bit wide because all data signals (A and B) are 1-bit in width.
The s signal is still a single bit wide because it must choose between the 2 inputs.

The function of, say, the 1-bit wide 2-to-1 mux can be described with two rules:

\texttt{y} = \begin{cases} \texttt{a} & \text{when } \texttt{s} = 0 \\ \texttt{b} & \text{when } \texttt{s} = 1 \\ \end{cases}

To remind us of which value of s corresponds to which input, within the mux symbol we commonly label each input with its corresponding s value.

Show Answer

4 input signals
32 bits wide
2 selector bits

Muxes find common use within the design of microprocessors, e.g., those that implement RISC-V.

3MUX: Implementation¶

In most applications, you will have access to a mux; you will not need to build your own from scratch. Nevertheless, it is good to remember that like all combinational logic blocks, the function of muxes can be described using a truth table and thereby implemented as a logic gate circuit.

Click to show the gate diagrams of two muxes: a 1-bit wide, 2-to-1 mux, and a 1-bit wide, 4-to-1 mux.


::::{note} Show Truth Table
:class: dropdown

:::{table} Truth table for the 1-bit 2-to-1 mux in @fig-mux-2. Note that because there are three 1-bit inputs (`a`, `b`, and control `s`), the truth table has $3^2 = 8$ rows.
:label: tab-mux-2

| s | ab | y |
| :--: | :--: | :--: |
| 0 | 00 | 0 |
| 0 | 01 | 0 |
| 0 | 10 | 1 |
| 0 | 11 | 1 |
| 1 | 00 | 0 |
| 1 | 00 | 0 |
| 1 | 01 | 1 |
| 1 | 10 | 0 |
| 1 | 11 | 1 |
:::

::::

::::{note} Show Boolean Algebra Explanation
:class: dropdown

To come up with the logic equation and the associated gate-level circuit diagram we can apply
the technique that we studied [last chapter](#sec-boolean-algebra). We write the sum-of-products canonical form and simplify through algebraic manipulation:

```{math}
\begin{aligned}
     c 
     &= \overline{s} a \overline{b} + \overline{s} a b + s \overline{a} b + sab && \text{Sum of Products} \\
     &= \overline{s} (a \overline{b} + ab) + s (\overline{a} b + ab) && \text{Distributive Property} \\
     &= \overline{s} (a (\overline{b} + b)) + s ((\overline{a} + a) b) && \text{Distributive Property} \\
     &= \overline{s} (a \cdot 1) + s (1 \cdot b) && \text{Inverse (OR)} \\
     &= \overline{s} a + sb && \text{Identity (AND)} \\
\end{aligned}
```

Intuitively this result makes sense; When the control input, `s`, is a `0`, the expression on the right-hand side of the expression reduces to `a`, and when it is a `1`, the expression reduces to `b`.
::::

### 1-bit wide 4-to-1 mux

Often times we find the need to extend the number of data inputs of a multiplexor. For instance consider a 4-to-1 multiplexor in @fig-mux-4-bits:

:::{figure} images/mux-4-bits.png
:label: fig-mux-4-bits
:width: 55%
:alt: "TODO"

A 1-bit wide 4-to-1 MUX.
:::

@fig-mux-4-block shows how this larger mux can be formed by wiring together smaller MUXes.

:::{figure} images/mux-4-block.png
:label: fig-mux-4-block
:width: 60%
:alt: "TODO"

4-to-1 multiplexor (MUX) circuit diagram.
:::

This circuit design leverages the hierarchical nature of multiplexing. The first layer of muxes uses the $s_0$ input to narrow the four inputs down to two, then the second layer uses $s_1$ to choose the final output.

::::{note} Show Boolean Algebra Approach
:class: dropdown

```{math}
\texttt{e} = 
\begin{cases}
\texttt{a} & \text{when } \texttt{S} = 00 \\
\texttt{b} & \text{when } \texttt{S} = 01 \\
\texttt{c} & \text{when } \texttt{S} = 10 \\
\texttt{d} & \text{when } \texttt{S} = 11 \\
\end{cases}
```

An alternate approach could start by enumerating the truth-
table—in this case the function has 4 single bit data inputs and one 2-bit wide control input, for a total of 6 single bit inputs. The truth table would have 26, or 64 rows. Certainly, a feasible approach. If we were to do this, we would end up with the following logic equation:

$$e = \overline{s_1 s_0} a
     + \overline{s_1} s_0 b
     + s_1 \overline{s_0} c
     + s_1 s_0 d$$

::::