Combinational Circuits

Q: What is the difference between a half adder and a full adder?

A half adder adds two 1-bit inputs (A and B) and produces a 2-bit result: Sum = A XOR B, Carry = A AND B. It has no carry-in input. A full adder adds three 1-bit inputs (A, B, and Carry-in Cin) and produces Sum = A XOR B XOR Cin, and Carry-out Cout = (A AND B) OR (B AND Cin) OR (A AND Cin). Full adders are used in multi-bit adder chains because they can accept the carry from a previous stage.

Q: How is a multiplexer used to implement any Boolean function?

A 2^n-to-1 MUX with n select lines can implement any n-variable Boolean function by connecting the function's truth table values (0 or 1) to the data inputs D0 through D(2^n - 1). For an (n+1)-variable function, use a 2^n-to-1 MUX with n variables as select lines and the (n+1)th variable (or its complement or 0 or 1) as data inputs - this is the standard GATE technique.

Q: What is carry-lookahead and why is it faster than ripple-carry?

In a ripple-carry adder, each stage must wait for the carry from the previous stage, causing a delay that grows linearly with the number of bits (O(n)). A carry-lookahead adder (CLA) computes all carry signals in parallel using Generate (G = A AND B) and Propagate (P = A XOR B) signals. The carry for any stage can be computed directly from the original inputs in O(log n) time, making CLA significantly faster for wide adders.

Q: What is the difference between an encoder and a decoder?

An encoder converts 2^n input lines (one active at a time) into an n-bit binary code. A priority encoder handles multiple simultaneous active inputs by encoding the highest-priority one. A decoder does the reverse: it takes an n-bit binary input and activates exactly one of 2^n output lines. Decoders are commonly used for memory address decoding and implementing truth tables directly.

Adders, MUX, decoders, encoders, and comparators – the building blocks of every digital system. Master these for 1-2 marks in GATE CS with worked examples and circuit analysis.

Last updated: April 2026 | GATE CS 2024-2026 syllabus

Key Takeaways

A combinational circuit has no memory – its output at any instant depends only on its current inputs, not on past inputs.
Half adder: Sum = A ⊕ B, Carry = AB. Full adder adds carry-in: Sum = A ⊕ B ⊕ Cin, Cout = AB + BCin + ACin.
Ripple-carry adder propagates carry serially – delay grows as O(n). Carry-lookahead adder (CLA) computes all carries in parallel – delay O(log n).
A 2ⁿ-to-1 MUX with n select lines can implement any n-variable Boolean function directly from its truth table.
A decoder with n inputs activates exactly one of 2ⁿ outputs – it implements all minterms of n variables simultaneously.
Priority encoder: if multiple inputs are active, only the highest-priority input is encoded.
A 4-bit magnitude comparator compares two 4-bit numbers and produces three outputs: A>B, A=B, A<B.

1. What is a Combinational Circuit?

A combinational circuit is a digital circuit whose output depends solely on the present combination of inputs – there is no feedback, no memory, and no clock. Change the inputs and the output changes immediately (subject only to gate propagation delay).

Key property: Output = f(current inputs only). No past history matters.
Contrast with sequential circuits: Sequential circuits have memory (flip-flops) and their output depends on both current inputs and past state.

All combinational circuits can be described by a truth table and implemented with logic gates (AND, OR, NOT) or equivalently with NAND/NOR (universal gates). Standard building blocks – adders, MUX, decoders – are pre-designed and used as components.

2. Adders and Subtractors

2.1 Half Adder

Adds two 1-bit numbers A and B. Produces a 2-bit result: Sum (LSB) and Carry (MSB).

Sum = A ⊕ B (XOR gate)
Carry = A · B (AND gate)

A	B	Sum	Carry
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

Gate count: 1 XOR + 1 AND = 2 gates. The half adder has no carry-in, so it cannot be cascaded directly for multi-bit addition.

2.2 Full Adder

Adds three 1-bit inputs: A, B, and Carry-in (Cin). Used in multi-bit adder chains.

Sum = A ⊕ B ⊕ Cin
Cout = AB + BCin + ACin = AB + Cin(A ⊕ B)

