2. Historical review: Role of the "carry"

The addition of two multi-digit 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].

2.1 Ripple Carry

Ripple carry is the simplest form of addition carry, coming straight from the definition of addition. It consists of two single-digit additions per bit as shown in Figure 2-1. For each bit, the operands are "half-added", 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.

FIGURE 2-1: Ripple Carry

 

2.2 Carry select

Improvements on carry times involve computation over groups and generating intermediate results in parallel. Carry-select [BEDR62] in Figure 2-2 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 carry-computation circuitry is included, one assuming a carry in of one, the other a carry in of zero. When the carry-in 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 carry-in is applied.

FIGURE 2-2: Carry Select Adder

 

2.3 Carry look-ahead

Carry look-ahead [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 look-ahead is shown in Figure 2-3. When units creating generate and propagate signals are combined into groups, like in Figure 2-4, 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.

FIGURE 2-3: Flat Carry Look-ahead

 

FIGURE 2-4: Block Carry Look-ahead

 

2.4 Carry skip

Carry-skip, in Figure 2-5, is based on computing carries for groups of bits in parallel, like for carry-select. The underlying property is that for any group of bits, either the carry-out 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 look-ahead) is true but the generate signal is not, then the carry-out is equal to the carry in. In all other cases, the carry out can be computed solely from the bits in the group.

FIGURE 2-5: Carry-skip