Fast Adders: Carry Lookahead

Why ripple-carry is not fast enough

The ripple-carry adder from the combinational-logic lesson chains n full adders, each waiting for the carry out of the stage before it. That dependency is exactly the problem: the worst-case delay through the whole adder grows with n, since the final stage cannot even start its real work until a carry has rippled all the way from bit 0. For a 4-bit adder this is a minor cost; for the 32-bit or 64-bit adders inside a real ALU, a carry chain that long would dominate the clock period on its own. A carry-lookahead adder (CLA) removes this growth by computing every stage's carry directly from the input bits, rather than waiting for it to propagate stage by stage.

Generate and propagate

The key move is to notice that each bit position's carry-out depends on its inputs in only two ways, and to give each of those two ways a name. Bit i generates a carry on its own, regardless of any incoming carry, exactly when both A_i and B_i are 1: Gi = Ai·Bi. Bit i propagates an incoming carry through to its carry-out exactly when exactly one of A_i, B_i is 1 – the case where a carry-in of 1 would tip the sum into producing a carry-out of 1 as well: Pi = Ai ⊕ Bi. Both G_i and P_i depend only on the two input bits at position i, so every bit position can compute its own G and P in parallel, with no dependency on any other bit – this is what makes the lookahead scheme fast.

Once G_i and P_i are available for every bit, the carry out of bit i is

Ci+1 = Gi + Pi·Ci

which reads directly as "bit i generates a carry on its own, or it propagates whatever carry came in." Expanding this recurrence by substitution shows why it is called lookahead: C₂ = G₁ + P₁G₀ + P₁P₀C₀, C₃ = G₂ + P₂G₁ + P₂P₁G₀ + P₂P₁P₀C₀, and so on – every carry can be written as a sum-of-products expression in the G's, P's and C₀ alone, with no term depending on any other carry. That means every C_i can, in principle, be computed directly and in parallel from the original inputs, instead of waiting on the carry before it.

Worked example: adding 11 and 6

Let us reuse the two numbers from the very first lesson's ripple-carry example – A = 1011 (11) and B = 0110 (6) – so the carry-lookahead result can be checked directly against that earlier, already-verified sum of 17.

With C₀ = 0, each carry follows directly from Ci+1 = Gi + PiCi:

• C₁ = G₀ + P₀C₀ = 0 + (1·0) = 0
• C₂ = G₁ + P₁C₁ = 1 + (0·0) = 1
• C₃ = G₂ + P₂C₂ = 0 + (1·1) = 1
• C₄ = G₃ + P₃C₃ = 0 + (1·1) = 1 (this is the final carry-out)

Each sum bit is then S_i = P_i ⊕ C_i: S₀ = 1⊕0 = 1, S₁ = 0⊕0 = 0, S₂ = 1⊕1 = 0, S₃ = 1⊕1 = 0. Reading the carry-out and sum bits together, C₄S₃S₂S₁S₀ = 1 0 0 0 1, which is binary 10001 – decimal 17, matching the ripple-carry result from the first lesson exactly, as it must, since both circuits compute the same addition by different means.

What it costs

The lookahead carries do not arrive for free. Expanding C₃ and C₄ algebraically, as shown earlier, produces sum-of-products expressions with more and more terms as the bit position grows – C₄ in a wider adder needs a term for every way a carry could have been generated at an earlier bit and propagated through everything after it. In practice this means the lookahead logic itself gets wider and more gate-heavy as the adder gets wider, which is why real wide adders (32-bit, 64-bit) do not use one flat lookahead block spanning every bit. Instead they build a lookahead adder across a manageable group of bits – often 4 – and then apply the same generate/propagate idea one level higher, treating each 4-bit group as if it were itself a single bit with a group-generate and group-propagate signal, to produce carries between groups just as quickly. This hierarchical construction is usually called a carry-lookahead adder with block (or group) carry generation, and it is the standard way real ALUs get both a short carry chain and a bounded amount of lookahead hardware at every width.