Carry Lookahead Adder

Introduction

The carry lookahead adder (CLA) solves the fundamental speed problem of the ripple carry adder. In a ripple carry adder, each bit position must wait for the carry from the previous position before it can compute its final result. For a 32-bit adder, the worst case requires the carry to propagate through all 32 stages sequentially, resulting in unacceptable delay for high-speed processors. The CLA eliminates this sequential dependency by computing all carry signals simultaneously using dedicated lookahead logic.

The insight behind the CLA is that we can predict whether each bit position will generate a new carry or propagate an incoming carry, and use these predictions to calculate all carries in parallel with just two levels of logic gates — regardless of the adder width. This transforms the addition delay from O(n) to O(1) for a single-level CLA, or O(log n) for practical multi-level designs.

Generate and Propagate Signals

The CLA is built on two fundamental concepts for each bit position i:

Generate (Gi): Position i generates a carry-out regardless of whether there is a carry-in. This happens when both inputs are 1: Gi = Ai AND Bi

Propagate (Pi): Position i will propagate an incoming carry to its output. This happens when exactly one input is 1: Pi = Ai XOR Bi

Note that Pi also serves as the sum bit before the carry-in is incorporated (Sum_i = Pi XOR Ci). Some implementations use Pi = Ai OR Bi instead of XOR, which simplifies carry logic but requires separate XOR gates for the sum. The XOR version is more common because it serves dual purposes.

Deriving the Carry Equations

Starting from the fundamental carry relation — a carry-out occurs when the position generates a carry OR when it propagates an incoming carry:

Ci+1 = Gi + Pi · Ci

We can recursively expand this for each position:

• C1 = G0 + P0 · C0
• C2 = G1 + P1 · C1 = G1 + P1 · G0 + P1 · P0 · C0
• C3 = G2 + P2 · C2 = 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

Each carry equation depends only on the original inputs (A, B) and the initial carry-in (C0) — there is no dependency on previous carry results. All of these can be evaluated simultaneously using a two-level AND-OR network.

Worked Example: 4-Bit CLA

Let us add A = 1011 and B = 0111 with C0 = 0:

First, compute G and P for each position:

• Position 0: G0 = 1·1 = 1, P0 = 1⊕1 = 0
• Position 1: G1 = 1·1 = 1, P1 = 1⊕1 = 0
• Position 2: G2 = 0·1 = 0, P2 = 0⊕1 = 1
• Position 3: G3 = 1·0 = 0, P3 = 1⊕0 = 1

Now compute carries simultaneously:

• C1 = G0 + P0·C0 = 1 + 0·0 = 1
• C2 = G1 + P1·G0 + P1·P0·C0 = 1 + 0 + 0 = 1
• C3 = G2 + P2·G1 + P2·P1·G0 + P2·P1·P0·C0 = 0 + 1·1 + 0 + 0 = 1
• C4 = G3 + P3·G2 + P3·P2·G1 + P3·P2·P1·G0 + P3·P2·P1·P0·C0 = 0 + 0 + 1·1·1 + 0 + 0 = 1

Finally, compute sums: Si = Pi ⊕ Ci

• S0 = P0 ⊕ C0 = 0⊕0 = 0
• S1 = P1 ⊕ C1 = 0⊕1 = 1
• S2 = P2 ⊕ C2 = 1⊕1 = 0
• S3 = P3 ⊕ C3 = 1⊕1 = 0

Result: C4 S3 S2 S1 S0 = 1 0010 = 10010 (decimal 18). Check: 11 + 7 = 18. Correct!

Delay Analysis

The CLA computes its result in three stages:

1. Stage 1: Compute all Gi and Pi values (1 gate delay — AND and XOR in parallel)
2. Stage 2: Compute all carries using the lookahead logic (2 gate delays — one AND level, one OR level)
3. Stage 3: Compute all sums Si = Pi XOR Ci (1 gate delay)

Total: approximately 4 gate delays for any width CLA. Compare this to a 4-bit ripple carry adder's 8 gate delays, or a 32-bit ripple carry adder's 64 gate delays.

The Hardware Cost Trade-off

The speed improvement comes at a cost: the carry equations grow wider as position increases. C4 requires a 5-input OR gate fed by AND gates with up to 5 inputs. For a 16-bit single-level CLA, C16 would require a 17-input OR gate and AND gates with up to 17 inputs. Wide gates are impractical — they are slow, large, and difficult to fabricate. This limits practical single-level CLA to about 4 bits.

Multi-Level (Hierarchical) CLA

To build adders wider than 4 bits, we use group generate and group propagate signals with hierarchical lookahead. A 16-bit adder is constructed from four 4-bit CLA blocks, each producing a group generate (Gg) and group propagate (Pg):

• Gg = G3 + P3·G2 + P3·P2·G1 + P3·P2·P1·G0 (the group generates a carry)
• Pg = P3·P2·P1·P0 (the group propagates an incoming carry through all four positions)

A second-level Carry Lookahead Generator (CLG) takes these group signals and computes inter-group carries using the same lookahead principle. This creates a two-level CLA: carries within 4-bit groups are computed by first-level CLA logic, and carries between groups are computed by the second-level CLG. The total delay is approximately 4 + 2 = 6 gate delays for 16 bits — dramatically faster than 32 gate delays for a 16-bit ripple carry adder.

For 64-bit addition, a three-level hierarchy might be used: 4-bit CLA blocks, 16-bit group CLA, and a 64-bit top-level CLG.

The 74181: A Classic CLA Chip

The 74181, introduced in 1970, was a famous 4-bit ALU chip that used carry lookahead internally. It computed 16 arithmetic functions and 16 logic functions, with group generate and propagate outputs for cascading with the 74182 carry lookahead generator chip. Four 74181s plus one 74182 created a fast 16-bit ALU. This architecture directly influenced modern ALU design.

Key Takeaways

1. The CLA eliminates sequential carry propagation by computing all carries simultaneously
2. Generate (Gi = Ai AND Bi) indicates a position will produce a carry regardless of carry-in
3. Propagate (Pi = Ai XOR Bi) indicates a position will pass through an incoming carry
4. Carry equations are expanded so each depends only on original inputs and C0 — enabling parallel evaluation
5. A single-level 4-bit CLA computes in approximately 4 gate delays versus 8 for ripple carry
6. Hierarchical CLA uses group generate/propagate to extend the technique to 16, 32, or 64 bits
7. The CLA trades increased gate count and wiring complexity for dramatically reduced delay