Carry-Lookahead Adder
A carry-lookahead adder computes all carries in parallel from generate and propagate signals, breaking the ripple-carry bottleneck.
The Ripple Bottleneck
A ripple-carry adder is simple but slow: each bit's carry must wait for the bit below it, so the total delay grows linearly with word width. For a 64-bit add this chain is intolerable. A carry-lookahead adder (CLA) computes the carries directly from the inputs, in parallel, rather than waiting for them to ripple.
Generate and Propagate
The key is to characterize each bit position with two signals. Position i generates a carry if both its input bits are 1 (g_i = a_i AND b_i), producing a carry regardless of the incoming one. It propagates an incoming carry if at least one input bit is 1 (p_i = a_i OR b_i, or a_i XOR b_i in some formulations). From these, the carry into any position is a Boolean expression in the g and p signals below it.
- g_i = a_i AND b_i (this position makes a carry)
- p_i = a_i XOR b_i (this position passes a carry through)
- c_{i+1} = g_i OR (p_i AND c_i), expanded fully across all lower bits
Parallel Carry Computation
Expanding the carry recurrence gives each carry as a flat sum-of-products of the generate and propagate signals, which can be computed in a fixed number of gate levels rather than a growing chain. A four-bit CLA block computes all its internal carries at once. The cost is that these expressions grow quickly with width, so wide adders use CLA blocks combined hierarchically rather than one giant flat expression.
Hierarchy and Variants
Practical wide adders combine block-level generate and propagate signals to look ahead across blocks, giving logarithmic delay. Prefix adders such as the Kogge-Stone and Brent-Kung designs formalize this as a parallel-prefix computation over the (g, p) pairs, offering different trade-offs between speed, gate count, and wiring. These structures are how modern processors add wide numbers in a small number of gate delays.