Why Ripple Carry is Slow

• In a simple adder, each bit’s CarryOut becomes the next bit’s CarryIn.
• For n bits → worst-case delay ∝ n (carry “ripples” through all bits).
• Example: 16-bit ripple adder ≈ 32 gate delays for carry
  • This is because each carry/add operation needs two sequential logic blocks (an AND level and an OR level) to check AB + Ac + Bc
  • (c being carry in value)
  • So each carry will have 2 gate delays, because there’s two sequential levels of logic, one after another

Goal of Fast Adders

• Compute high-order carries earlier so the worst-case delay grows like log₂(n) instead of n.
• Hardware works in parallel; all signals begin evaluating at once.

“Infinite Hardware” Idea

• In theory, each CarryIn could be expressed directly in terms of the two operands and the initial carry (two levels of logic).
• But equations grow exponentially with bit position → hardware cost explodes for wide adders.

First Abstraction: Propagate & Generate

• Define for each bit i:

  • gi = ai · bi (Generate) → this bit generates a carry regardless of ci.
  • pi = ai + bi (Propagate) → this bit propagates an incoming carry.

• Carry equation:

  ci+1 = gi + (pi · ci)

• Intuition:

  • gi=1 → carry out always 1 (like a valve letting water flow regardless).
  • gi=0, pi=1 → carry out = carry in (carry “domino effect”).

Example for 4 bits:

• c1 = g0 + p0·c0
• c2 = g1 + p1·g0 + p1·p0·c0