Carry-lookahead adder

A carry-lookahead adder (CLA) computes all the carry bits in parallel directly from the inputs, instead of waiting for them to ripple stage by stage. The trick is to express each carry as a flat function of the inputs by decomposing per-bit behaviour into two simpler signals — generate and propagate.

The motivation: the ripple-carry adder takes $O(n)$ gate delays for an $n$-bit add because each stage must wait for the previous stage’s carry. For wide datapaths at high clock rates, that ripple is too slow. Lookahead breaks the dependency chain and brings worst-case carry delay down to $O(\log n)$ when applied hierarchically.

Generate and propagate

For each bit position $i$ with operand bits $A_i,B_i$:

• Generate $G_i=A_i\cdot B_i$ — bit $i$ produces a carry-out regardless of carry-in (both inputs are $1$, so $A_i+B_i=10_2$ unconditionally).
• Propagate $P_i=A_i\oplus B_i$ — bit $i$ passes its carry-in through unchanged (exactly one input is $1$, so $A_i+B_i=1$ and adding any carry-in flips that to $10_2$).

These two signals capture everything about how stage $i$ contributes to the carry chain:

$C_{i+1}=G_i+P_i\cdot C_i.$

Read it as: stage $i$‘s carry-out is high if it generates a carry by itself, or if it propagates an incoming carry. The sum bit comes from the propagate signal and the carry-in:

$S_i=P_i\oplus C_i.$

(For the generate-active case where $G_i=1$, both $A_i=B_i=1$, so $P_i=0$ and the sum bit is $C_i$ — the carry, not the operand sum, is what surfaces.)

$A_i$	$B_i$	$C_i$	$G_i$	$P_i$	$C_{i+1}$	$S_i$
0	0	0	0	0	0	0
0	0	1	0	0	0	1
0	1	0	0	1	0	1
0	1	1	0	1	1	0
1	0	0	0	1	0	1
1	0	1	0	1	1	0
1	1	0	1	0	1	0
1	1	1	1	0	1	1

Flattening the carry chain

Substitute the recurrence into itself to expand each carry as a function of the inputs and the original $C_0$:

$C_1=G_0+P_0{C}_0$ $C_2=G_1+P_1{C}_1=G_1+P_1{G}_0+P_1{P}_0{C}_0$ $C_3=G_2+P_2{G}_1+P_2{P}_1{G}_0+P_2{P}_1{P}_0{C}_0$ $C_4=G_3+P_3{G}_2+P_3{P}_2{G}_1+P_3{P}_2{P}_1{G}_0+P_3{P}_2{P}_1{P}_0{C}_0$

Every carry is a single-level OR of ANDs over the inputs — independent of every other carry. With enough silicon, all four can be computed in parallel from $A_{\mathrm{0..3}},B_{\mathrm{0..3}},C_0$ in just three gate delays (XOR for $P$, AND for $G$, OR-of-ANDs for $C$). That’s constant time, not linear in the bit width — at this scale.

A 4-bit CLA combines:

• 4 full-adders (one per bit) for the sum and per-bit $G/P$.
• A carry-lookahead unit (CLU) computing $C_1,C_2,C_3,C_4$ in parallel using the flattened formulas above.

Group propagate and generate

The CLU also produces group signals that summarise the whole 4-bit block:

$P_G=P_3{P}_2{P}_1{P}_0$

— the block as a whole propagates a carry only if every stage propagates.

$G_G=G_3+P_3{G}_2+P_3{P}_2{G}_1+P_3{P}_2{P}_1{G}_0$

— the block as a whole generates a carry if any stage generates and all higher stages propagate.

These are the same recurrence applied at the next level up. Cascade four 4-bit CLAs with a higher-level lookahead carry unit (LCU) consuming their group $P_G,G_G$ and you get a 16-bit adder with carry latency proportional to ${\log }_4(16)=2$ levels. Stack again for 64 bits, 256 bits, etc.

$4^n$-bit hierarchical CLA

Generally for a $4^n$-bit CLA, four $4^{n-1}$-bit CLAs feed an LCU. The LCU computes group $P$ and $G$ from the per-block signals, applying the same recurrence at the higher level:

$P_G=P_{3\cdot 4^{n-1}}\cdot P_{2\cdot 4^{n-1}}\cdot P_{4^{n-1}}\cdot P_0$

$G_G=G_{3\cdot 4^{n-1}}+P_{3\cdot 4^{n-1}}{G}_{2\cdot 4^{n-1}}+P_{3\cdot 4^{n-1}}{P}_{2\cdot 4^{n-1}}{G}_{4^{n-1}}+P_{3\cdot 4^{n-1}}{P}_{2\cdot 4^{n-1}}{P}_{4^{n-1}}{G}_0$

The carry latency grows as ${\log }_{4}n$ — three levels for 64 bits, four for 256.

Cost

The price of $O(\log n)$ delay is more silicon. The CLU’s gate count grows superlinearly because of the wider AND gates needed for the higher-order terms. In practice, designers limit the lookahead block size (4 bits is the textbook unit; 8 occasionally) and use hierarchy for the rest.

Aspect	Ripple-carry	Carry-lookahead (hierarchical)
Worst-case carry delay	$O(n)$ stages	$O(\log n)$ levels
Gate count	$O(n)$	$O(n\log n)$ approximately
Layout	Trivially regular, neighbour wiring	Group/level structure, longer wires
Fan-in pressure	Constant per stage	Grows with block size
When to use	Low-speed, narrow operands	Wide, high-speed datapaths

Other fast-adder schemes

Carry-lookahead is the textbook example, but not the only fast adder. Brief mention:

• Carry-skip adder — splits the operand into blocks; if a block has $P_G=1$ (carries propagate through the entire block), the incoming carry “skips” past the block via a multiplexer. Simpler than full lookahead.
• Carry-select adder — computes both possible sums for each block (assuming carry-in 0 and carry-in 1), then selects the right one once the carry arrives.
• Kogge-Stone, Brent-Kung, Han-Carlson — parallel-prefix adders that organise the $G/P$ combination as a tree, optimising different points on the depth/wire/area trade-off. Modern CPU adders are usually parallel-prefix designs.

All of these reduce carry latency below the $O(n)$ of ripple, by paying with more gates and more wiring.

In context

For typical undergraduate digital logic, ripple-carry and carry-lookahead are the two canonical adders. Real CPUs use deeply optimised parallel-prefix adders, but the lookahead idea — break the carry dependency by computing $G/P$ separately and combining them in parallel — is the foundational insight all of those build on.

For the cell-level building blocks, see Half-adder and Full-adder. For the comparison adder family, see Adder.