Each bit declares two facts: generate g = a & b, and propagate p = a ^ b. Generate makes a carry locally; propagate passes an incoming carry through.
The carry recurrence is c[i+1] = g[i] + p[i] c[i], with + as OR and juxtaposition as AND. Unrolling it removes the wait for lower bits.
Signal | Formula | Meaning |
|---|---|---|
g[i] | a[i] & b[i] | Bit i creates a carry regardless of carry-in. |
p[i] | a[i] ^ b[i] | Bit i passes its carry-in to carry-out. |
c[i+1] | g[i] + p[i] c[i] | Carry-out from local facts plus the incoming carry. |
A 4-bit block unrolls the recurrence fully. Every carry is a sum of products of g, p, and the block carry-in.
Notation below: + is OR, juxtaposition is AND. Each product covers one way the carry can arise.
4-bit lookahead block with carry-in c0:
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
s[i] = p[i] ^ c[i] for i = 0..3The block carry uses two AND-OR levels instead of four ripple stages. But the widest product has five inputs, so wider blocks slow each gate.
Designs group 4 bits at a time and add a second lookahead level across groups. Group size trades fewer levels against wider, slower gates, and the best size varies by library.
EXAMPLE parameters (not measured silicon): one AND-OR level = 1 unit, one ripple carry stage = 2 units
16-bit two-level lookahead, 4-bit groups: pg 1 + block 2 + top 2 + sum 1 = 6 units
16-bit ripple: 16 x 2 = 32 unitsc4 = g3 + p3 g2 + p3 p2 g1 + p3 p2 p1 g0 + p3 p2 p1 p0 c0 = 0 + 1 + 1 + 0 + 0 = 1. Bits 1 and 2 generate and the upper bits propagate.
The unit costs are EXAMPLE parameters. A library with slow wide gates or fast carry chains changes both rows, so the comparison must be remeasured.