Lookahead Carry

A carry-lookahead 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 carry-lookahead adder it is useful to look at a simpler hierarchical circuit for a comparator.

An m-bit comparator has two m-bit inputs, X and Y. It has two 1-bit outputs:

A hierarchical circuit is defined recursively. For a hierarchical comparator, we assume that we can build an m-bit comparator. From 4 m-bit comparators and some additional circuitry we define how to build a 4m-bit 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 1-bit comparator) that terminates the recursion.

The 4m-bit comparator has 4m-bit inputs, X and Y. We can split these into four m-bit groups:

We route the Xis and the Yis into separate m-bit 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.

Comparison Combiner Unit

Now we need to determine logic equations for the Comparison Combiner Unit.

EQ Output

What is the logic equation for the EQ output?

Answer

Two 4m-bit numbers are equal precisely when each of their corresponding m-bit groups are equal.

EQ = EQ3•EQ2•EQ1•EQ0

GT Output

What is the logic equation for the GT output?

Answer

A 4m-bit number X is greater than a 4m-bit number Y when any one of the m-bit groups of X is greater than the corresponding m-bit group of Y and the higher-order groups of X are equal to the corresponding higher-order groups of Y.

GT = GT3 + EQ3•GT2 + EQ3•EQ2•GT1 + EQ3•EQ2•EQ1•GT0

Comparator Base Case

The base case 1-bit comparator has 1-bit inputs, X and Y. We need to generate the EQ and GT outputs.

The EQ Output

What is the logic equation for the EQ output?

Answer

1-bit numbers X and Y are equal when both are 1 or both are 0.

EQ = X•Y + XY = X ⊕ Y

The GT Output

What is the logic equation for the GT output?

Answer

The 1-bit number X is greater than the 1-bit number X only when X is 1 and Y is 0.

GT = X•Y

Note

To compare signed numbers the only thing that needs to change is the 1-bit comparator GT output for the high-order (sign) bit:

GT = X•Y

  • The base case is a 1-bit comparator (blue dot).
  • Take four 1-bit comparators and connect their outputs into a comparison combiner unit (green dot). This gives you a 4-bit comparator.
  • Take four 4-bit comparators and connect their outputs into a comparison combiner unit. This gives you a 16-bit comparator.
  • Take four 16-bit comparators and connect their outputs into a comparison combiner unit. This gives you a 64-bit comparator.

An m-bit adder has two m-bit inputs, X and Y and a 1-bit 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 m-bit 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 1m denote the m-bit number whose bits are all 1. This number is critical for determining the effects on carries:

  • X + Y > 1m:

    The group generates a carry. There is always a carry out even if there is no carry in.

  • X + Y = 1m:

    The group propagates a carry. There is a carry out only if there is a carry in.

  • X + Y < 1m:

    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 1m. 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,

  • instead of comparing X + Y and 1m
  • we compare X and 1m - Y.

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 m-bit number from 1m you never get any borrows. In fact 1m - Y is just Y, the bitwise complement of Y.

So here is how we get carry information from a comparison. X and Y denote m-bits numbers, generally corresponding groups of bits from larger numbers, and Y denotes the bitwise complement of Y.

  • X > Y:

    The group generates a carry. There is always a carry out even if there is no carry in.

  • X = Y:

    The group propagates a carry. There is a carry out only if there is a carry in.

  • X < Y:

    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 m-bit sum comparator has two m-bit inputs X and Y and two 1-bit outputs:

  • P (propagate) is 1 when the sum of the X and Y inputs is equal to 1m and P is 0 when the sum is less than 1m. We do not care what the output is when the sum is greater than 1m — that is handled by the G output.
  • G (generate) is 1 when the sum of the X and Y inputs is strictly greater than 1m, else G is 0.

Like the ordinary comparator, we need to specify how to build a 4m-bit sum comparator from four m-bit sum comparators and some additional circuitry, and we need to describe the base case 1-bit sum comparator.

Sum Comparator Reduction

For the sum comparator, we assume that we can build an m-bit sum comparator. From these building blocks we define how to build a 4m-bit 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.

P Output

What is the logic equation for the P output?

Answer

The sum of two 4m-bit numbers is equal to 14m precisely when each sum of their corresponding m-bit groups is equal to 1m.

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.

G Output

What is the logic equation for the G output?

Answer

The sum of two 4m-bit number X and Y is greater than 14m when the sum for any one of the m-bit groups is greater than 1m and the sums for the higher-order groups of X and Y are equal to 1m.

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.

Adder Structure

We can define an m-bit adder in a recursive manner similar to an m-bit 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.

Carry Outputs

We need to determine the logic equations for the carry outputs.

The C1 Output

What is the logic equation for C1 output?

Answer

A carry is needed into the second m-bit only if one of two conditions is met.

  • The first adder generates a carry.
  • There is a carry into the first adder and it propagates through the first adder.

C1 = G0 + P0 • C0

The Other Outputs

The logic equations for the other carry outputs are left as an exercise.

Full Adder Modifications

The base case 1-bit 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.

  • EQ is true when X = Y

    EQ = X•Y + XY

  • P is true when X = Y

    P = X•Y + X•Y = X ⊕ Y

  • GT is true when X > Y

    GT = X•Y

  • G is true when X > Y

    G = X•Y

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 full adders (FA) are modified so that they generate P and G outputs instead of a carry out. Their X and Y inputs and their S output are not shown.
  • The P and G outputs of four 1-bit adders are connected into a carry lookahead unit and the carry outputs of the carry lookahead unit are connected back to the 1-bit adders. This gives you a 4-bit adder as in the four full adders and the carry lookahead unit at the upper right of the diagram.
  • The P and G outputs of four 4-bit adders are connected into a carry lookahead unit and the carry outputs of the carry lookahead unit are connected back to the 4-bit adders. This gives you a 16-bit adder.

Performance Improvement

Even in a 4-bit adder, carry lookahead leads to a performance improvement. In a 4-bit ripple-carry adder the outputs are not ready until after 8 gate delays. For a 4-bit carry-lookahead adder:

  • All 1-bit adder P and G outputs are ready after 1 gate delay.
  • The carry lookahead unit outputs are ready after 2 more gate delays. Some of these outputs are fed into the 1-bit adder Ci inputs.
  • The 1-bit adder S outputs are ready after 2 more gate delays.

Thus outputs of the carry-lookahead adder are ready after only 5 gate delays.

For 16-bit ripple-carry adders the outputs are not ready until after 32 gate delays. For 16-bit carry-lookahead adders 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 1-bit adders. Thus outputs of the carry-lookahead adder are ready after only 9 gate delays.

This performance boost can be obtained with only about a 50-70% 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.