A	B	Cin	Sum	Cout
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

Implementation: One full adder = two half adders + one OR gate.

2.3 Ripple-Carry Adder (RCA)

Chain n full adders to add two n-bit numbers. The carry-out of each stage feeds the carry-in of the next stage – it “ripples” from LSB to MSB.

Delay: Each full adder introduces a delay of t_FA. Total delay = n × t_FA = O(n).
Problem: Slow for large n – the MSB cannot be computed until all carries have propagated.

4-bit RCA: 4 full adders chained. C₀ = 0 (LSB carry-in). Produces S₃S₂S₁S₀ and final carry-out C₄.

2.4 Carry-Lookahead Adder (CLA)

Computes all carry signals simultaneously using Generate and Propagate functions:

Generate: G_i = A_i · B_i (this stage generates a carry regardless of Cin)
Propagate: P_i = A_i ⊕ B_i (this stage propagates a carry-in to carry-out)

C_i+1 = G_i + P_i · C_i

Expanding for 4-bit CLA:
C₁ = G₀ + P₀C₀
C₂ = G₁ + P₁G₀ + P₁P₀C₀
C₃ = G₂ + P₂G₁ + P₂P₁G₀ + P₂P₁P₀C₀
C₄ = G₃ + P₃G₂ + P₃P₂G₁ + P₃P₂P₁G₀ + P₃P₂P₁P₀C₀

All C_i are computed in parallel from the original inputs, giving O(log n) delay.

Feature	Ripple-Carry Adder	Carry-Lookahead Adder
Carry propagation	Serial (ripple)	Parallel (simultaneous)
Delay	O(n)	O(log n)
Gate count	Low	Higher
Use case	Low-speed, area-constrained	High-speed arithmetic units

2.5 Subtractor and 2’s Complement Subtraction

A full adder can perform subtraction using 2’s complement: A – B = A + (~B + 1).

Adder-Subtractor Circuit: Use an XOR gate on each B_i with a control signal M.
• M = 0: XOR passes B unchanged → performs A + B (addition)
• M = 1: XOR inverts B → performs A + B' + 1 = A – B (subtraction, with M also fed to C₀)

This single circuit performs both addition and subtraction, controlled by one bit – the basis of every ALU.

3. Multiplexer (MUX)

A MUX (data selector) selects one of 2ⁿ input data lines and routes it to a single output, based on n select (address) lines.

2-to-1 MUX: Y = S'D₀ + SD₁
4-to-1 MUX: Y = S₁'S₀'D₀ + S₁'S₀D₁ + S₁S₀'D₂ + S₁S₀D₃

MUX as Universal Logic Element

A 2ⁿ-to-1 MUX can implement any n-variable Boolean function:

Connect the n input variables to the select lines.
Connect each data input D_i to the function value f at minterm i (either 0 or 1).

GATE technique – (n+1)-variable function with 2ⁿ-to-1 MUX:

Use n variables as select lines.
For each of the 2ⁿ input combinations of the select variables, examine the truth table rows for both values of the (n+1)th variable (call it X).
Connect D_i to: 0, 1, X, or X' depending on f when X=0 and X=1 for that select combination.

MUX Implementation Table (4-to-1 MUX for 3-variable function)

S1 S0	f when C=0	f when C=1	Connect D_i to
0 0	0	0	0
0 1	1	1	1
1 0	0	1	C
1 1	1	0	C'

4. Demultiplexer (DEMUX)

A DEMUX routes a single input to one of 2ⁿ output lines, selected by n address lines. It is the functional inverse of a MUX.

1-to-4 DEMUX:
Y₀ = D · S₁' · S₀'
Y₁ = D · S₁' · S₀
Y₂ = D · S₁ · S₀'
Y₃ = D · S₁ · S₀

When D = 1 (enabled), only the selected output is 1. When D = 0, all outputs are 0. DEMUX is commonly used to distribute a single data stream to multiple destinations.

5. Encoder and Priority Encoder

Encoder

An encoder converts 2ⁿ input lines (exactly one active at a time) into an n-bit binary code. Example: 8-to-3 encoder (octal to binary).

