Carry Lookahead Generation

Motivation

The ripple carry adder is slow because carry bit $c_i$ must be computed before $c_{i+1}$ can be computed. The insight behind carry lookahead is that all carries can be generated directly from the inputs, without waiting for the ripple chain, by evaluating the logical conditions for a carry to arise.

Generate, propagate, and kill

For a single bit position with inputs $a_i$ and $b_i$, three mutually exclusive conditions determine whether a carry-out is produced:

• Carry generate $g_i = a_i \cdot b_i$: both bits are 1, so a carry-out is always produced regardless of the carry-in. The column “generates” a carry.
• Carry propagate $p_i = a_i \oplus b_i$: exactly one of the bits is 1, so a carry-out is produced if and only if the carry-in is 1. The column “propagates” the incoming carry.
• Carry kill $k_i = \bar{a}_i \cdot \bar{b}_i$: both bits are 0, so no carry-out is produced regardless of the carry-in.

Note that $p_i = a_i \oplus b_i$ is the standard definition in this course. Some texts define $p_i = a_i + b_i$ (the “propagate if either is 1”), which gives different equations but equivalent results when used with appropriate generate definitions.

Carry recurrence

The fundamental recurrence for the carry chain is:

$c_{i+1} = g_i + p_i \cdot c_i$

In words: column i produces a carry-out if it generates one, OR if it propagates the incoming carry. This is exactly the expression derived from the full adder truth table: cout = a·b + (a⊕b)·cin.

Unrolling the recurrence

By substituting repeatedly, every carry is expressed directly in terms of the primary inputs $a_i$, $b_i$, and $c_0$:

$c_1 = g_0 + p_0 \cdot c_0$

$c_2 = g_1 + p_1 \cdot g_0 + p_1 \cdot p_0 \cdot c_0$

$c_3 = g_2 + p_2 \cdot g_1 + p_2 \cdot p_1 \cdot g_0 + p_2 \cdot p_1 \cdot p_0 \cdot c_0$

$c_4 = g_3 + p_3 \cdot g_2 + p_3 \cdot p_2 \cdot g_1 + p_3 \cdot p_2 \cdot p_1 \cdot g_0 + p_3 \cdot p_2 \cdot p_1 \cdot p_0 \cdot c_0$

Pattern: $c_{i+1}$ is the OR of its own generate, OR the propagate AND each lower generate, OR the propagate of all lower positions AND $c_0$.

Two-level logic

Each carry equation is a sum-of-products expression in the primary inputs (the $g_i$ and $p_i$ are themselves functions of $a_i$, $b_i$). Implementing these equations directly gives a two-level AND-OR circuit for each carry.

The critical path from inputs to any carry is:

• 1 gate delay to compute $g_i$ and $p_i$ from $a_i$, $b_i$.
• 1 gate delay for the AND plane (computing product terms like $p_2 \cdot p_1 \cdot g_0$).
• 1 gate delay for the OR plane (combining product terms).

Total: 3 gate delays, independent of n. This is a dramatic improvement over the O(n) ripple delay.

Practical limitations

Two problems arise for large n:

1. Fan-in: $c_n$ requires an OR gate with n+1 inputs and AND gates with up to n inputs. Gates with high fan-in are slow and physically large.
2. Fan-out: Early $g_i$ and $p_i$ signals must fan out to many subsequent carry equations.

In practice, carry lookahead is applied in blocks of 4 bits, with ripple between blocks. Alternatively, a second level of lookahead (block generate G = g3 + p3·g2 + p3·p2·g1 + p3·p2·p1·g0 and block propagate P = p3·p2·p1·p0) creates a two-level hierarchy.

Sum computation

Once the carries are known, each sum bit is:

$s_i = p_i \oplus c_i = a_i \oplus b_i \oplus c_i$

The carries and sums can be computed in parallel, yielding the full addition result in O(1) gate delays from the inputs.