Digital Design / Module 2: Combinational building blocks
9. Carry look-ahead and prefix adders
Trade area for speed.
See it move
The idea
A ripple adder makes the top bit wait for every carry below it. Faster adders work out the carries in parallel, using two signals from each bit position:
- Generate
G = A·B: this bit makes a carry, whatever comes in. - Propagate
P = A ^ B: this bit passes an incoming carry along.
Then C(i+1) = G(i) + P(i)·C(i).
Carry look-ahead
Substitute the equation into itself to remove the dependence on earlier carries:
C1 = G0 + P0·C0C2 = G1 + P1·G0 + P1·P0·C0C3 = G2 + P2·G1 + P2·P1·G0 + P2·P1·P0·C0
Each carry is now a two-level function of the inputs. The catch is that the terms grow with width, so gates become too wide past about four bits. Designs use small look-ahead blocks instead and combine them.
Prefix adders
A prefix tree merges neighbouring groups of bits: (G,P) pairs for 1 bit combine into 2-bit groups, then 4-bit, then 8-bit. A group's generate is G_hi + P_hi·G_lo, and its propagate is P_hi·P_lo. Each level doubles how far carry information has travelled, so depth grows with log2(N) rather than N.
Kogge-Stone and Brent-Kung are two well-known forms. Kogge-Stone has low fanout and many wires, whereas Brent-Kung uses fewer cells and more levels. In practice, the synthesis tool usually selects an architecture based on your timing constraints.
The trade-off
| Ripple | Prefix | |
|---|---|---|
| Delay | Grows with N | Grows with log2(N) |
| Area and wiring | Smallest | Larger |
| Use when | Timing is relaxed | Timing is tight |
Common mistake
Hand-writing a fast adder in RTL by default. Write a + b, set the timing constraint, and let the tool choose. Hand-built structures are worth the effort only when you have measured a problem they solve.
Key ideas
- Generate is AB, propagate is A xor B.
- Look-ahead computes carries in parallel.
- Prefix trees reach logarithmic depth.
Your exercise
Interview questions
coreExpress C2 with G and P.
C2 = G1 + P1G0 + P1P0C0.
basicDefine generate and propagate for one bit of an adder and say what each means.
Generate is G = A·B: both bits are 1, so the column makes a carry whatever comes in. Propagate is P = A XOR B: exactly one bit is 1, so the carry out copies the carry in. If both are 0, the column kills any incoming carry. Carry out is G + P·Cin.
basicHow many levels of merge cells does a prefix tree need for a 64-bit adder, compared with stages in a ripple adder?
Each prefix level doubles the span of bits each column knows about, so 64 bits need log2(64) = 6 levels. A ripple adder has a chain of 64 stages. The prefix adder pays for this with many more cells and wires.
coreFor A = 1011 and B = 0110 with carry in 0, compute G, P and every carry using look-ahead.
G = A & B = 0010 and P = A ^ B = 1101. C1 = G0 + P0·C0 = 0. C2 = G1 + P1·C1 = 1. C3 = G2 + P2·C2 = 0 + 1·1 = 1. C4 = G3 + P3·C3 = 0 + 1·1 = 1. Each sum bit is P XOR the carry into that bit: P = 1101 and the carries into bits 3 down to 0 are 1100, so the sum is 0001 with carry out 1. That is 10001 = 17, matching 11 + 6.
coreA low group has G = 1, P = 0 and the high group next to it has G = 0, P = 1. What are the merged group's G and P?
Merged G = G_hi + P_hi·G_lo = 0 + 1·1 = 1, and merged P = P_hi·P_lo = 1·0 = 0. The low group makes a carry and the high group passes it on, so the combined block generates. It does not propagate, because the low group would kill or replace any incoming carry.
coreWhy doesn't a flat carry look-ahead scale to 32 bits?
Expanding the carry equation gives C(i) with i + 1 product terms, and the largest term ANDs i + 1 signals. C32 would need 33 terms and a 33-input AND, built from long series transistor stacks that are slow. Flat look-ahead is practical only up to about four bits, so wider adders combine small blocks or use a prefix tree.
coreSome texts define propagate as A OR B instead of A XOR B. Do the carries still come out right? What about the sum?
The carries are still correct. The only case where OR and XOR differ is A = B = 1, and there G is already 1, so G + P·Cin is 1 either way. The sum, however, must use XOR, since sum = A XOR B XOR Cin. So designs that use OR for the carry tree still need an XOR for the sum.
advancedIn a 16-bit Kogge-Stone tree (carry in 0), how many merge cells are there and how many levels?
There are log2(16) = 4 levels. At the level that merges with the group 2^k places down, the columns from 2^k upward have a partner, so the levels have 15, 14, 12 and 8 cells, 49 in total. Kogge-Stone keeps depth minimal and fanout low, at the cost of many cells and long wires; Brent-Kung uses fewer cells but more levels.
advancedA hand-written prefix merge cell computes group generate as shown. Find a case where it gives the wrong carry.
// merge two (g,p) groups; hi is more significant assign g = g_hi | g_lo; assign p = p_hi & p_lo;
The correct rule is g = g_hi | (p_hi & g_lo): a carry from the low group only leaves the block if the high group passes it. Take a 2-bit block adding 01 + 01: the low bit generates (g_lo = 1) but the high bit has A = B = 0, so p_hi = 0 and g_hi = 0. The real sum is 10 with no carry out, but this cell reports g = 1.