Multiplexers, Decoders and Adders

MSI combinational blocks — multiplexers, decoders, encoders and adders — are reusable design primitives frequently exploited in GATE EC to implement arbitrary functions (1–2 marks).

Key results

• MUX: 2ⁿ inputs, n select lines, 1 output = selected input. A 2ⁿ:1 MUX can realize any n-variable function (or n+1 variables with one input feeding data).
• Decoder: n inputs → 2ⁿ outputs (one active); each output is a minterm → decoders + OR gates realize SOP.
• Encoder: 2ⁿ inputs → n outputs; priority encoder resolves multiple active inputs.
• Half adder: S = A⊕B, C = A·B. Full adder: S = A⊕B⊕C_in, C_out = AB + C_in(A⊕B).
• Ripple-carry adder is slow (carry propagates); carry-look-ahead is faster.

Block	Inputs	Outputs	Function realized
2ⁿ:1 MUX	2ⁿ data + n select	1	any n-var function
n:2ⁿ decoder	n	2ⁿ (minterms)	SOP with OR gates
Full adder	A,B,C_in	S, C_out	1-bit add

Exam Tricks & Tips

• 🎯 A 2ⁿ:1 MUX implements any function of n select variables — connect minterm values (0/1) to data inputs.
• 🎯 With one variable fed to data inputs, a 2ⁿ:1 MUX covers an (n+1)-variable function (variable-entered mapping).
• 🎯 Decoder outputs are minterms; OR the needed ones to build any SOP function.
• 🎯 Full adder: SUM = A⊕B⊕C_in, CARRY = majority(A,B,C_in) = AB+BC_in+AC_in.
• 🎯 Carry-look-ahead removes the ripple delay by computing carries in parallel (G = AB, P = A⊕B).
• ❌ Common mistake: mixing up MUX (many→one, select) and DEMUX/decoder (one→many, distribute).

Expected exam pattern

1–2 marks: implement a function with a MUX/decoder, count required MUX size, or compute adder sum/carry / propagation delay.

Quick recap

2ⁿ:1 MUX realizes any n-var function (n+1 with variable-entered). Decoder outputs = minterms → OR for SOP. Full adder: S=A⊕B⊕C_in, C=AB+C_in(A⊕B). Carry-look-ahead beats ripple-carry on speed.

Cover the answer, recall, then check. 11 cards on MUX, decoders and adders for GATE EC.

Q1. How many select lines does a 2ⁿ:1 multiplexer need?
A1. n select lines for 2ⁿ data inputs.

Q2. How many variables can a 2ⁿ:1 MUX implement?
A2. Any function of n variables directly; up to n+1 variables using variable-entered inputs.

Q3. What does an n-to-2ⁿ decoder output?
A3. 2ⁿ outputs, exactly one active at a time — each output equals a minterm.

Q4. How do you realize a SOP function with a decoder?
A4. OR together the decoder outputs corresponding to the function's minterms.

Q5. Write the half-adder equations.
A5. Sum = A ⊕ B; Carry = A·B.

Q6. Write the full-adder equations.
A6. Sum = A ⊕ B ⊕ C_in; Carry = AB + C_in(A ⊕ B) = AB + BC_in + AC_in.

Q7. What does a priority encoder do?
A7. Encodes the highest-priority active input when several inputs are asserted simultaneously.

Q8. Why is a ripple-carry adder slow?
A8. Each stage's carry must propagate to the next, so delay grows linearly with the number of bits.

Q9. How does carry-look-ahead speed up addition?
A9. It computes all carries in parallel from generate G = AB and propagate P = A ⊕ B signals.

Q10. Difference between a MUX and a demultiplexer?
A10. A MUX selects one of many inputs to a single output; a DEMUX routes one input to one of many outputs.

Q11. The carry of a full adder is what function of its three inputs?
A11. The majority function of A, B, and C_in.

Multiplexers, decoders, and adders are the standard combinational building blocks — and GATE loves them because a MUX or decoder can implement any Boolean function, turning a logic question into a data-routing puzzle. Knowing their structure and the "MUX as universal function generator" trick is worth guaranteed marks.

Core concept: A MUX selects one of many inputs onto a single output; a decoder activates one output line per input code; adders sum binary numbers. All can realise arbitrary logic functions.

The theory

Beginner — the blocks

