Adder speed: ripple-carry delay, carry-lookahead (generate, propagate), gate-delay counting

0 · Recall Warm-up

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

• How does an ALU subtract with an adder? from Lesson 2.1.1
• How many select lines for a 2ᵏ-to-1 MUX? from Lesson 0.2.3
• Which flag is cₙ₋₁ ⊕ cₙ? from Lesson 2.1.1

1 · The Hook

🎣

In a ripple-carry adder, bit 31 cannot finish until the carry has crawled through all 31 bits below it. For a 64-bit adder that crawl sets the clock speed of the whole CPU. Carry lookahead computes every carry at once, straight from the inputs. GATE asks for the delays of both, in gate delays.

2 · Predict First

🤔

A 4-bit adder: a = 1011, b = 0101. Without adding bit by bit, which bit positions are guaranteed to create a carry no matter what comes in from below? Which ones would just pass along a carry that arrives?

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

3 · Core Concept

💡

Predict First — the answer

Create (generate) where both bits are 1: aᵢbᵢ = 1 only at bit 0 (1 and 1). Pass along (propagate) where exactly one bit is 1: bits 1, 2 and 3 (aᵢ ⊕ bᵢ = 1).

Ripple-carry delay

In a ripple-carry adder, carry-in to bit i + 1 is the carry-out of bit i. Suppose each full adder needs t_c to produce its carry-out and t_s to produce its sum after its carry-in arrives. Then:

• last carry cₙ is ready after n × t_c,
• last sum bit sₙ₋₁ is ready after (n − 1) × t_c + t_s.

Delay grows linearly: Θ(n).

A full adder's carry is ab + c(a ⊕ b): with AND–OR logic, the carry passes through 2 gate delays per bit once a and b are stable. So an n-bit ripple adder needs about 2n gate delays for the final carry.

Generate and propagate

For bit i define:

• gᵢ = aᵢ · bᵢ (generate: this bit makes a carry by itself),
• pᵢ = aᵢ ⊕ bᵢ (propagate: this bit passes an incoming carry on). (Some books use aᵢ + bᵢ; both work for carries.)

Then cᵢ₊₁ = gᵢ + pᵢ · cᵢ and sᵢ = pᵢ ⊕ cᵢ.

Carry lookahead

Substitute repeatedly so every carry depends only on g's, p's and c₀:

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

Each is a sum of products: one level of AND gates, one level of OR gates. Delay of a carry-lookahead adder (CLA), counting one gate delay per gate level:

• 1 for all gᵢ, pᵢ (in parallel),
• 2 for all carries (AND then OR, in parallel),
• 1 for the sums sᵢ = pᵢ ⊕ cᵢ.

Total 4 gate delays, independent of n, if gates may have unlimited inputs (fan-in). The cost: cᵢ needs gates with up to i + 1 inputs and the number of gates grows fast.

Real CLAs: blocks and bounded fan-in

Practical adders use 4-bit CLA blocks. Chaining blocks by their carry-out (ripple between blocks) gives about 2 gate delays per block after the first g/p level. A second lookahead level over block-generate and block-propagate signals makes a tree. With gates of bounded fan-in (say 2 inputs), the lookahead tree has depth proportional to log n: CLA addition time is Θ(log n), ripple is Θ(n).

4 · Visual

Ripple (4 bits): carries crawl one stage at a time
 c0 -> [FA0] -c1-> [FA1] -c2-> [FA2] -c3-> [FA3] -> c4      last carry after 4 x tc

CLA (4 bits): all carries in parallel from g, p, c0
  level 1:  g_i = a_i b_i ,  p_i = a_i xor b_i          (1 gate delay)
  level 2-3: c1..c4 as AND-OR sums of products           (2 gate delays)
  level 4:  s_i = p_i xor c_i                            (1 gate delay)   total 4

5 · Worked Examples

Example 1 Easy

A 16-bit ripple-carry adder: each full adder produces its carry-out 2 ns after its carry-in. When is c₁₆ ready?

Solution

16 × 2 = 32 ns.

Example 2 Medium

Same adder, sum delay t_s = 3 ns after carry-in. When is the last sum bit s₁₅ ready?

Solution

(16 − 1) × 2 + 3 = 33 ns.

Example 3 GATE

A 16-bit adder is built from four 4-bit CLA blocks connected in ripple fashion. g and p take 1 gate delay; each block produces its carry-out 2 gate delays after its carry-in (g, p ready); sums take one more gate delay after a block's internal carries. When is the last sum bit ready?

Solution

c₄ at 1 + 2 = 3, c₈ at 5, c₁₂ at 7. The last block's internal carries are ready at 7 + 2 = 9; its sums at 10 gate delays (c₁₆ also at 9).

6 · GATE Traps

⚠️

• Ripple delay of the last sum is (n − 1)t_c + t_s; of the last carry, n·t_c.
• The constant-time CLA needs unlimited fan-in; with bounded fan-in it is Θ(log n).
• gᵢ = aᵢbᵢ (AND); pᵢ = aᵢ ⊕ bᵢ (or aᵢ + bᵢ).
• Blocks of CLA connected by ripple still ripple between blocks.

7 · Memory Hook

🧠

"Generate makes it, propagate passes it." c_{i+1} = gᵢ + pᵢcᵢ, unrolled into one AND–OR level.

8 · Connect the Dots

Lesson 2.1.1 built the ALU; this lesson made its adder fast. Next: multiplication by repeated shifting and adding, and Booth's trick that skips runs of 1s.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markRipple carry

A 32-bit ripple-carry adder: each full adder's carry-out is ready 3 ns after its carry-in. When is the final carry-out ready (ns)?

Numerical answer: ________

Q2NAT2 marksRipple sum

An 8-bit ripple-carry adder with t_c = 2 gate delays and t_s = 3 gate delays (after carry-in). When is s₇ ready?

Numerical answer: ________

Q3MCQ1 markAsymptotic

With gates of fan-in at most 2, the time to add two n-bit numbers with a carry-lookahead adder grows as:

• (A) Θ(1)
• (B) Θ(n)
• (C) Θ(n log n)
• (D) Θ(log n)

Q4MSQ2 marksGenerate and propagate

For aᵢ = 1, bᵢ = 1, which statements hold?

• (A) cᵢ₊₁ = 1 regardless of cᵢ
• (B) gᵢ = 1
• (C) pᵢ = aᵢ ⊕ bᵢ = 0
• (D) sᵢ = cᵢ

Q5NAT2 marksBlock CLA

A 32-bit adder uses eight 4-bit CLA blocks rippled together. g/p: 1 gate delay. Each block's carry-out is ready 2 gate delays after its carry-in. When is c₃₂ ready (gate delays)?

Numerical answer: ________

10 · Rule Card

• Ripple: last carry n·t_c; last sum (n−1)·t_c + t_s; ≈ 2 gate delays per bit for carries; Θ(n).
• gᵢ = aᵢbᵢ, pᵢ = aᵢ ⊕ bᵢ; cᵢ₊₁ = gᵢ + pᵢcᵢ; sᵢ = pᵢ ⊕ cᵢ.
• CLA (unlimited fan-in): 1 (g,p) + 2 (carries) + 1 (sum) = 4 gate delays.
• Bounded fan-in CLA: Θ(log n). Rippled CLA blocks: 2 per block after g/p.

11 · Concept Ledger

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

ripple-carry delaycarry delay t_c and sum delay t_sgenerate gᵢpropagate pᵢcarry-lookahead adder (CLA)fan-inblock CLAΘ(n) vs Θ(log n) adders

12 · Answer Vault