Carry look-ahead adder is the adder design that overcomes the limitations of the Ripple wave adder by computing the carry values directly from the adder input. This is different from the ripple wave adder, each higher section waits till the carry value comes from the lower section, the previous pair of digits. A summary of concept and review of possible optimizations can be found at [1]. Apart wiring diagrams, such devices can be represented as the coded the software algorithms[2].

## Problems with the ripple wave carry adder

Problems of the ripple carry adder become obvious after we add delay elements that simulate delays in the logic gates of each cell. In order to add 1111 and 0001, for instance, the carry wave must propagate through all nodes of the adder. If such adder is used to add 128 bit values, it is more than two orders of magnitude slower than the single node.

Explaining the delays in the ripple wave carry adder

## The G and P signals

### The carry generation signal, G

Carry look-ahead adder is based on the two additional signals that must be computed for every node. The G signal means that the section will generate the carry bit for the next (higher) section, regardless if it gets the carry bit from the lower section or not. This is only true for the combination 1 + 1 = 10, hence the G signal can be computed with AND logic gate:

[[Math:c|G(A,B) = A \cdot B]]

### The carry propagation signals P and P'

The carry propagation signal P' means that the section would not generate the carry bit itself but will pass through the carry bit (if any) from the lower section. This is true for the combinations 1+0 and 0+1, so this is the XOR gate operation:

[[Math:c|P^{\prime}(A,B) = A \oplus B]]

It was noticed that carry look ahead adder also works correctly if the XOR gate is replaced by OR gate (see the formula below):

[[Math:c|\ P(A,B) = A \plus B]]

As a result, the XOR gate is frequently replaced by the faster OR gate.

### Computing the carry value from the propagation signals

The section i will generate the carry signal if

• G is true or
• there is a carry signal from the lower section and P or P' is true:
[[Math:c|C_{i\plus1} = G_i \plus P_i \cdot C_i]]

This formula is stays true if we substitute P by P'. Using this formula, we can compute carry signals without involving adder circuits and immediately supply these signals to adders that require them to perform they operations. This is still not much faster than with the ripple wave adder as we can only start computing [[Math:c|C_i\plus1]] after we already know [[Math:c|C_i]]. However we can now substitute [[Math:c|C_i]]. For instance, for the four digit adder, the carry signals can be computed from formulas

[[Math:c|C_1 = G_1]]
[[Math:c|C_2 = G_2 \plus P_2 \cdot C_1]]
[[Math:c|C_3 = G_3 \plus P_3 \cdot C_2]]

In our example, there is no carry bit for the lowest digit and also we do not compute [[Math:c|C_4]] in accelerated way (it will be available from adder of the highest section roughly at the same time as the value bit anyway).

Substitions

[[Math:c|C_1 \to C_2,\ C_2 \to C_3,\ C_3 \to C_4]]

yield to:

[[Math:c|C_1 = G_1]]
[[Math:c|C_2 = G_2 \plus G_1 \cdot P_2]]
[[Math:c|C_3 = G_3 \plus G_2 \cdot P_3 \plus G_1 \cdot P_2 \cdot P_3]]

This allows us to draw the interactive diagram (likely the most complex diagram in the project):

Carry look-ahead adder. You may need to zoom in with ctrl+ to see the rightmost part of the schema as it is very large. The applet does not zoom, it simply gets the bigger screen area available.

In comparison to the ripple wave adder, it is relatively complex, and the complexity increases rapidly with the number of digits (C1 is relatively easy to compute, C2 is much more complex and C3 is even more sophisticated). However now more gates work in parallel hence this circuit is significantly faster. Also, the adder nodes may now be simpler as they do not need to compute the carry output bit.