Carry-lookahead adders

Q: What are generate and propagate in a carry-lookahead adder?

Generate g_i = a_i AND b_i means a bit column makes a carry on its own (only 1 + 1 does). Propagate p_i = a_i OR b_i means the column would pass an incoming carry on up (true whenever at least one bit is 1). Together they give the carry recurrence c_(i+1) = g_i + p_i · c_i, which unrolls into a flat function of the inputs.

Computing every carry at once

13 min read

A carry-lookahead adder speeds up addition by computing all of the carries in parallel directly from the input bits, using per-bit generate and propagate terms, instead of waiting for each carry to ripple up one bit at a time.

Builds onAdding 8-bit numbers Full adder

The 8-bit ripple-carry adder is correct and simple: eight full adders in a row, each one's carry-out wired into the next one's carry-in. The catch is speed. The top sum bit cannot settle until the carry has walked all the way up from the bottom, one stage at a time. This lesson keeps the exact same sum but computes the carries a different way, in parallel, so a wide adder stops being slow.

Why ripple-carry is slow

Each stage of a ripple adder needs its carry-in before it can produce its carry-out, and that carry-in comes from the stage below. So the carry travels like a row of falling dominoes: stage 0 must finish before stage 1 can, which must finish before stage 2, and so on. For an n-bit adder the worst-case delay is proportional to n, the carry rippling through every stage. Double the width and you roughly double the delay. At 32 or 64 bits that linear delay is the slowest path in the whole machine.

Picture two ways to pass a message down a line of people. Ripple-carry is a bucket brigade: each person waits for the bucket from the person on their right before passing it left, so the last person waits for everyone. Lookahead is a dispatcher who already knows what every person is holding and works out, all at once, exactly what each one will pass along. The dispatcher answers everybody in one shot instead of waiting for the line.

Generate and propagate: two questions per column

The trick is to notice that, before any carry arrives, each bit column already knows how it will treat a carry. Ask each column two yes/no questions about its own bits a_i and b_i:

Generate g_i = a_i AND b_i: does this column produce a carry on its own? Only 1 + 1 makes a carry with no help, so generate is an AND.
Propagate p_i = a_i OR b_i: would this column pass an incoming carry on up? If at least one bit is 1, a carry coming in turns the column's sum into 10 and the carry sails through, so propagate is an OR.

Ai	Bi	Gi	Pi
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	1

Generate Gi = Ai AND Bi and propagate Pi = Ai OR Bi for one column. Gi = 1 only for 1,1 (this column makes its own carry); Pi = 1 whenever at least one bit is 1 (a carry coming in would pass through). Both depend only on Ai and Bi, so the whole adder can compute every Gi and Pi at the same instant.

Those two signals sort every column into one of three carry behaviors, and the third one has a name too. When both bits are 0, the column kills a carry: it can neither make one (g_i = 0) nor pass one (p_i = 0), so its carry-out is 0 whatever comes in (the 0,0 row). When exactly one bit is 1, the column propagates: p_i = 1 and g_i = 0, so an incoming carry leaves unchanged and a 0 stays 0 (the 0,1 and 1,0 rows). When both bits are 1, the column generates: g_i = 1, so it puts out a carry on its own (the 1,1 row). Kill, propagate, generate is the full vocabulary of what a single column can do to a carry.

Some textbooks define propagate as p_i = a_i XOR b_i instead of a_i OR b_i. The two disagree only on the 1,1 row, and there g_i is already 1, so the next carry comes out 1 either way. OR and XOR give the same carries; XOR is handy because it is also the column's sum bit, so one gate does double duty.

The carry recurrence

Now the carry out of column i has a tidy form: the column carries if it generates a carry, or if it propagates a carry that came in. That is the whole adder's carry chain in one line:

c_(i+1) = g_i + p_i · c_i

Written this way it is still a chain: c_2 needs c_1, which needs c_0. But it is a chain we can unroll. Substitute each carry's formula into the next, and every carry becomes a flat expression in the generate and propagate signals plus the single starting carry c_0, with no c on the right-hand side. Those signals are all available immediately, so every carry is now a two-level AND-OR function of the inputs.

Worked example: expand the carries of a 4-bit adder

Start from c_(i+1) = g_i + p_i · c_i and unroll it. c_0 is the external carry-in:

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 · c_2

= g_2 + p_2·g_1 + p_2·p_1·g_0 + p_2·p_1·p_0·c_0

