Implement 3-input gates using 2:1 muxes

The implementation of 3-input gates using 2:1 muxes requires two stages of multiplexing logic as there is only 1 select line for a mux. Two of the variables can form as the select, one for each stage multiplexers. And the third input can act as the input of the first stage multiplexers depending upon the function needed. In this post, we will illustrate the process building a 3-input AND gate and a 3-input OR gate using 2:1 muxes:

3-input AND gate using 2:1 muxes: As we know, a AND gate's output goes '1' when all its inputs are '1', otherwise it is '0'. The truth table for a 3-input AND gate is shown below in figure 1, where A, B and C are the three inputs and O is the output.

                                      O = A (and) B (and) C

Truth table for 3-input AND gate

If we observe carefully, when A is 0, output is '0'. And when A is 1, output depends upon combination of B and C. So, we need at least two 2:1 muxes to implement 3-input AND gate. The mux closest to output can have A connected to the select, data0 input can be connected to '0'. data1 input needs to be connected to another mux that implements sub-function of B and C.

Now, if we observe the rows with A=1, when B = 0, O = 0. And when B = 1, O = C. So, to implement the sub-function, we need to connect B to select of mux, data0 of mux should be connected to '0' and data1 should be connected to 'C'.

Figure 2 below shows the implementation of 3-input AND gate using 2:1 muxes.

3-input AND gate using 2:1 muxes

3-input OR gate using 2:1 muxes: The output of an OR gate is '0' when all the inputs are '0', otherwise it is '1'. The truth table of a 3-input OR gate is shown in figure 3 below:

Truth table for 3-input OR gate

Looking at the truth table of 3-input OR gate, we see that when A = '1', output also goes '1'. And when A is '0', output is a sub-function of B and C. Seeing at the highlighted portion, when B = 0, output is equal to C. And when B is '1', output is also '1'.

Thus, we can connect the select of output side mux to A, with D0 input connected to another mux implementing sub-function of B and C and D1 input to '1'. The select of mux implementing sub-function can be connected to B, D0 to C and D1 to '1'.

Figure 4 below shows the implementation of 3-input OR gate using 2:1 muxes:

3-input OR gate using 2:1 muxes

3-input NAND gate using 2:1 mux: A NAND gate's output is 0 when all the inputs are 1. For all other combinations of inputs, the output is 1. The truth table for a 3-input NAND gate is shown in figure below. 

O = A (nand) B (nand) C

Truth table for 3-input NAND gate

Let us choose to have a 2:1 mux decoding the value of A. So, the mux closest to output will have its select connected to A. When A = 0, output is 1. So, pin D1 needs to be connected to "1". When A is 1, output is a further function of B and C. So, we need another mux. Let us choose to have B decode the value; i.e. B at the select of mux. When B = 0 & A = 1, O = 1. When B = 1 & A = 1, O = C'. The resulting logic using 2:1 muxes for a 3-input NAND gate is shown in figure below.

3-input NAND gate using 2:1 muxes

3-input NOR gate using 2:1 muxes: A 3-input NOR gate returns 0 when all the inputs are "0", otherwise the output is 1. The truth table for a 3-input NOR gate is shown in figure below.

Truth table for 3-input NOR Gate

Let us choose A to be the select of mux closest to output. When A is "1", output is "0". So, input-1 of the mux will be connected to logic "0". When A is "0", output is further a function of B and C.

Now, looking at the rows where A is "0", let us choose B to select the logic. When B is 1, output is "0" and when B is "0", output is invert of C. Thus, input-1 of this mux will be connected to "0" and other input to C'. Below figure shows the implementation of 3-input NOR gate using 2:1 muxes.

3-input NOR gate using 2:1 muxes

3-input XOR gate using 2:1 muxes: A 3-input XOR gate returns "1" when the odd number of inputs are "1". The truth table for 3-input XOR gate is shown in figure below.

Truth table for 3-input XOR gate

Let us choose A to be the select of mux closest to output. When A is "0", output is a function of B and C. So, we need another mux, let us choose B to be the select of this mux. Among the rows with A = 0, when B is "0", output is equal to C and when B is "1", output is equal to C'.

Similarly among the rows with A = "1", when B is "0", output is equal to C' and when B is "1", output is equal to C. The implementation of 3-input XOR gate using 2:1 muxes is shown in figure below.

3-input XOR gate using 2:1 muxes

3-input XNOR gate using 2:1 muxes: An XNOR gate returns "1" when even number of inputs are "1". Truth table of XNOR gate is shown in figure below.

Truth table of 3-input XNOR gate

Let us choose A to be the select of mux closest to output. When A is "0", output is a function of B and C. So, we need another mux, let us choose B to be the select of this mux. Among the rows with A = 0, when B is "0", output is equal to C' and when B is "1", output is equal to C.

Similarly among the rows with A = "1", when B is "0", output is equal to C and when B is "1", output is equal to C'. The implementation of 3-input XNOR gate using 2:1 muxes is shown in figure below.

3-iput XNOR gate using 2:1 muxes

Also read:

• XOR gate implementation using NAND gates
• 16x1 mux using 4x1 muxes
• 2-inputs gates using 2:1 mux

How to build an XOR gate using NAND gates

We can build a 2-input XOR gate using 5 NAND gates. Sound interesting, isn't it? Let us see how.

As we know, the logical equation of a 2-input XOR gate is given as below:

                      Y = A (xor) B = (A' B    +    A B')

Let us take an approach where we consider A and A' as different variables for now (optimizations related to this, if any, will consider later). Thus, the logic equation, now, becomes:

                       Y = (CB    +    A D)           -----   (i)

     where

                      C = A'     and      D = B'

De-Morgan's law states that

                                m + n = (m'n')'

Taking this into account,

                     Y = ((CB)'(AD)')' = ((A' B)'  (A B')')'

Thus, Y is equal to ((A' nand B) nand (A nand B')). No further optimizations to the logic seem possible to this logic. Figure 1 below shows the implementation of XOR gate using 2-input NAND gates.

Figure 1: 2-input XOR gate implementation using 2-input NAND gate

Thus, we have seen an XOR gate can be implemented by putting NAND gates in cascade. Can you think of a better way of implementing XOR gate using NAND gates?


Also read:

• XOR/XNOR gate using 2:1 mux
• Latch using 2:1 mux
• 2-input gates using 2:1 mux
• VHDL code for clock divider