A carrylookahead adder replaces ripple carry generation with lookahead carry generation. Lookahead carry generation is based on a hierarchical arrangement of carry lookahead units. Before describing a carrylookahead adder it is useful to look at a simpler hierarchical circuit for a comparator.
An mbit comparator has two mbit inputs, X and Y. It has two 1bit outputs:
A hierarchical circuit is defined recursively. For a hierarchical comparator, we assume that we can build an mbit comparator. From 4 mbit comparators and some additional circuitry we define how to build a 4mbit comparator.
Like any recursion, we need to specify how to reduce a larger problem to smaller ones (describe the interconnections and the additional circuitry) and define a base case (a 1bit comparator) that terminates the recursion.
The 4mbit comparator has 4mbit inputs, X and Y. We can split these into four mbit groups:
We route the Xis and the Yis into separate mbit comparators and introduce a circuit block to combine their results:
Before proceeding to the base case, we need to figure out the logic equations for the combiner.
Now we need to determine logic equations for the Comparison Combiner Unit.
What is the logic equation for the EQ output?
Two 4mbit numbers are equal precisely when each of their corresponding mbit groups are equal.
EQ = EQ3•EQ2•EQ1•EQ0
What is the logic equation for the GT output?
A 4mbit number X is greater than a 4mbit number Y when any one of the mbit groups of X is greater than the corresponding mbit group of Y and the higherorder groups of X are equal to the corresponding higherorder groups of Y.
GT = GT3 + EQ3•GT2 + EQ3•EQ2•GT1 + EQ3•EQ2•EQ1•GT0
The base case 1bit comparator has 1bit inputs, X and Y. We need to generate the EQ and GT outputs.
What is the logic equation for the EQ output?
1bit numbers X and Y are equal when both are 1 or both are 0.
EQ = X•Y + X•Y = X ⊕ Y
What is the logic equation for the GT output?
The 1bit number X is greater than the 1bit number X only when X is 1 and Y is 0.
GT = X•Y
To compare signed numbers the only thing that needs to change is the 1bit comparator GT output for the highorder (sign) bit:
GT = X•Y
An mbit adder has two mbit inputs, X and Y and a 1bit Ci (carry in) input. It uses m modified full adders The basic idea for lookahead carry generation is to use an augmented comparator to generate all of the carry ins for the adders. We will first look at how to get carry information from a comparison. Then we will look at the overall structure of an m bit adder and the modifications of the full adders needed to use lookahead carry.
Suppose we are adding two mbit numbers X and Y. Generally X and Y may be corresponding groups of bits from larger numbers. We would like to be able to to determine the effects of adding X and Y on carries in the larger numbers. Let 1_{m} denote the mbit number whose bits are all 1. This number is critical for determining the effects on carries:
The group generates a carry. There is always a carry out even if there is no carry in.
The group propagates a carry. There is a carry out only if there is a carry in.
The group cannot have a carry out, even if there is a carry in.
That is, we can get carry information from a comparison between X + Y and 1_{m}. But we still have an addition which involves carries, so this observation has not yet helped us.
Suppose we try subtracting Y from both numbers to be compared. That is,
At first glance this only appears to convert the problem from an addition with carries into a subtraction with borrows. However, when you subtract an mbit number from 1_{m} you never get any borrows. In fact 1_{m}  Y is just Y, the bitwise complement of Y.
So here is how we get carry information from a comparison. X and Y denote mbits numbers, generally corresponding groups of bits from larger numbers, and Y denotes the bitwise complement of Y.
The group generates a carry. There is always a carry out even if there is no carry in.
The group propagates a carry. There is a carry out only if there is a carry in.
The group cannot have a carry out, even if there is a carry in.
The carry lookahead circuitry starts as a sum comparator. Then circuitry is added for carry generation. An mbit sum comparator has two mbit inputs X and Y and two 1bit outputs:
Like the ordinary comparator, we need to specify how to build a 4mbit sum comparator from four mbit sum comparators and some additional circuitry, and we need to describe the base case 1bit sum comparator.
For the sum comparator, we assume that we can build an mbit sum comparator. From these building blocks we define how to build a 4mbit sum comparator. The organization of the circuitry is the same as an ordinary comparator. We just need to determine logic equations for the sum comparator combiner unit.
What is the logic equation for the P output?
The sum of two 4mbit numbers is equal to 1_{4m} precisely when each sum of their corresponding mbit groups is equal to 1_{m}.
P = P3•P2•P1•P0
This has the same form as the ordinary comparator logic equation for EQ. And it does not require computing any sums.
What is the logic equation for the G output?
The sum of two 4mbit number X and Y is greater than 1_{4m} when the sum for any one of the mbit groups is greater than 1_{m} and the sums for the higherorder groups of X and Y are equal to 1_{m}.
G = G3 + P3•G2 + P3•P2•G1 + P3•P2•P1•G0
This has the same form as the ordinary comparator logic equation for GT. Again, it does not require computing any sums.
We can define an mbit adder in a recursive manner similar to an mbit comparator. In the reduction case, m > 1, it uses a modified comparison combiner unit, which is called a carry lookahead unit. The reduction is shown in the following diagram.
The EQ and GT inputs and outputs of the comparison combiner unit are renamed to Ps and Gs, respectively, to reflect their role in lookahead carry generation. A carry lookahead unit also has carry outputs, C4, C3, C2, and C1, that are ultimately fed back to the base case adders. We need to develop the logic equations for these outputs.
We need to determine the logic equations for the carry outputs.
What is the logic equation for C1 output?
A carry is needed into the second mbit only if one of two conditions is met.
C1 = G0 + P0 • C0
The logic equations for the other carry outputs are left as an exercise.
The base case 1bit adder is a modified full adder. Its carry output and associated circuitry are removed and replaced by circuitry to generate outputs for base case comparison between X and Y. The logic equations can be obtained by substituting Y for Y in the comparator base case equations.




