Implementing Boolean Functions with Multiplexers and Decoders

Welcome to the next lesson in our Digital Logic module. In the previous session, we built foundational arithmetic circuits like adders and comparators, seeing how simple logic gates can be combined to perform complex calculations. We also analyzed their performance, particularly the crucial concept of propagation delay.

Today, we'll shift our focus from building logic functions from scratch using individual gates to using larger, pre-designed building blocks. This lesson introduces two essential combinational logic components: multiplexers and decoders. Your goal is to master how to use these powerful components to implement any arbitrary Boolean function. This is a highly practical skill and a recurring topic in GATE, where questions often test your ability to implement logic efficiently using these standard blocks rather than just minimizing expressions with K-maps.

1. The Multiplexer: A Digital Switch

A Multiplexer, often abbreviated as MUX, is a combinational circuit that acts like a digital selector switch. It has multiple data input lines, a set of selection lines, and a single output line. The binary code applied to the selection lines determines which one of the data inputs is routed to the output.

If a multiplexer has $n$ selection lines, it can select from $2^{n}$ data input lines. This gives rise to common configurations like 2-to-1 (2:1), 4-to-1 (4:1), and 8-to-1 (8:1) multiplexers.

Multiplexer Explained | Implementation of Boolean function using Multiplexer

The video "Multiplexer Explained" from ALL ABOUT ELECTRONICS provides an excellent introduction to this concept.

First, watch the segment that defines a multiplexer and establishes the relationship between its inputs and select lines. Then, observe how the internal logic for 2:1 and 4:1 multiplexers is constructed from basic AND, OR, and NOT gates.