The pattern is easy to read: c_3 is 1 if column 2 generates, or column 1 generates and column 2 propagates it, or column 0 generates and both columns above propagate it, or the incoming c_0 propagates the whole way up. The next carry continues the same shape:

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 one of these is just ANDs feeding an OR, two gate levels deep, and none of them waits on another carry. So after one gate delay to make all the gs and ps and one or two more for the lookahead, all four carries are ready at once. The sum bits then follow from s_i = a_i XOR b_i XOR c_i. The carry no longer ripples: it is computed.

Each column's generate and propagate come from one AND and one OR on its two input bits. The micro-figure below is that per-bit cell: Gi = Ai AND Bi and Pi = Ai OR Bi. A lookahead adder builds one of these per column, then feeds all the Gi and Pi into the flat carry equations above.

The generate/propagate cell for one bit: Gi = Ai AND Bi (this column makes its own carry) and Pi = Ai OR Bi (this column passes a carry through). Open it in the lab and sweep Ai and Bi: Gi lights only for 1,1, Pi lights whenever either bit is 1.

Common mistakes. Lookahead changes only *how fast* the carries are produced, not *what* the answer is: a lookahead adder and a ripple adder compute the identical sum, so do not expect different bits. Do not try to build a single flat lookahead over all 32 or 64 bits either: c_n needs an OR with n+1 terms and ANDs with up to n+1 inputs, and that fan-in (and the wires feeding it) blows up. And remember the recurrence uses propagate p_i = a_i OR b_i for the *carry*; the *sum* still uses a_i XOR b_i XOR c_i, a different combination of the same bits.

The cost is area, and the fix is hierarchy

This is the course's first real speed-versus-area trade. Ripple-carry is tiny and slow; full lookahead is fast but the gates and wiring grow quickly with width. The practical answer is to do lookahead in blocks. Split a 16-bit adder into four 4-bit lookahead units, each producing its four carries fast, plus a block-level generate and propagate for the whole group. A second layer of lookahead then computes the carry into each block from those block signals, exactly the same equations one level up. That hierarchy keeps every gate small while still avoiding the long ripple.

Two more designs push the same idea further, worth knowing by name. A carry-select adder computes a block's sum *twice* in parallel, once assuming the incoming carry is 0 and once assuming 1, then uses a multiplexer to pick the right pair the moment the real carry arrives, hiding the block's delay. Parallel-prefix adders (Kogge-Stone, Brent-Kung, and friends) arrange the generate/propagate combining into a tree, so the carries are ready in a number of levels proportional to log n rather than n. They are the adders inside fast modern CPUs.

Carry-select: add both ways, then choose

The carry-select adder attacks the same bottleneck as block lookahead (a block cannot finish until it knows its carry-in) with an almost cheeky trick: if a block does not yet know whether its carry-in will be 0 or 1, have it work out the answer for both guesses at once and throw one away. Split the word into blocks. Every block above the lowest builds two adders side by side, one wired with carry-in 0 and one wired with carry-in 1. Both start the instant the input bits arrive, long before the real carry has climbed up from below, so each upper block is already holding two finished candidate sums (and two candidate carry-outs) well before it knows which one is right.

When the real carry finally arrives from the block below, a bank of 2:1 multiplexers, one per sum bit, uses it as the select line: carry-in 0 keeps the first candidate, carry-in 1 keeps the second. The wait is one mux delay instead of a full ripple through the block's adders. That same carry also selects between the block's two candidate carry-outs, and the chosen carry-out becomes the select line for the next block up. So the carry still travels block by block, but now it only passes through one fast mux per block boundary, never again through a full-adder stage. The adders all finished long ago; the arriving carry is just flipping switches on its way up.

Work a concrete one. Split an 8-bit add into a low nibble (bits 0 to 3) and a high nibble (bits 4 to 7), and add A = 0110 1101 to B = 0011 0110. The low block adds normally: 1101 + 0110 = 1 0011, a sum of 0011 with carry-out 1. The high block refuses to wait for that carry and adds its own bits 0110 + 0011 twice, in parallel:

**Assuming carry-in 0:** 0110 + 0011 + 0 = 1001 (6 + 3 = 9), carry-out 0.
**Assuming carry-in 1:** 0110 + 0011 + 1 = 1010 (6 + 3 + 1 = 10), carry-out 0.

