# Carry-lookahead adders

*Computing every carry at once*

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.

Group: Arithmetic
URL: https://digiwleea.wleeaf.dev/learn/carry-lookahead/

The [8-bit ripple-carry adder](https://digiwleea.wleeaf.dev/learn/adder8/) is correct and simple: eight [full adders](https://digiwleea.wleeaf.dev/learn/fulladder/) 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.

> **TIP:** 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](https://digiwleea.wleeaf.dev/learn/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](https://digiwleea.wleeaf.dev/learn/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.

> **TIP:** 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 `g`s and `p`s 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](https://digiwleea.wleeaf.dev/learn/and/) and one [OR](https://digiwleea.wleeaf.dev/learn/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.

_Circuit diagram: 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._

> **WARN:** **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](https://digiwleea.wleeaf.dev/learn/mux/) 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](https://digiwleea.wleeaf.dev/learn/mux/), 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.

> **KEY:** **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.

**Q (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.

**A:** Unrolling gives `c_3 = g_2 + p_2·g_1 + p_2·p_1·g_0 + p_2·p_1·p_0·c_0`. For `A = 0110`, `B = 0011`: column 0 has `a_0 = 0, b_0 = 1`, so `g_0 = 0, p_0 = 1`; column 1 has `1,1`, so `g_1 = 1, p_1 = 1`; column 2 has `1,0`, so `g_2 = 0, p_2 = 1`. Substitute: `c_3 = 0 + 1·1 + 1·1·0 + 1·1·1·0 = 1`. Check by hand: `0110 + 0011 = 1001` (6 + 3 = 9), and the carry into bit 3 is indeed `1` (bit 1 generated a carry that propagated up through bit 2). The lookahead equation agrees with the ripple, just without waiting.

> **KEY:** Carry-lookahead is the first place the course buys speed with extra hardware, and that trade never stops mattering: adders, [multipliers](https://digiwleea.wleeaf.dev/learn/multiplier/), and the whole [ALU](https://digiwleea.wleeaf.dev/learn/alu/) live or die on how fast the carry resolves, because the longest carry path sets the clock period. Next, [binary multiplication](https://digiwleea.wleeaf.dev/learn/multiplier/) reuses these fast adders, summing a whole grid of partial products.

### FAQ

**Q:** What is a carry-lookahead adder?

**A:** 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](https://digiwleea.wleeaf.dev/learn/adder8/).

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

**A:** **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.

**Q:** Why is a ripple-carry adder slower than a carry-lookahead adder?

**A:** 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.

**Q:** What is the trade-off of carry-lookahead?

**A:** 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.

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

**A:** 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.

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

**A:** 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](https://digiwleea.wleeaf.dev/learn/mux/) 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.