Adders and Carry Propagation
Follow the carry across four stages one gate delay at a time, and see exactly why lookahead exists.
Skip to the animationA full adder computes one column of a binary addition from three inputs, and chaining them makes a ripple-carry adder that is correct but whose delay grows with width — which is the entire reason carry-lookahead exists.
Half adder, then full adder
One bit plus one bit can be 0, 1 or 2, and 2 needs two output bits. The low bit is 1 when the inputs differ — XOR. The high bit is 1 only when both are 1 — AND. Two gates: a half adder.
A real column has three inputs, because it receives a carry from the column to its right. A full adder gives SUM = A ⊕ B ⊕ C_in and C_out = A·B + (A ⊕ B)·C_in, built as two half adders and an OR.
Ripple carry, and why it is slow
Chain n full adders, carry-out to carry-in. It is correct, it is the cheapest possible construction, and its cost grows linearly with width. The problem is time.
- 1Bit 0 computes immediately and produces a carry.
- 2Bits 1 to n−1 already have their A and B inputs — but cannot produce a correct sum until the carry arrives.
- 3Each stage adds another gate delay, so the carry travels rather than appearing.
- 4Worst case, the carry crosses every stage: delay proportional to n.
This is a sequential dependency, not a shortage of hardware. Every stage is present and idle. Until the carry arrives the outputs are showing wrong values, which is why the adder sets the clock period of the whole processor.
Carry-lookahead
Define two signals per stage that depend only on the inputs, so both are available immediately:
- Generate, G = A·B
- This stage produces a carry regardless of what arrives.
- Propagate, P = A ⊕ B
- This stage passes a carry through if it receives one.
Every carry can then be written as a two-level expression in the inputs — C₁ = G₀ + P₀C₀, C₂ = G₁ + P₁G₀ + P₁P₀C₀, and so on — so all of them settle together rather than in sequence. Delay becomes logarithmic in the width.
The cost is gate count and fan-in, both of which grow quickly. Real adders are hybrids: lookahead within 4-bit blocks, ripple between the blocks, or a carry-select design that computes both possibilities and picks one when the carry arrives.
Subtraction for free
Since −B = B′ + 1 in two's complement, A − B = A + B′ + 1. Feed each B bit through an XOR controlled by an add/subtract line, and route that same line into the carry-in.
One adder plus n XOR gates does both operations. This is the concrete reward for having chosen two's complement in the previous topic.
The numbers you will be asked for
- Half adder
S = A ⊕ B · C = A·B
Two gates.
- Full adder
S = A ⊕ B ⊕ C_in · C_out = A·B + (A⊕B)·C_in
Sum is odd parity; carry is majority.
- Generate and propagate
G = A·B · P = A ⊕ B
Both available at t = 0.
- Lookahead carry
C_{i+1} = Gᵢ + Pᵢ·Cᵢ
Expand recursively to remove the dependency.
- Ripple delay
t ≈ n · t_carry
Linear in width — the problem lookahead solves.
Advantages and disadvantages
Advantages
- A full adder is nine gates and handles any width by repetition.
- The same hardware does signed and unsigned arithmetic.
- Subtraction needs only n XOR gates on top.
- Lookahead reduces delay from O(n) to O(log n).
Disadvantages
- Ripple carry's delay grows linearly, which is unusable at 64 bits.
- Lookahead's gate count and fan-in grow fast, so pure lookahead does not scale either.
- During propagation the outputs are transiently wrong, so the result must be sampled after the worst-case delay.
- Overflow detection is separate logic on top of the adder.
Watch it work
Check yourself
question 1 / 4
One question at a time. Pick an answer to see why it is right or wrong, then move on — there is no score to keep and nothing is saved.