The addition of two multidigit numbers is based on two intermediate results: the sum and the carry. The sum is the addition result of the operand digits at a particular bit. The carry is the result of a sum being larger than can be held in a single digit, resulting in a term which must be added to the succeeding sum. Therefore the critical path of an addition unit is typically the carry, since for each bit it depends on all previous bits and thus the carry out of the adder depends on every operand bit [HWAN79].
Ripple carry is the simplest form of addition carry, coming straight from the definition of addition. It consists of two singledigit additions per bit as shown in Figure 21. For each bit, the operands are "halfadded", the lowest digit of the result being the sum and the rest being a carry. The carry is then added to the sum of the next bit, producing the addition result. This mechanism of adding the carry at one position to the sum at the next position creates the next carry. The carry signals are said to "ripple" from one bit to the next. The logical structure needed at each bit, as well as the interconnections between bits, are identical. The time to produce all result digits and the necessary circuit area are linear functions of time.

Improvements on carry times involve computation over groups and generating intermediate results in parallel. Carryselect [BEDR62] in Figure 22 is based on computing carries over specific groups of bits based on assumed inputs that are generated in parallel. The carry out of one group is the carry in of the succeeding group. For each group, two sets of the carrycomputation circuitry is included, one assuming a carry in of one, the other a carry in of zero. When the carryin from the previous group is determined, the proper carry for the current group is selected. All of the "assumed carry" values can be generated in parallel, and then the proper alternatives selected in turn when the carryin is applied.
Carry lookahead [BREN82] uses a tree structure to parallelize carry generation. The tree structure is based on two intermediate signals the, "carry propagate" and the "carry generate". If the generate signal at a position is asserted, there is an unconditional carry out at that position, i.e. a carry is "generated" at that point. If the propagate is asserted, the carry out follows the carry in, i.e. a carry is "propagated" though that circuit. Carry lookahead is shown in Figure 23. When units creating generate and propagate signals are combined into groups, like in Figure 24, the generate for the group is asserted if any unit has its generate asserted and all subsequent propagates are asserted. The group propagate is asserted if all unit propagates are asserted.
Carryskip, in Figure 25, is based on computing carries for groups of bits in parallel, like for carryselect. The underlying property is that for any group of bits, either the carryout is generated solely by the current group or it is solely propagated from the previous group, but not both. If for each bit the propagate signal (see carry lookahead) is true but the generate signal is not, then the carryout is equal to the carry in. In all other cases, the carry out can be computed solely from the bits in the group.