The low block's real carry-out turns out to be 1, so every mux in the high block selects the second candidate: the high sum is 1010 and its carry-out is 0. Stitch the halves back together and the result is 1010 0011. Check it against a plain add: A = 0110 1101 = 109 and B = 0011 0110 = 54, and 109 + 54 = 163 = 1010 0011. Identical to what a ripple adder produces, except the high block did its work *at the same time* as the low block rather than after it. All the carry had to do at the boundary was flip one mux.

With more blocks the picture just repeats. A 32-bit adder in eight 4-bit blocks precomputes both carry versions of every block above the first, all at once, and the real carry ripples up through one mux per block to pick the winners. The worst-case delay is about one block's add time (the blocks overlap) plus one mux delay for each block boundary the carry crosses, which grows with the *number of blocks*, not the total width. Fewer, wider blocks give a shorter mux chain but slower blocks; more, narrower blocks give faster blocks but a longer chain, so some block size minimizes the worst case.

Carry-select versus carry-lookahead: two ways to spend area for speed. Lookahead keeps a single adder and bolts on AND-OR carry logic, so its cost is gate fan-in that balloons with width. Carry-select keeps simple adders (each block can even be a plain ripple adder) but builds *two* of every upper block plus a mux bank, roughly doubling the adder hardware. Lookahead rewrites how the carry is computed; carry-select precomputes both answers and picks late. Neither is strictly better, and real high-speed adders often blend them: lookahead or parallel-prefix logic inside each block, carry-select between blocks.

Try it

Using c_(i+1) = g_i + p_i · c_i, expand c_3 in terms of the generate and propagate signals and c_0. Then evaluate it for A = 0110, B = 0011, c_0 = 0 and check it against adding the numbers by hand.

Carry-lookahead is the first place the course buys speed with extra hardware, and that trade never stops mattering: adders, multipliers, and the whole ALU live or die on how fast the carry resolves, because the longest carry path sets the clock period. Next, binary multiplication reuses these fast adders, summing a whole grid of partial products.

Frequently asked

What is a carry-lookahead adder?

A carry-lookahead adder is an adder that computes all of its carries in parallel, directly from the input bits, instead of letting each carry ripple up one stage at a time. It derives a generate signal g_i = a_i AND b_i and a propagate signal p_i = a_i OR b_i for each bit, then evaluates every carry from those signals at once, so its delay does not grow linearly with width like a ripple-carry adder.

What are generate and propagate in a carry-lookahead adder?

Generate g_i = a_i AND b_i means a bit column makes a carry on its own (only 1 + 1 does). Propagate p_i = a_i OR b_i means the column would pass an incoming carry on up (true whenever at least one bit is 1). Together they give the carry recurrence c_(i+1) = g_i + p_i · c_i, which unrolls into a flat function of the inputs.

Why is a ripple-carry adder slower than a carry-lookahead adder?

In a ripple-carry adder each stage must wait for the carry from the stage below, so the carry walks through every bit and the worst-case delay is proportional to the word width n. A carry-lookahead adder expands the carry recurrence into a two-level AND-OR expression that depends only on the inputs, so all carries resolve in roughly constant gate delay regardless of width.

What is the trade-off of carry-lookahead?

Speed for area. Computing every carry in parallel needs extra AND-OR logic, and a flat lookahead over many bits needs gates with impractically large fan-in. Designs solve this with block (hierarchical) lookahead, carry-select adders, and parallel-prefix adders, which keep the gates small while still beating the linear ripple delay.

Do carry-lookahead and ripple-carry adders give the same answer?

Yes. They compute the identical sum bits and the identical carries; lookahead only changes *how fast* those carries are produced, not their values. The whole point is to get the same result in less time.

What is the difference between a carry-select adder and a carry-lookahead adder?

Both cut the ripple delay by spending extra area, but in different ways. A carry-lookahead adder keeps one adder and adds AND-OR logic that computes the carries directly from the inputs, so its cost is gate fan-in that grows with width. A carry-select adder keeps simple adders but builds two copies of every upper block (one assuming carry-in 0, one assuming carry-in 1) plus a multiplexer bank, then picks the right precomputed sum the moment the real carry arrives and passes the chosen carry-out to the next block's select. Lookahead restructures the carry logic; carry-select precomputes both answers and selects late. Fast adders often combine the two.

Every lesson here builds toward one thing: a working CPU, from the transistor up.

Open the free lab →