Carry Look-Ahead Adder

Why ripple-carry is slow

In a ripple-carry adder bit 3 cannot finish until bit 2 hands it a carry, bit 2 waits for bit 1, and bit 1 waits for bit 0. The delay grows with the number of bits. A 64-bit add done this way would be far too slow for a CPU that adds billions of times a second.

The carry look-ahead adder (CLA) asks a different question: can we work out each carry directly from the input bits, without waiting for the carry below it? Yes. Two signals per bit are all we need.

Generate and propagate

Look at one column of the addition on its own, ignoring the carry coming in:

Ai	Bi	Gi = A·B	Pi = A ⊕ B	What this bit does with carries
0	0	0	0	kills a carry: 0 + 0 + 1 = 1, no carry out
0	1	0	1	propagates: carries out only if a carry comes in
1	0	0	1	propagates
1	1	1	0	generates: carries out whatever comes in

So a carry leaves bit i if bit i generates one, or it propagates one that came in:

C(i+1) = G(i) + P(i)·C(i)

Here + means OR and · means AND.

Every carry straight from the inputs

That formula still needs C_i. The trick is to substitute it again and again until only P, G and the first carry-in C0 are left:

C1 = G0 + P0·C0
C2 = 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 out loud: “there is a carry into bit 3 if bit 2 generates one, or bit 1 generates one and bit 2 passes it on, or bit 0 generates one and bits 1 and 2 pass it on, or the carry-in passes through all three.”

Every formula is just one layer of AND gates and one OR gate, and none of them uses another carry. So the hardware computes all four carries at the same time. Finally each sum bit is:

S(i) = P(i) ⊕ C(i)

Worked example: 11 + 6

1011 + 0110, carry-in C0 = 0.

Bit	A	B	P = A ⊕ B	G = A · B	Carry in Ci	Sum = P ⊕ C
0	1	0	1	0	0	1
1	1	1	0	1	0	0
2	0	1	1	0	1	0
3	1	0	1	0	1	0

• C2 = G1 + P1·G0 + P1·P0·C0 = 1 + 0 + 0 = 1 (bit 1 generates).
• C3 = G2 + P2·G1 + … = 0 + 1·1 + … = 1 (bit 1’s carry passes through bit 2).
• C4 = G3 + P3·G2 + P3·P2·G1 + … = 0 + 0 + 1·1·1 + … = 1 (it passes through bits 2 and 3 too).

Result: C4 followed by the sums = 10001 = 17.

How much faster?

Count gate delays: every gate takes one unit of time, and P and G take 1. Build both adders from the same P and G signals:

Output (4 bits)	Ripple-carry	Look-ahead
P and G	1	1
C1	3	3
C2	5	3
C3	7	3
C4 (carry-out)	9	3
Last sum bit S3	8	4

The ripple-carry adder needs 2n + 1 gate delays for its carry-out, so it grows with every bit. The look-ahead block is done in 4. Some textbooks count the ripple-carry delay as 2n because they don’t count making P and G as a separate step. The pattern is the same either way: ripple-carry grows with n, but one look-ahead block doesn’t.

The catch: wide gates

C4 already needs a 5-input OR and a 5-input AND. C16 would need 17-input gates, and real gates can only take a few inputs (their fan-in is limited). So real adders:

1. Build 4-bit look-ahead blocks.
2. Give each block a group generate G* = G3 + P3·G2 + P3·P2·G1 + P3·P2·P1·G0 and a group propagate P* = P3·P2·P1·P0.
3. Feed those into a second-level look-ahead unit that uses exactly the same formulas to find the carry into each block.

Each extra level covers 4 times as many bits and adds only a couple of gate delays, so the total delay grows as O(log n). This is how a 64-bit adder finishes in a handful of gate delays.

Some books define P = A OR B instead of A XOR B. The carries come out the same, but then the sum needs its own XOR. With XOR, one signal does both jobs.

Code

def lookahead_carry(i, P, G, c0):
    """C_i straight from P, G and C0: G[i-1] + P[i-1]G[i-2] + ... + P[i-1]...P[0]C0."""
    c = 0
    for j in range(-1, i):              # j = -1 stands for the carry-in term
        term = c0 if j < 0 else G[j]
        for k in range(j + 1, i):       # it must pass through every bit above j
            term &= P[k]
        c |= term
    return c

def cla_add(a, b, c0=0, n=4):
    P = [(a >> i & 1) ^ (b >> i & 1) for i in range(n)]   # propagate
    G = [(a >> i & 1) & (b >> i & 1) for i in range(n)]   # generate
    C = [lookahead_carry(i, P, G, c0) for i in range(n + 1)]
    S = [P[i] ^ C[i] for i in range(n)]
    return sum(s << i for i, s in enumerate(S)) | (C[n] << n)

print(cla_add(11, 6))      # 17
print(cla_add(15, 1))      # 16
print(cla_add(9, 5, 1))    # 15

In software the loops run one after another, but every lookahead_carry call is independent of the others. In hardware they all happen at once.

Common mistakes

• Writing C_i in terms of C_i−1. That is a correct formula, but it is the ripple-carry adder again. In a CLA each carry uses only P, G and C0.
• Forgetting the last term P_i−1…P0·C0. Without it a carry-in of 1 is lost.
• Mixing up P and G: G needs both bits to be 1, P needs exactly one.
• Thinking the delay stays constant for any width. Only one block is constant. Wide adders need more levels, so they are O(log n).