Carry-lookahead adder
A carry-lookahead adder improves speed by reducing the amount of time required to determine carry bits.
The carry-lookahead adder calculates one or more carry bits before the sum, which reduces the wait time to calculate the result of the larger-value bits of the adder.
Already in the mid-1800s, Charles Babbage recognized the performance penalty imposed by the ripple-carry used in his Difference Engine, and subsequently designed mechanisms for anticipating carriage for his never-built Analytical Engine.
[3] Gerald B. Rosenberger of IBM filed for a patent on a modern binary carry-lookahead adder in 1957.
A binary ripple-carry adder works in the same way as most pencil-and-paper methods of addition.
A 'carry out' may occur if the result requires a higher digit; for example, "9 + 5 = 4, carry 1".
This means that no digit position can have an absolutely final value until it has been established whether or not a carry is coming in from the right.
Moreover, if the sum without a carry is the highest value in the base (9 in base-10 pencil-and-paper methods or 1 in binary arithmetic), it is not possible to tell whether or not a given digit position is going to pass on a carry to the position on its left.
It is the "rippling" of the carry from right to left that gives the ripple-carry adder its name and slowness.
When adding 32-bit integers, for instance, allowance has to be made for the possibility that a carry could have to ripple through every one of the 32 one-bit adders.
Carry-lookahead depends on two things: Supposing that groups of four digits are chosen.
The sequence of events would go like this: The net effect is that the carries start by propagating slowly through each 4-bit group, just as in a ripple-carry system, but then move four times as fast, leaping from one lookahead-carry unit to the next.
Deciding the group size to be governed by lookahead carry logic requires a detailed analysis of gate and propagation delays for the particular technology being used.
Each lookahead-carry unit already produces a signal saying "if a carry comes in from the right, I will propagate it to the left", and those signals can be combined so that each group of, say, four lookahead-carry units becomes part of a "supergroup" governing a total of 16 bits of the numbers being added.
With this kind of two-level implementation, a carry may first propagate through the "slow road" of individual adders, then, on reaching the left-hand end of its group, propagate through the "fast road" of 4-bit lookahead-carry logic, then, on reaching the left-hand end of its supergroup, propagate through the "superfast road" of 16-bit lookahead-carry logic.
For very large numbers (hundreds or even thousands of bits), lookahead-carry logic does not become any more complex, because more layers of supergroups and supersupergroups can be added as necessary.
The increase in the number of gates is also moderate: if all the group sizes are four, one would end up with one third as many lookahead carry units as there are adders.
However, the "slow roads" on the way to the faster levels begin to impose a drag on the whole system (for instance, a 256-bit adder could have up to 24 gate delays in its carry processing), and the mere physical transmission of signals from one end of a long number to the other begins to be a problem.
At these sizes, carry-save adders are preferable, since they spend no time on carry propagation at all.
In the descriptions below, the word digit can be replaced by bit when referring to binary addition of 2.
Due to the way generate and propagate bits are used by the carry-lookahead logic, it doesn't matter which definition is used.
For binary arithmetic, or is faster than xor and takes fewer transistors to implement.
This allows the circuit to "pre-process" the two numbers being added to determine the carry ahead of time.
Then, when the actual addition is performed, there is no delay from waiting for the ripple-carry effect (or time it takes for the carry from the first full adder to be passed down to the last full adder).
The XOR is used normally within a basic full adder circuit; the OR is an alternative option (for a carry-lookahead only), which is far simpler in transistor-count terms.
The numeric value determines the signal from the circuit above, starting from 0 on the far right to 3 on the far left: Substituting
A lookahead-carry unit (LCU) takes these 8 values and uses identical logic to calculate
A standard 16-bit ripple-carry adder would take 16 × 2 − 1 = 31 gate delays.
Below is the expansion: More simple 4-bit carry-lookahead adder: The Manchester carry chain is a variation of the carry-lookahead adder[5] that uses shared logic to lower the transistor count.
One of the major downsides of the Manchester carry chain is that the capacitive load of all of these outputs, together with the resistance of the transistors causes the propagation delay to increase much more quickly than a regular carry lookahead.
