Multiplexers and demultiplexers

Why it exists

A multiplexer (MUX) is a digital switch: it passes one of several data inputs to a single output, and the select lines say which. It is the circuit behind register-file reads, ALU result selection and bus sharing. It is also a universal building block: any Boolean function can be implemented by a multiplexer, which GATE tests with questions of the form "implement this function with a 4:1 multiplexer and what are the data inputs", "how many 2:1 multiplexers are needed for a 16:1", or "which function does this multiplexer circuit compute". The demultiplexer does the reverse: it routes one input to one of several outputs.

Prerequisites

You need the design flow from combinational design and minterm numbering from SOP, POS, minterms and maxterms.

Precise definitions

Multiplexer ($2^n$-to-1 MUX). It has $2^n$ data inputs $I_0, \dots, I_{2^n - 1}$, $n$ select lines $S_{n-1} \dots S_0$ and one output $Y$. The output is the data input whose index is the binary number on the select lines:

$Y = \sum_{i=0}^{2^n - 1} m_i(S)\, I_i .$

Here $m_i(S)$ is the minterm of the select variables. For the 2:1 and 4:1 cases:

$Y_{2:1} = S' I_0 + S I_1,\qquad Y_{4:1} = S_1'S_0' I_0 + S_1'S_0 I_1 + S_1S_0' I_2 + S_1S_0 I_3 .$

A multiplexer often has an enable input $E$: when $E = 0$ the output is 0 (or off); $Y = E \cdot \sum m_i I_i$.

Building larger multiplexers. A tree of smaller multiplexers works: the first level uses the low select bits and the next level uses the higher ones. The number of multiplexers needed to build a $2^k$-to-1 multiplexer from 2-to-1 multiplexers is $2^k - 1$ (a binary tree with $2^k$ leaves). In general, build the first level with $\lceil N / s \rceil$ multiplexers of size $s$ and repeat on their outputs. For example a 16:1 multiplexer needs 15 of size 2:1, or $4 + 1 = 5$ of size 4:1; a 64:1 needs 21 of size 4:1.

Implementing a function with a multiplexer.

• Direct method. An $n$-variable function uses a $2^n$-to-1 multiplexer with the variables on the select lines. Each data input is tied to the function's output (0 or 1) for that row of the truth table.
• Shannon expansion method (one variable less). Use a $2^{n-1}$-to-1 multiplexer: connect $n - 1$ of the variables to the select lines. For each select combination, the function is a function of the remaining variable $x$ alone, which is one of $0$, $1$, $x$ or $x'$. Connect that to the data input. So any $n$-variable function needs a $2^{n-1}$-to-1 multiplexer and at most one inverter.
• Repeating the Shannon expansion on more variables reduces the multiplexer size further, at the cost of more gates on the data inputs.

Universality. With the constants 0 and 1 available, a 2:1 multiplexer is functionally complete: NOT: $I_0 = 1$, $I_1 = 0$, select $A$; AND: $I_0 = 0$, $I_1 = B$, select $A$; OR: $I_0 = B$, $I_1 = 1$, select $A$.

Demultiplexer (1-to-$2^n$ DEMUX). One data input $D$, $n$ select lines and $2^n$ outputs. The output selected by the select lines carries $D$ and all the others are 0: $Y_i = D \cdot m_i(S)$. A demultiplexer is exactly a decoder with $D$ used as its enable input, which is why the two are sold as one part (decoders and encoders).

How it works

Implement $F(A, B, C) = \sum m(1, 2, 6, 7)$ with a 4:1 multiplexer. Put $A$ and $B$ on the select lines $S_1$ and $S_0$. Group the truth table rows by $(A, B)$:

The animation fills the table row by row. The columns are the function, the four data inputs as functions of $C$, and the multiplexer output $Y$ (choose the data input selected by $A B$); the function and the output are compared.

Worked examples

#include <stdio.h>
 
static int mux4(int s1, int s0, int i0, int i1, int i2, int i3) {
    int in[4] = { i0, i1, i2, i3 };
    return in[2 * s1 + s0];
}
 