As you saw in the video, the output equation for a 4:1 MUX with data inputs $D_{0}, D_{1}, D_{2}, D_{3}$ and select lines $S_{1}, S_{0}$ is:
$Y = S_{1}^{'} S_{0}^{'} D_{0} + S_{1}^{'} S_{0} D_{1} + S_{1} S_{0}^{'} D_{2} + S_{1} S_{0} D_{3}$
Notice something familiar? This is a Sum-of-Products (SOP) expression. The select lines act as variables to generate the minterms ( $S_{1}^{'} S_{0}^{'}$ is minterm $m_{0}$ , $S_{1}^{'} S_{0}$ is $m_{1}$ , etc.), and the data inputs ( $D_{0}, D_{1}, ...$ ) act as switches that determine whether each minterm is included in the final sum. This property makes the multiplexer a universal logic element.

2. Implementing Boolean Functions with a Multiplexer

Let's explore the primary application tested in GATE: using a MUX to realize a Boolean function. We will cover two methods, from a straightforward but less efficient approach to a more optimized one.

Method 1: The Direct Implementation

To implement an $n$ -variable Boolean function, the most direct method is to use a $2^{n}$ -to-1 multiplexer.

The procedure is as follows:

Connect the $n$ variables of the function directly to the $n$ selection lines of the MUX.
Examine the minterm list or truth table of the function.
For each data input line $D_{i}$ on the MUX, if the corresponding minterm $m_{i}$ is present in the function, connect $D_{i}$ to logic 1 (High).
If minterm $m_{i}$ is not in the function, connect $D_{i}$ to logic 0 (Low).

Multiplexer Explained | Implementation of Boolean function using Multiplexer

The same video demonstrates this direct implementation method.

Watch the example from this section, where a 3-variable function is implemented using an 8:1 MUX. This visually clarifies how the minterms of the function map directly to the data inputs of the MUX.

For example, to implement $F (A, B, C) = \sum m (1, 3, 5, 6)$ using an 8:1 MUX:

Connect A, B, and C to select lines $S_{2}, S_{1}, S_{0}$ , respectively.
Connect data inputs $D_{1}, D_{3}, D_{5}, D_{6}$ to logic 1.
Connect the remaining data inputs ( $D_{0}, D_{2}, D_{4}, D_{7}$ ) to logic 0.

While simple, this method requires a large multiplexer that might not be available or cost-effective.

Method 2: The Efficient Implementation

A more common and efficient method, frequently seen in GATE questions, is to implement an $n$ -variable function using a smaller $2^{n - 1}$ -to-1 multiplexer.

The procedure is more nuanced:

Connect the first $n - 1$ variables of the function (e.g., A and B for a function of A, B, C) to the $n - 1$ select lines of the MUX.
The last remaining variable (e.g., C) and its complement (C'), along with logic 0 and 1, will be connected to the data input lines.
To determine what to connect to each data input, we create an implementation table. Let's use the example $F (A, B, C) = \sum m (1, 3, 5, 6)$ with a 4:1 MUX.

Minterm	A	B	C	F	Data Input for AB	Relationship between F and C
$m_{0}$	0	0	0	0	\multirow{2}{*}{ $D_{0}$ }	\multirow{2}{*}{ $F = C$ }
$m_{1}$	0	0	1	1
$m_{2}$	0	1	0	0	\multirow{2}{*}{ $D_{1}$ }	\multirow{2}{*}{ $F = C$ }
$m_{3}$	0	1	1	1
$m_{4}$	1	0	0	0	\multirow{2}{*}{ $D_{2}$ }	\multirow{2}{*}{ $F = C^{'}$ }
$m_{5}$	1	0	1	1
$m_{6}$	1	1	0	1	\multirow{2}{*}{ $D_{3}$ }	\multirow{2}{*}{ $F = C^{'}$ }
$m_{7}$	1	1	1	0

How to read the table:

For select lines AB = 00, the MUX looks at input $D_{0}$ . We see that for this combination of A and B, the function F is 0 when C=0 and 1 when C=1. Thus, F follows C. So, we connect $D_{0}$ to C.
For AB = 01, the MUX looks at $D_{1}$ . Again, F follows C. Connect $D_{1}$ to C.
For AB = 10, the MUX looks at $D_{2}$ . Here, F is 1 when C=0 and 0 when C=1. Thus, F is the complement of C. Connect $D_{2}$ to C'.
For AB = 11, the MUX looks at $D_{3}$ . Again, F is the complement of C. Connect $D_{3}$ to C'.

The final implementation uses a 4:1 MUX with $S_{1} = A, S_{0} = B$ , and data inputs $D_{0} = C, D_{1} = C, D_{2} = C^{'}, D_{3} = C^{'}$ .

Multiplexer Explained | Implementation of Boolean function using Multiplexer

This efficient method is explained in detail in the "Multiplexer Explained" video.

Pay close attention to the systematic approach demonstrated from this segment for a 3-variable function with a 4:1 MUX. Then, follow the more complex example of a 4-variable function with an 8:1 MUX to solidify your understanding.

This technique can be generalized. For instance, you could implement a 4-variable function using a 4:1 MUX ( $2^{n - 2}$ :1). This requires using two variables for selection and deriving expressions for the data inputs in terms of the other two variables, often by simplifying small K-maps.

Implementation of Boolean Function using Multiplexers

The video "Implementation of Boolean Function using Multiplexers" by Neso Academy demonstrates exactly this advanced K-map based approach.

Watch the introduction from the beginning to understand the motivation. Then, carefully follow the detailed, step-by-step example from this section, where a 4-variable function is implemented using a 4:1 MUX. Notice how they use the K-map to visually group the minterms and derive the expressions for the MUX's data inputs.

3. The Decoder: A Minterm Generator

A Decoder is another fundamental combinational circuit. It performs the inverse operation of an encoder. A decoder with $n$ input lines can generate signals on $2^{n}$ unique output lines. For any given binary input, exactly one output line is "activated".

For example, a 3-to-8 decoder with inputs A, B, C has 8 outputs, $Y_{0}$ through $Y_{7}$ . If the input is $A B C = 101$ , the output line $Y_{5}$ will be activated. The decoder is essentially a minterm generator; each output line corresponds directly to one minterm of the input variables.

resource_title
A 3-to-8 decoder's logic diagram. Each output is an AND gate that corresponds to one of the 8 possible minterms of the 3 input variables (A, B, C).

Implementing Functions with a Decoder

Since a decoder generates all the minterms, implementing a Boolean function in SOP form is incredibly simple.

The procedure is:

Use an $n$ -to- $2^{n}$ decoder for an $n$ -variable function.
Connect the function variables to the decoder's input lines.
Take an OR gate with a number of inputs equal to the number of minterms in the function.
Connect the decoder's output lines that correspond to the minterms in the function to the inputs of the OR gate.
The output of the OR gate is the function itself.

Example: To implement $F (A, B, C) = \sum m (1, 4, 7)$ using a 3-to-8 decoder:

Connect A, B, C to the decoder inputs.
Connect the decoder's outputs $Y_{1}, Y_{4}, Y_{7}$ to a 3-input OR gate.
The output of the OR gate is the function $F$ .

resource_title
Implementation of the function F(A,B,C) = Σm(1,4,7) using a 3-to-8 decoder and an OR gate. The decoder generates all minterms, and the OR gate sums the required ones.

A Note on Active-Low Outputs: In practice, many decoders have active-low outputs. This means the selected output line goes to 0, while all others remain at 1. To implement an SOP function with an active-low decoder, you would use a NAND gate instead of an OR gate. This is a direct application of De Morgan's laws: $(m_{1}^{'} \cdot m_{4}^{'} \cdot m_{7}^{'})^{'} = m_{1} + m_{4} + m_{7}$ . This is a common variation in GATE problems, so be prepared for it.

Conclusion

In this lesson, you've learned to wield two of the most versatile tools in the digital designer's toolkit. Instead of working at the gate level, you can now think at a higher level of abstraction, using standard MSI components to build complex logic.

Key Takeaways:

Multiplexers (MUX): These are data selectors that can implement any Boolean function. The key is to map the function's variables to the select lines and determine the correct signals (0, 1, a variable, or its complement) for the data inputs. The $n$ -variable to $2^{n - 1}$ :1 MUX implementation is a crucial, efficient technique.
Decoders: These are minterm generators. Implementing a function in SOP form is as straightforward as using an OR gate to combine the outputs of the decoder corresponding to the function's minterms.

So far, all circuits we have studied have been combinational—their outputs are determined solely by their present inputs. In our next lesson, we will make a significant leap into sequential logic, where circuits gain the ability to "remember" past states. We will introduce the fundamental building blocks of memory: latches and flip-flops.

Recommended resources

1. The Multiplexer: A Digital Switch

2. Implementing Boolean Functions with a Multiplexer

Method 1: The Direct Implementation

Method 2: The Efficient Implementation

3. The Decoder: A Minterm Generator

Implementing Functions with a Decoder

Conclusion