Carry-lookahead Addition

Carry look ahead addition optimizes the addition circuits. Without carry look ahead addition, ripple adders would be used. Ripple adders take three bits of input a_i, b_i and c_i.

The first two are the addends and the third is the carry bit from the prior adder. The result bit (r_i) is a_i xor b_i xor c_i. The xor operation can be decomposed to x and not y or y and not x. The carry bit (c_i+1) is a_i and b_i or b_i and c_i or c_i and a_i. From the software developer point of view, these subscripts make it easy to "code" this as a for-loop.

The key here is that the ripple adder requires that the carry bit be rippled through the adder. This takes time for the signal to go through all the gates.

The carry look ahead adder uses boolean algebra to create all the carry bits in parallel by using more gates. This allows you to xor a, b, and c together. To generate the carry bits, each bit position can be show to generate a carry bit or propagate a carry bit. The carry bit for any position is c_i = g_i-1 + p_i-1*c_i-1. You can expand this recurrence into an expression that you can then evaluate in roughly O(log n) since logic gates can take two inputs and have the associative and commutative property.

Parallelism here requires significant gate resources. The simple ripple adder has a straight forward software implementation. The carry look ahead adder doesn't. The latter is faster. Is it worth the software complexity if we always had to code things like the carry look ahead adder?