8-to-3 Encoder outputs (active-high inputs):
A₂ = D₄ + D₅ + D₆ + D₇
A₁ = D₂ + D₃ + D₆ + D₇
A₀ = D₁ + D₃ + D₅ + D₇

Limitation: Basic encoder fails if two inputs are active simultaneously – the output is incorrect (OR of two codes).

Priority Encoder

Handles multiple simultaneous active inputs by encoding the highest-priority input and ignoring the rest. Also has a Valid output V to indicate whether any input is active.

D3	D2	D1	D0	A1	A0	V
0	0	0	0	X	X	0
0	0	0	1	0	0	1
0	0	1	X	0	1	1
0	1	X	X	1	0	1
1	X	X	X	1	1	1

D3 has the highest priority. X = dont-care (any value).

6. Decoder

A decoder takes an n-bit binary input and activates exactly one of 2ⁿ output lines – the one corresponding to the binary value of the input.

2-to-4 Decoder (active-high outputs):
D₀ = A₁' A₀' (minterm 0)
D₁ = A₁' A₀    (minterm 1)
D₂ = A₁ A₀'    (minterm 2)
D₃ = A₁ A₀     (minterm 3)

Key insight: A decoder generates all minterms of n variables simultaneously. Any Boolean function of n variables can be implemented using a decoder + OR gate: simply OR together the minterms where the function is 1.

Enable input: Most practical decoders have an enable (EN) input. When EN = 0, all outputs are 0 (or 1 for active-low decoders). This allows multiple decoders to be cascaded for larger address spaces.

Cascading: Two 2-to-4 decoders + one additional input = one 3-to-8 decoder. The additional input selects which decoder is enabled.

7. Magnitude Comparator

Compares two n-bit unsigned numbers A and B and produces three outputs: A>B, A=B, A<B.

1-bit Comparator

(A = B) = A ⊕ B ' = XNOR(A, B)
(A > B) = A · B'
(A < B) = A' · B

4-bit Comparator (74HC85 style)

For A = A₃A₂A₁A₀ and B = B₃B₂B₁B₀:

Compare MSBs first: if A₃ ≠ B₃, the result is determined.
If A₃ = B₃, compare A₂ vs B₂, and so on down to LSB.
If all bits are equal, A = B.

(A = B) = (A₃ XNOR B₃) · (A₂ XNOR B₂) · (A₁ XNOR B₁) · (A₀ XNOR B₀)

Cascading comparators: the 4-bit comparator IC has cascade inputs (I_A>B, I_A=B, I_A<B) that allow chaining for 8-bit, 16-bit, etc. comparison.

8. GATE CS Solved Examples

Example 1 – MUX Implementation (GATE CS 2020)

Question: Implement F(A, B, C) = Σm(1, 2, 6, 7) using a 4-to-1 MUX with A, B as select lines and C as a possible data input.

Solution:

A (S1)	B (S0)	f when C=0 (minterm)	f when C=1 (minterm)	D_i
0	0	f(0,0,0) = m0 = 0	f(0,0,1) = m1 = 1	C
0	1	f(0,1,0) = m2 = 1	f(0,1,1) = m3 = 0	C'
1	0	f(1,0,0) = m4 = 0	f(1,0,1) = m5 = 0	0
1	1	f(1,1,0) = m6 = 1	f(1,1,1) = m7 = 1	1

Answer: D₀ = C, D₁ = C', D₂ = 0, D₃ = 1

Example 2 – Ripple Carry Adder Delay (GATE CS 2016)

Question: A ripple-carry adder is implemented for n=16 bits. Each full adder has a carry propagation delay of 10 ns and a sum output delay of 15 ns. What is the total worst-case delay for the 16-bit sum?

Solution: The critical path is through all carry stages plus the final sum.

Carry must ripple through 15 stages before the MSB full adder: 15 × 10 ns = 150 ns
MSB sum output: +15 ns
Total = 150 + 15 = 165 ns

Answer: 165 ns worst-case delay.

Example 3 – Decoder as Logic Implementer (GATE CS 2017)