If the carry lookahead circuitry is only used for carry lookahead and not for comparison then can simplify the logic equation for P. We can allow it to be 1 when X and Y are both 1. This computes P with a simple OR gate.
P = X + Y
The justification for this change is that it does not affect P outputs in the carry lookahead unit tree except when a corresponding G output is 1. In effect, it allows carries to be incorrectly propagated, but only when a carry would be generated anyway.
The diagram to the left show the symbol for a carry lookahead full adder. The diagram below shows its implementation.
This implementation is suitable for implementing an ALU which uses carry lookahead circuitry for generating comparison outputs in addition to sums and differences.
Extending to modern processors with 64bit words is similar. It just involves using four 16bit adders, combining their P and G outputs with a single additional lookaheadcarry unit.
Even in a 4bit adder, carry lookahead leads to a performance improvement. In a 4bit ripplecarry adder the outputs are not ready until after 8 gate delays. For a 4bit carrylookahead adder:
Thus outputs of the carrylookahead adder are ready after only 5 gate delays.
For a 16bit ripplecarry adder, the outputs are not ready until after 32 gate delays. For a 16bit carrylookahead adder, there is one additional level of carry lookahead units. The carry signals are only delayed an additional 4 gate delays: 2 on the way towards the root of the carry lookahead unit tree and 2 more on the way back to the 1bit adders. Thus outputs of the carrylookahead adder are then ready after only 9 gate delays.
Considering 64bit addition typical of modern processors, for a 64bit ripplecarry adder the outputs are not ready until after 128 gate delays. For a 64bit carrylookahead adder, there is one additional level of carry lookahead units. Their carry signals are only delayed an additional 4 gate delays. Thus outputs of the carrylookahead adder are ready after only 13 gate delays — almost 10 times faster than a ripplecarry adder.
This performance boost can be obtained with only about a 5070% increase in the number of transistors. If the adder is on a critical path that determines the cycle time the benefits are well worth the cost.