int main(void) {
    int bad = 0;
    printf("A B C | F  Y\n");
    for (int m = 0; m < 8; m++) {
        int a = (m >> 2) & 1, b = (m >> 1) & 1, c = m & 1;
        int f = m == 1 || m == 2 || m == 6 || m == 7;
        int y = mux4(a, b, c, !c, 0, 1);
        printf("%d %d %d | %d  %d\n", a, b, c, f, y);
        bad += f != y;
    }
    printf("mismatches: %d\n", bad);
    int cmp = 0;
    for (int s = 0; s < 2; s++) {
        cmp += (s ? 0 : 1) != !s;                   /* NOT: I0 = 1, I1 = 0 */
        for (int b = 0; b < 2; b++) {
            cmp += (s ? b : 0) != (s && b);         /* AND: I0 = 0, I1 = b */
            cmp += (s ? 1 : b) != (s || b);         /* OR:  I0 = b, I1 = 1 */
        }
    }
    printf("2:1 mux with constants as AND, OR, NOT mismatches: %d\n", cmp);
    int two_to_one = 0, left = 16;
    while (left > 1) {
        two_to_one += left / 2;
        left /= 2;
    }
    printf("16:1 from 2:1 muxes: %d\n", two_to_one);
    int four_to_one = 0;
    left = 16;
    while (left > 1) {
        four_to_one += left / 4;
        left /= 4;
    }
    printf("16:1 from 4:1 muxes: %d\n", four_to_one);
    return 0;
}

A B C | F  Y
0 0 0 | 0  0
0 0 1 | 1  1
0 1 0 | 1  1
0 1 1 | 0  0
1 0 0 | 0  0
1 0 1 | 0  0
1 1 0 | 1  1
1 1 1 | 1  1
mismatches: 0
2:1 mux with constants as AND, OR, NOT mismatches: 0
16:1 from 2:1 muxes: 15
16:1 from 4:1 muxes: 5

Cheat box

Traps and GATE patterns

Connections

A decoder produces the minterms and a multiplexer selects among them, so the two are duals in use; a demultiplexer is a decoder with an enable. Multiplexers implement every function of SOP and POS forms, and their completeness is a case of functional completeness. A table of outputs stored in memory is the same idea in bulk: see ROM and PLA. In the processor the multiplexers choose the ALU input or the register to write (ALU design).

PYQs

Consider the digital circuit shown below with two
input lines A and B, two select lines S0 and S1, and
an output line Y. The blocks Q and M represent an
active-high 2:4 decoder and a 4-to-1 multiplexer,
respectively.
Out
of
16
possible
input
combinations, the number of combinations that
produce Y = 1 is __________. (Answer in integer).

A Boolean digital circuit is composed using two 4-
input multiplexers (M1 and M2) and one 2-input
multiplexer (M3) as shown in the figure. X0-X7 are
the inputs of the multiplexers M1 and M2 and could
be connected to either 0 or 1. The select lines of the
multiplexers are connected to Boolean variables A, B
and C as shown.

Which one of the following set of values of (X0, X1,
X2, X3, X4, X5, X6, X7) will realise the Boolean
function A'+ A'⋅C' + A⋅ B'⋅C?

Consider a digital display system (DDS) shown in the
figure that displays the contents of register X. A 16-
bit code word is used to load a word in X, either from
S or from R. S is a 1024-word memory segment and
R is a 32-word register file. Based on the value of
mode bit M, T selects an input word to load in X. P
and Q interface with the corresponding bits in the
code word to choose the addressed word. Which one
of the following represents the functionality of P, Q,
and T?

DIGITAL LOGIC

Which one of the following circuits implements the
Boolean function given below? f (x, y, z) = m0 +
m1 + m3 + m4 + m5 + m6, where mi is the ith min-
term.

A multiplexer is placed between a group of 32
registers and an accumulator to regulate data
movement such that at any given point in time the
content of only one register will move to the
accumulator. The minimum number of select lines
needed for the multiplexer is _____.

Consider the 4-to-1 multiplexer with two select
lines S1 and S0 given below

The minimal sum of products form of the output X
is

Consider the following combinational function
block involving four Boolean variables x, y, a, b
where x, a, b are inputs and y is the output.

f(x,y,a,b)

{

if(x is 1)y =a;

else y=b;

}

Which one of the following digital logic blocks is
the most suitable for implementing this function?

The Boolean expression of the output of the
multiplexer shown below is

Consider the circuit below. Which one of the
following options correctly represents f(x,y,z)

Consider a digital logic circuit consisting of three 2-
to-1 multiplexers M1, M2, and M3 as shown
below. X1 and X2 are inputs of M1. X3 and X4 are

DIGITAL LOGIC
inputs of M2. A, B, and C are select lines
of M1, M2, and M3, respectively.

For an instance of inputs X1= 1, X2= 1, X3= 0,
and X4= 0, the number of combinations
of A, B, C that give the output Y= 1 is
____________.

Self-check

Revision card

References