Carry look-ahead adder

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.

Run Review see Project * Alone

Explaining the delays in the ripple wave carry adder

This article describes carry look-ahead adder that is free from this problem.

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:

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:

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

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:

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 after we already know . However we can now substitute . For instance, for the four digit adder, the carry signals can be computed from formulas

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

Substitions

yield to:

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

Run Review see Project * Alone

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.

Ripple-block carry look-ahead adder

As there is increasingly difficult to compute carry bits for the higher digits, it may be reasonable to use intermediate design, where several carry look-ahead adders are connected into chain. Each adder processes some reasonable number of bits (say four) and uses the carry look-ahead circuits internally. However it obtains the carry bit value from the lower digit (if any) and itself outputs the carry bit for the higher digit. Hence the carry bit propagates between the multiple bit adders same way as in the simple ripple wave carry adder it propagates between single bit adders. This design has intermediate speed and complexity.

Run Review see Project * Alone

Ripple-block carry look-ahead adder, consisting from the pair of two digit blocks. The carry signal between the blocks is marked as carry bit. Having the same functionality as the previous circuit, this implementation is simpler. It is slower but still faster than the plain ripple wave adder.

Block carry look-ahead adder

Another approach is to use ripple wave carry adders inside 4-bit (or similar) size blocks but use additional circuits to compute if carry bits of these blocks (without waiting the carry bit value to appear in the block output).

References

1. ¹ Hardware algorithms
2. ² Verilog implementation of the Carry look-ahead adder (source code of the algorithm)