Day 19: Combinational design II: adders — half, full, ripple vs carry-lookahead
Building arithmetic from gates
A half adder adds two bits: sum = A ⊕ B, carry = A · B. A full adder adds three (two bits plus a carry-in): sum = A ⊕ B ⊕ Cin, Cout = A·B + Cin·(A ⊕ B). Chain n full adders, carry-out to carry-in, and you have an n-bit ripple-carry adder — simple, compact, and the natural first ALU core.
The ripple problem, and carry-lookahead
The catch: each bit's sum waits for the carry to *ripple* up from the bit below, so a ripple-carry adder's delay grows linearly with width. Carry-lookahead breaks the chain by computing carries in parallel from generate G = A·B and propagate P = A ⊕ B signals — a bit generates a carry, or propagates an incoming one. It costs more gates but makes delay grow roughly logarithmically: the classic area-vs-speed trade.
Adder delay vs width: ripple-carry grows linearly; carry-lookahead grows ~logarithmically (illustrative).
This is a real ChipX decision
ChipX's ALU (Stage 2) needs a 32-bit adder. Ripple-carry is trivial to write but may blow your timing budget; a lookahead or prefix adder closes timing at the cost of area. You'll make exactly this trade — and 'compute a 32-bit add's critical path' is a staple interview question.
Key terms
- Half adder
- Adds two bits: sum = A ⊕ B, carry = A · B.
- Full adder
- Adds two bits plus a carry-in, producing sum and carry-out.
- Ripple-carry adder
- Full adders chained by carry; simple but delay grows linearly with width.
- Generate / propagate
- G = A·B (this bit makes a carry), P = A ⊕ B (it passes an incoming carry) — the basis of lookahead.
- Carry-lookahead adder
- Computes carries in parallel from G/P for ~logarithmic delay at higher area cost.
Before moving on, you should be able to
Why does a carry-lookahead adder outperform a ripple-carry adder for wide operands?
