The Carry-Lookahead Adder
The ripple-carry adder of the last article has one clearly nameable problem: $C_2$ waits for $C_1$, which waits for $C_0$, and while the carry crawls up the chain most of the circuit sits idle. In this article we ask whether $C_2$ really needs $C_1$ at all. If $C_2$ can be written purely in terms of the inputs $A$ and $B$, it can be computed at the same moment as $C_1$, and so can every other carry. The dependency disappears. That is what the carry-lookahead adder does, and the trick has a name: generate and propagate.
Generate and propagate
For bit position $i$ with inputs $A_i$, $B_i$ and carry-in $C_i$, the carry-out is the majority function
$$C_{i+1} = A_iB_i + A_iC_i + B_iC_i$$
Now think about the two distinct ways a carry can come out of position $i$.
If both $A_i$ and $B_i$ are 1, there is a carry out whatever the carry in. The position generates a carry:
$$G_i = A_i B_i$$
If exactly one of $A_i$ and $B_i$ is 1, then a carry in becomes a carry out, and no carry in means no carry out. The position propagates the carry:
$$P_i = A_i \oplus B_i$$
With these, the carry-out is
$$C_{i+1} = G_i + P_i C_i$$
The important property is that $G_i$ and $P_i$ depend only on $A_i$ and $B_i$. They can all be computed at once, for every bit, the moment the inputs arrive, with no carry involved.
The lookahead equations
Now substitute each carry into the next:
$$C_1 = G_0 + P_0 C_0$$
$$C_2 = G_1 + P_1 C_1 = G_1 + P_1 G_0 + P_1 P_0 C_0$$
$$C_3 = G_2 + P_2 G_1 + P_2 P_1 G_0 + P_2 P_1 P_0 C_0$$
$$C_4 = G_3 + P_3 G_2 + P_3 P_2 G_1 + P_3 P_2 P_1 G_0 + P_3 P_2 P_1 P_0 C_0$$
Look at what these say. Every carry is written in terms of the $G$s, the $P$s and the single external carry-in $C_0$. $C_2$ does not mention $C_1$; $C_3$ does not mention $C_2$. All four can be computed at the same time, each as a two-level AND-OR expression of signals that are already available.
The pattern is easy to read. $C_k$ has $k + 1$ terms. The first is $G_{k-1}$: the top position generates. Each further term is a generate lower down, propagated through every position above it. The last term is $C_0$ propagated through every position, which happens only when every bit propagates.
The circuit
A 4-bit carry-lookahead adder has three stages (Figure 1).
Stage 1, generate and propagate. For every bit at once, an AND gate for $G_i$ and an XOR for $P_i$. One gate delay.
Stage 2, the lookahead unit. The four carry equations as two-level AND-OR logic. $C_4$, for example, is four AND gates feeding a 5-input OR. All four carries appear together after two more gate delays.
Stage 3, the sums. $S_i = P_i \oplus C_i$, one XOR per bit. One more gate delay.
Four gate delays in total for the 4-bit adder, against ten for the 4-bit ripple-carry adder.
Tracing 0110 + 0101
The same example as the last article, $A = 0110$ and $B = 0101$ with $C_0 = 0$.
| Bit | $A_i$ | $B_i$ | $G_i$ | $P_i$ |
|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 2 | 1 | 1 | 1 | 0 |
| 3 | 0 | 0 | 0 | 0 |
$$C_1 = 0 + 1 \cdot 0 = 0$$ $$C_2 = 0 + 1 \cdot 0 + 1 \cdot 1 \cdot 0 = 0$$ $$C_3 = 1 + \ldots = 1$$ $$C_4 = 0 + 0 \cdot 1 + \ldots = 0$$
$$S_0 = 1 \oplus 0 = 1 \quad S_1 = 1 \oplus 0 = 1 \quad S_2 = 0 \oplus 0 = 0 \quad S_3 = 0 \oplus 1 = 1$$
Result $1011$, carry out 0, the same as before, and every carry was computed in parallel.
Timing against the ripple-carry adder
| Width | Ripple-carry | Carry-lookahead (single level) |
|---|---|---|
| 4 | 10 | 4 |
| 16 | 34 | 4 in principle, see below |
| 32 | 66 | 4 in principle, see below |
The single-level CLA is four gate delays whatever the width, on paper. In practice there is a catch.
The fan-in problem
Count the terms in the carry equations as the width grows. $C_1$ has two terms, $C_4$ has five, $C_8$ has nine, $C_{16}$ has seventeen, and $C_{64}$ has sixty-five, one of which is a 64-input AND. Real gates have a fan-in limit; a standard cell library goes up to perhaps four or eight inputs. A 64-input AND has to be built as a tree of smaller gates, which adds levels of delay and eats the advantage. A flat single-level CLA is practical up to about four or eight bits and no further.
The hierarchical CLA
The fix is to apply the generate and propagate idea again, one level up. For a group of four bits, define a group generate and a group propagate:
$$G^{[3:0]} = G_3 + P_3 G_2 + P_3 P_2 G_1 + P_3 P_2 P_1 G_0$$
$$P^{[3:0]} = P_3 P_2 P_1 P_0$$
The group generates a carry if it produces a carry out regardless of its carry in, and it propagates if a carry in passes all the way through. These are just the coefficients of $C_4$ with the $C_0$ term separated out.
Now four 4-bit blocks each produce a group $G$ and $P$, and a second lookahead unit, identical in form to the first, computes the carries into each block: $C_4$, $C_8$, $C_{12}$ and $C_{16}$. The block-level carries feed back into the blocks, which compute their internal carries and sums. For 16 bits:
- bit-level $G$ and $P$: 1 gate delay
- group $G$ and $P$: 2
- block carries from the second-level unit: 2
- internal carries within each block: 2
- sums: 1
About 8 gate delays for 16 bits, against 34 for ripple-carry. A third level handles 64 bits in roughly 12. Delay grows with the logarithm of the width, which is what high-performance datapaths need.
Two more things worth knowing. Real implementations of the lookahead unit use the AOI and OAI compound cells from Module 1, which do an AND-OR level in one transistor stage and are noticeably faster and smaller than separate gates. And a common mistake in understanding the CLA is to picture the carries as a chain of 2-input gates, which would bring back the serial delay. They are not. Each carry has its own independent two-level network fed straight from the $G$ and $P$ signals.
The idea underneath is the one I mentioned in the first article of this section. We asked what property of a bit position determines its carry behaviour independently of what comes before it. The answer, generate or propagate, is a function of the inputs alone, and that is what lets the chain be flattened. Prefix sums and carry-save arithmetic use the same move.
Practice Exercise
For $A = 1011$, $B = 0110$, $C_0 = 1$: compute $G_i$ and $P_i$, derive $C_1$ to $C_4$ from the lookahead equations, compute the sum, and check it in decimal.
Solution
| Bit | $A_i$ | $B_i$ | $G_i$ | $P_i$ |
|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 0 |
| 2 | 0 | 1 | 0 | 1 |
| 3 | 1 | 0 | 0 | 1 |
$C_1 = 0 + 1 \cdot 1 = 1$. $C_2 = 1 + 0 + 0 = 1$. $C_3 = 0 + 1 \cdot 1 + 0 + 0 = 1$. $C_4 = 0 + 1 \cdot 0 + 1 \cdot 1 \cdot 1 + 0 + 0 = 1$.
$S_0 = 1 \oplus 1 = 0$, $S_1 = 0 \oplus 1 = 1$, $S_2 = 1 \oplus 1 = 0$, $S_3 = 1 \oplus 1 = 0$. Result $0010$ with carry out 1.
Decimal: $11 + 6 + 1 = 18 = 10010_2$. Lower four bits $0010$, carry out 1. Correct.
The carry-lookahead adder computes carries analytically, at the cost of logic that grows quickly with width. The next article takes a completely different approach: do not compute the carry faster at all, compute both possible results and pick one when the carry arrives.