Skip to content
Tutorials Center
My learning

Topics

Lesson 24 of 57 · Combinational Building Blocks

Carry-Lookahead and Faster Adders

Why ripple-carry adders are slow and how carry-lookahead, carry-select and carry-skip adders speed them up, with propagate and generate signals and a Python delay model.

The ripple-carry adder has one big weakness: bit 31 has to wait for bit 30, which waits for bit 29, all the way down to bit 0. In a modern processor an addition happens billions of times per second, so waiting for a carry to crawl through 64 stages is out of the question. The cure is to stop waiting for carries and predict them instead.

This lesson introduces the two signals that make prediction possible, propagate and generate, derives the carry-lookahead equations, compares delays with a small Python model, and gives a short tour of two other speed-up tricks: carry-select and carry-skip.

Why the carry is the bottleneck

Look at one full adder. Its sum depends on its carry-in, but the sum gate is only one gate deep. The expensive part is the carry-out, Cout = G + P·Cin, which needs an AND and an OR (two gate delays) after the previous carry is ready. Chain n of these and the last carry arrives after roughly 2n gate delays. The inputs A and B of every bit are known at time zero, so in principle every carry can be computed right away. The question is how to write each carry as a direct function of the inputs, without passing through the carries in between.

Propagate and generate

For one bit position, the carry-out is decided by two simple questions.

  • Generate G = A·B: both inputs are 1, so this bit creates a carry no matter what comes in.
  • Propagate P = A ⊕ B: exactly one input is 1, so this bit passes on an incoming carry (a carry-in of 1 produces a carry-out of 1, and a carry-in of 0 does not).

If both inputs are 0, the bit absorbs any carry and sends out 0. The carry-out is therefore

Cout = G + P·Cin

and the sum bit is S = P ⊕ Cin. Both signals depend only on A and B, so all P and G values are ready after one gate delay, in parallel.

Three things a bit can do with a carry

Generate Both inputs 1. Makes a carry on its own.
Propagate Inputs differ. Passes the carry along.
Kill Both inputs 0. Absorbs any carry.

Only generate and propagate matter in the equations.

1 / 2

The lookahead equations

Now substitute. Write c0 for the carry into the lowest bit and c1, c2, ... for the carries into the following bits:

  • c1 = G0 + P0·c0
  • c2 = G1 + P1·c1 = G1 + P1·G0 + P1·P0·c0
  • c3 = G2 + P2·G1 + P2·P1·G0 + P2·P1·P0·c0
  • c4 = G3 + P3·G2 + P3·P2·G1 + P3·P2·P1·G0 + P3·P2·P1·P0·c0

Read c3 aloud: "a carry enters bit 3 if bit 2 generated one, or bit 1 generated one and bit 2 propagates it, or bit 0 generated one and bits 1 and 2 both propagate it, or the incoming carry propagates through all three." Every term is an AND of signals that are available after one gate delay, and the terms are combined by one OR. So each carry takes just two more gate delays (AND, then OR), no matter which bit it belongs to. Nothing ripples.

The Python function below follows these equations literally: it builds each carry from P, G and c0 with nested loops that mirror the product terms. It then proves itself against ordinary addition for every 4-bit pair and both values of c0.

Python A 4-bit carry-lookahead adder

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The lists run from the least significant bit. For 11 + 6 = 17, only bit 1 generates a carry (both operands have a 1 there), while bits 0, 2 and 3 propagate. The lookahead produces c2 = 1 straight away, and that carry then propagates through bits 2 and 3 to give a carry out of 1 and the sum 0001.

The catch: fan-in

The equations look perfect, but gates have a limited number of inputs. The term P3·P2·P1·P0·c0 needs a five-input AND, and for 32 bits the last carry would need a 33-input gate and a 33-term OR. Real gates cannot do that quickly (or at all). The practical answer is hierarchical lookahead: build 4-bit lookahead blocks, give each block a group generate and group propagate signal (GG says "this block makes a carry on its own", PP says "this block passes a carry through"), and apply the same lookahead equations again to the blocks. The same trick used twice or three times covers 16, 64 or more bits, and the delay grows with the logarithm of the width instead of linearly.

Two other tricks: select and skip

