Carry-lookahead adder, adder–subtractor and comparators

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Carry out of a full adder? from Lesson 5.1.2
• Delay of the last sum in an n-bit RCA? from Lesson 5.1.2
• A − B in 2's complement? from Lesson 1.1.2

1 · The Hook

🎣

A 64-bit ripple adder makes the last column wait for 63 carries. Can a column know its carry in advance? Yes: a column generates a carry if both its bits are 1, and passes on (propagates) an incoming carry if exactly one of them is 1. Writing that out lets every carry be computed in parallel: the carry-lookahead adder. GATE asks its equations, gate counts and delays.

2 · Predict First

🤔

In one column, A = 1 and B = 1. Does a carry come out of this column regardless of the carry coming in?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

Yes: 1 + 1 already makes a carry. This column generates a carry.

🗣️

In plain words

For each bit position compute G = AB ("I make a carry myself") and P = A ⊕ B ("I pass a carry through"). Then the carry into position i + 1 is "position i generates, or position i propagates a carry that came in". Unrolling this rule writes every carry directly in terms of the G's, P's and C₀, so all carries can be computed at the same time.

1. Generate and propagate

Gᵢ = AᵢBᵢ, Pᵢ = Aᵢ ⊕ Bᵢ, Sᵢ = Pᵢ ⊕ Cᵢ, and Cᵢ₊₁ = Gᵢ + PᵢCᵢ. Unrolled for 4 bits:

• 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₀

Cᵢ needs i AND gates (with 2, 3, …, i + 1 inputs) and one (i + 1)-input OR gate.

2. Timing (counting gate delays, any fan-in)

• P and G: 1 gate delay.
• Every carry (AND then OR): 2 more → all carries ready at 3.
• Sums Sᵢ = Pᵢ ⊕ Cᵢ: 1 more → 4 gate delays, whatever n is.

The price: gates with very many inputs for large n. Real designs use 4-bit lookahead blocks and connect the blocks. Blocks connected in a ripple: each block's carry-out comes 2 gate delays after its carry-in (P and G are already ready). 16 bits as four 4-bit blocks: C₄ at 3, C₈ at 5, C₁₂ at 7, C₁₆ at 9 gate delays; the last sum S₁₅ needs C₁₅ (ready at 9) plus 1: 10.

3. Adder–subtractor

Feed each Bᵢ through an XOR with a control line M, and connect M to C₀:

• M = 0: Bᵢ ⊕ 0 = Bᵢ, C₀ = 0 → A + B.
• M = 1: Bᵢ ⊕ 1 = Bᵢ', C₀ = 1 → A + B' + 1 = A − B.

Signed overflow V = Cₙ ⊕ Cₙ₋₁ (Lesson 1.1.2).

4. Comparators

• Equality of two n-bit numbers: E = AND of (Aᵢ ⊙ Bᵢ) over all bits.
• 2-bit magnitude: A > B ⟺ A₁B₁' + (A₁ ⊙ B₁)A₀B₀' (decide at the highest bit that differs).
• A < B similarly with the roles swapped; A = B is (A₁ ⊙ B₁)(A₀ ⊙ B₀).

4 · Visual

Carry lookahead: every carry is ready after 3 gate delays and every sum after 4, independent of the number of bits.

5 · Worked Examples

Example 1 Easy

For A₂ = 1, B₂ = 0: what are G₂ and P₂?

Solution

G₂ = 1·0 = 0, P₂ = 1 ⊕ 0 = 1 (propagates).

Example 2 Medium

How many AND gates and how many inputs does the OR gate need to produce C₄ directly in a 4-bit CLA?

Solution

4 AND gates (with 2, 3, 4 and 5 inputs) and a 5-input OR.

Example 3 GATE

An adder–subtractor has control M = 1, A = 0110 (6) and B = 0011 (3). What does it compute?

Solution

6 + 1100 + 1 = 1 0011 → result 0011 = 3 (6 − 3).

6 · GATE Traps

⚠️

• Pᵢ = Aᵢ ⊕ Bᵢ (some books use Aᵢ + Bᵢ for carries; the sum then needs the XOR form).
• CLA delay is constant (4 gate delays) only with unlimited fan-in.
• In the adder–subtractor, M feeds both the XOR gates and the carry-in.
• Rippled CLA blocks still ripple, but by blocks (2 gate delays per block).

7 · Memory Hook

🧠

"Generate = AND, propagate = XOR, carry = G + P·C. Lookahead: 1 + 2 + 1 = 4 gate delays."

8 · Connect the Dots

Chapter 5.1 is complete: circuits that do arithmetic. Chapter 5.2 covers circuits that route data: multiplexers choose one input, decoders pick one output, encoders compress.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markCarry equation

In a carry-lookahead adder, Cᵢ₊₁ equals:

• (A) GᵢCᵢ
• (B) Gᵢ + PᵢCᵢ
• (C) GᵢPᵢ + Cᵢ
• (D) Pᵢ ⊕ Cᵢ

Q2NAT1 markCLA delay

With P and G in 1 gate delay, carries in 2 more and sums in 1 more, after how many gate delays is a 32-bit carry-lookahead sum complete (unlimited fan-in)?

Numerical answer: ________

Q3NAT2 marksGate count

How many AND gates are needed to produce C₃ directly (unrolled) in a carry-lookahead adder?

Numerical answer: ________

Q4NAT2 marksRippled blocks

A 16-bit adder is four 4-bit CLA blocks connected in a ripple. P and G take 1 gate delay; a block's carry-out comes 2 gate delays after its carry-in. After how many gate delays is C₁₆ ready?

Numerical answer: ________

Q5MCQ1 markAdder–subtractor

In an adder–subtractor, the control M = 1 makes the circuit compute A − B because:

• (A) each Aᵢ is inverted
• (B) the sum bits are inverted
• (C) the carry-out is inverted
• (D) each Bᵢ is inverted by an XOR and the carry-in is 1

10 · Rule Card

• Gᵢ = AᵢBᵢ, Pᵢ = Aᵢ ⊕ Bᵢ, Cᵢ₊₁ = Gᵢ + PᵢCᵢ, Sᵢ = Pᵢ ⊕ Cᵢ.
• Unrolled Cᵢ: i AND gates + one (i + 1)-input OR. CLA delay: 1 (P, G) + 2 (carries) + 1 (sums) = 4.
• Rippled 4-bit CLA blocks: 2 gate delays per block for the carry.
• Adder–subtractor: Bᵢ ⊕ M, C₀ = M. Equality: AND of XNORs; magnitude: decide at the highest differing bit.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

generatepropagatecarry-lookahead equationsunrolled carrieslookahead gate countsconstant-time additionrippled lookahead blocksadder–subtractoroverflow detection in hardwareequality comparatormagnitude comparator

12 · Answer Vault