• Multiplexer (MUX): 2ⁿ data inputs, n select lines, one output = the selected input. A 4:1 MUX has 2 select lines.
• Demultiplexer / Decoder: routes one input to one of 2ⁿ outputs / activates one of 2ⁿ output lines for each n-bit code. An n-to-2ⁿ decoder outputs the minterms of its inputs.
• Encoder: the reverse — 2ⁿ inputs to n-bit code; a priority encoder resolves multiple active inputs by rank.

Intermediate — functions from MUX and decoder

• Decoder as function generator: since each output is a minterm, OR the required minterm outputs to realise any SOP function. An n-to-2ⁿ decoder + OR gate implements any n-variable function.
• MUX as function generator: a 2ⁿ:1 MUX implements any n-variable function by tying data inputs to 0/1 (minterm values). Even better, a 2^(n−1):1 MUX handles an n-variable function by connecting the last variable (or its complement, 0, or 1) to each data input — halving the MUX size.

Advanced — adders

• Half adder: Sum = A XOR B, Carry = A·B.
• Full adder: Sum = A XOR B XOR Cin, Cout = AB + Cin(A XOR B). Built from two half adders + OR.
• Ripple-carry adder: cascade full adders; carry propagates → delay grows linearly with bits (slow).
• Carry look-ahead adder: computes carries in parallel from generate Gi = AiBi and propagate Pi = Ai XOR Bi, so delay is nearly constant — the standard fast adder. A subtractor uses 2's-complement (add the inverted operand with Cin = 1).

Worked example

Implement F(A,B,C) = Σm(1,2,4,7) using an 8:1 MUX and, more cleverly, a 4:1 MUX.
8:1 MUX: select = ABC; tie data lines I1, I2, I4, I7 = 1, the rest = 0. Done directly.
4:1 MUX (select = AB), express F in terms of C for each AB:

• AB=00: minterm 1 (C=1) → I0 = C.
• AB=01: minterm 2 (C=0) → I1 = C'.
• AB=10: minterm 4 (C=0) → I2 = C'.
• AB=11: minterm 7 (C=1) → I3 = C.
  So a 4:1 MUX with inputs {C, C', C', C} realises F — half the size.

GATE relevance

1–2 mark NAT/MCQ: implement a function with a MUX/decoder (including the reduced-MUX trick), MUX/decoder cascading, priority encoder output, and full-adder/carry look-ahead logic and delay. The "function using a smaller MUX" problem is a recurring favourite.

Exam tricks and shortcuts

• 2ⁿ:1 MUX implements any n-variable function; 2^(n−1):1 MUX also can, using one variable at the data inputs.
• Decoder outputs are minterms → OR them for any SOP.
• Full adder: Sum = A⊕B⊕Cin, Cout = AB + Cin(A⊕B).
• Ripple = slow (linear delay); carry-look-ahead = fast (parallel carries).
• Mnemonic: "MUX selects, Decoder activates."

Key formulas

• MUX: 2ⁿ inputs, n select lines → 1 output; realises any function of n+1 variables.
• Decoder: n inputs → 2ⁿ outputs (one active).
• Half adder: S = A ⊕ B, C = AB.
• Full adder: S = A ⊕ B ⊕ C_in; C_out = AB + C_in(A ⊕ B).
• Ripple-carry delay ∝ n; carry-look-ahead reduces it.

MUX/decoder blocks build combinational logic; adders chain full adders (ripple or look-ahead carry).

Worked Example

Problem: Realize the function F(A, B, C) = Σm(1, 2, 4, 7) using a single 8-to-1 multiplexer with A, B, C as the select lines. Identify the standard logic function this represents.

Solution:
An 8:1 MUX with select inputs S₂S₁S₀ = A B C routes data input D_i to the output when the select code equals i. So the output equals the minterm list directly: set D_i = 1 for each minterm present, and D_i = 0 otherwise.

Given minterms {1, 2, 4, 7}, assign:
D₁ = D₂ = D₄ = D₇ = 1,
D₀ = D₃ = D₅ = D₆ = 0.

Wire these constants to the eight data inputs and connect A, B, C to the select lines — the MUX now outputs F for every input combination.

Recognise the pattern: the selected minterms {1(001), 2(010), 4(100), 7(111)} are exactly the input combinations with an odd number of 1s. That is the 3-input odd-parity function:
F = A ⊕ B ⊕ C.

This is precisely the SUM output of a full adder (sum = A ⊕ B ⊕ C_in), so the same MUX also implements a full-adder sum bit.

Answer: Set D₁ = D₂ = D₄ = D₇ = 1 and the rest to 0; the function is F = A ⊕ B ⊕ C (3-bit odd parity / full-adder sum).