Carry-lookahead is not the only way to beat the ripple. Two classic alternatives are simple to understand.

  • Carry-select adder. Split the number into blocks. For every block except the first, build two small ripple adders: one that assumes the incoming carry is 0 and one that assumes it is 1. While the earlier blocks are still working, both answers are already computed. When the real carry arrives, a multiplexer picks the right result. The carry only has to pass through one multiplexer per block instead of a whole adder. The price is roughly double the hardware.
  • Carry-skip adder. Each block also computes whether all its bits propagate (the AND of its P signals). If so, an incoming carry can skip the whole block through a bypass gate instead of rippling through it. It is cheap, but the worst case still ripples through the first and last blocks.

A delay model in Python

Let every AND, OR or XOR gate take one unit of delay and measure the time until the carry out of the whole adder is ready. The model below uses blocks of 4 bits. The formulas are rough (they ignore fan-out and wire delay), but they capture how each design scales.

  • Ripple: P and G take 1 unit, then each stage adds 2, so 1 + 2n.
  • Lookahead blocks that ripple between blocks: the first block's carry is ready at 3 and each further block adds 2.
  • Carry-select: the first block ripples (9 units), then each block adds one multiplexer delay.
  • Carry-skip: ripple through the first block, skip each middle block at 2 units, ripple through the last block.
Python Carry-out delay of four adder designs

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For 64 bits the ripple adder needs 129 units while lookahead blocks need 33, select 24 and skip 45. For a single 4-bit block, lookahead takes 3 units against 9 for rippling. Notice that select beats a chain of lookahead blocks at 64 bits in this model, because each block hands over the carry in a single multiplexer step. In real designs these ideas are mixed: a processor adder typically uses a multi-level lookahead tree for the carries and a few other tricks tuned to the technology.

The numbers are a teaching model, not a measurement of any real chip. Real delay depends on the manufacturing process, fan-in and fan-out limits, wire length and how the adder is laid out. What carries over is the shape: ripple grows linearly with width, while lookahead trees grow with the logarithm of the width, at the cost of more gates.

Speed against cost

No adder wins on every axis. The ripple-carry adder is the smallest. Carry-lookahead and carry-select are faster but larger; carry-skip sits in the middle. Designers pick based on the requirement: a small microcontroller or a low-power circuit may happily use ripple-carry, while the arithmetic unit in a desktop processor spends a lot of silicon on a tree adder. You will meet the same area-versus-speed trade-off again in the ALU design lesson.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. A bit position has A = 1 and B = 0. What does it do with an incoming carry?

    The inputs differ, so P = A XOR B = 1 and G = A AND B = 0. A carry coming in produces a carry going out, but this bit does not create one by itself.
  2. 2. Which equation is correct for the carry into bit 2?

    Substitute c1 = G0 + P0·c0 into c2 = G1 + P1·c1 and expand, which gives the three terms of the first option.
  3. 3. Why does a flat 32-bit carry-lookahead adder run into trouble in practice?

    The highest carry has a term with dozens of ANDed signals, and real gates have limited fan-in. Hierarchical lookahead with group propagate and generate signals solves it.
  4. 4. What does a carry-select adder compute in advance?

    Each block (after the first) is built twice, once assuming carry-in 0 and once assuming 1. A multiplexer picks the correct result when the real carry arrives.
  5. 5. How does the delay of a hierarchical lookahead adder grow with width?

    Each lookahead level combines about four groups, so the number of levels, and therefore the delay, grows like the logarithm of the width.

Summary

  • The slow part of a ripple-carry adder is the carry travelling from stage to stage.
  • Per bit, G = A·B generates a carry and P = A ⊕ B propagates one; Cout = G + P·Cin and S = P ⊕ Cin.
  • Carry-lookahead expands the carry equations so every carry comes straight from P, G and c0 in two gate levels.
  • Large fan-in limits flat lookahead, so real designs use hierarchical lookahead with group P and G signals, and delay grows with the logarithm of the width.
  • Carry-select computes both answers and chooses; carry-skip lets a carry bypass a block whose bits all propagate.
  • Speed costs gates: pick the adder that fits the speed and area budget.

Next: Subtractors and Comparators.