Question: Implement F(A, B, C) = Σm(0, 3, 5, 6) using a 3-to-8 decoder and minimum OR gates.

Solution: A 3-to-8 decoder generates all 8 minterms m0 through m7. Simply OR together the minterms where F = 1:

F = m₀ + m₃ + m₅ + m₆
Connect outputs D₀, D₃, D₅, D₆ of the decoder to a 4-input OR gate.

This requires exactly one 4-input OR gate – the decoder provides all minterms for free.

9. Common Mistakes

Mistake 1 – Confusing half adder and full adder limitations

Error: Using a half adder for intermediate stages of a multi-bit adder.
Root cause: Forgetting that intermediate stages must accept a carry-in from the previous stage.
Fix: Only the LSB stage can use a half adder (Cin = 0). All other stages need full adders with Cin connected to the previous Cout.

Mistake 2 – Wrong MUX data input assignment

Error: When implementing an (n+1)-variable function with a 2ⁿ-to-1 MUX, incorrectly determining what to connect to each data input.
Root cause: Not systematically going through each select combination and checking f for both values of the remaining variable.
Fix: Build the table: for each row of select inputs, note f when the extra variable = 0 and f when it = 1. Then assign: (0,0)→0; (1,1)→1; (0,1)→X; (1,0)→X'.

Mistake 3 – Confusing encoder and decoder direction

Error: Calling the circuit that converts binary to one-hot a “encoder” instead of “decoder.”
Root cause: The naming is counterintuitive.
Fix: Decoder: n-bit binary IN → 2ⁿ-line one-hot OUT. Encoder: 2ⁿ-line one-hot IN → n-bit binary OUT. Memory tip: decoder decodes an address into a specific location.

Mistake 4 – Forgetting the enable input in decoder cascading

Error: Not connecting the enable input when cascading decoders, causing all outputs to be simultaneously active.
Root cause: Overlooking the EN pin in circuit diagrams.
Fix: When building a 3-to-8 decoder from two 2-to-4 decoders, use the MSB of the address to enable exactly one decoder at a time: MSB=0 enables decoder 0; MSB=1 enables decoder 1.

Mistake 5 – Incorrect carry-lookahead formula expansion

Error: Stopping the CLA expansion at C_i+1 = G_i + P_iC_i without substituting previous C_i expressions – this still creates a dependency chain.
Root cause: Not fully unrolling the recurrence.
Fix: Fully substitute each C_i back until all expressions are in terms of G₀, P₀, G₁, P₁, … and the original C₀ only. Only then are all carries truly parallel.

10. Frequently Asked Questions

What is the difference between a half adder and a full adder?

A half adder adds two 1-bit inputs (A and B) producing Sum = A ⊕ B and Carry = AB. It has no carry-in. A full adder adds three 1-bit inputs (A, B, Cin) producing Sum = A ⊕ B ⊕ Cin and Cout = AB + BCin + ACin. Full adders are chained for multi-bit addition because each stage needs the carry from the previous stage.

How is a multiplexer used to implement any Boolean function?

A 2ⁿ-to-1 MUX with n select lines directly implements any n-variable Boolean function: connect each data input D_i to the function value at minterm i (0 or 1). For an (n+1)-variable function with a 2ⁿ-to-1 MUX, use n variables as selects and map the (n+1)th variable as 0, 1, X, or X' to each data input based on the truth table.

What is carry-lookahead and why is it faster than ripple-carry?

Ripple-carry adders compute carries serially (O(n) delay). Carry-lookahead adders compute all carries in parallel using Generate (G_i = A_iB_i) and Propagate (P_i = A_i ⊕ B_i) signals, achieving O(log n) delay. The trade-off is more gates (higher area) for faster speed.

What is the difference between an encoder and a decoder?

A decoder takes n-bit binary input and activates one of 2ⁿ output lines. An encoder takes 2ⁿ one-hot inputs (one active at a time) and produces an n-bit binary code. A priority encoder handles multiple simultaneous active inputs by encoding the highest-priority one and providing a Valid output signal.

Combinational Circuits – Digital Logic | GATE CS