The key to fast adders is to perform operations in parallel.

Suppose ci is the carry in for bit i of an adder and ai and bi are bit i of the numbers a and b.

ci+1 = (ai . bi) + (ai . ci) + (bi . ci)

We are interested in determining carry bits quickly, so factor out ci in the above equation:

ci+1 = (ai . bi) + (ai + bi) . ci

Consider c2:

c2 = (a1 . b1) + (a1 + b1) . c1

Substituting for c1 gives us:

c2 = (a1 . b1) + (a1 + b1) . ((a0 . b0) + (a0 + b0) . c0)

Notice that (ai . bi) and (ai + bi) are repeated expressions. They are called generate (gi) and propagate (pi):

gi = (ai . bi)
pi = (ai + bi)

We generate a carry ci if ai and bi are both 1s. ci will be a 1 regardless of the carry-in ci-1.

We propagate a carry ci if either ai or bi (or both) is a 1. ci will be a 1 if the carry-in ci-1 is a 1. It may be a 1 even if ci-1 is a 0 - when?

Plumbing analogy taken from the textbook

Using generate and propagate values, we can write the two-bit adder equations as:

c1 = g0 + (p0 . c0)
c2 = g1 + (p1 . g0) + (p1 . p0 . c0)

The propagate values cause carries to "ripple" through the adder. However we can calculate the generate and propagate values at the beginning of the addition operation in parallel and the value of ci does not depend upon the value of ci-1.

The equations get excessively complex and thus slow when implemented in hardware, for carry-lookahead adders of size 16. We can therefore group carry-lookahead adders into smaller units (say 4 bits) and use the same trick of determining generate and propagate values for these 4 bit adders.