Carry-lookahead adder

The parallel adder with look ahead carry or carry-look - ahead adder (short: CLA adder ) is a logic circuit for adding multi-digit binary numbers (see also adder ).

The CLA adder adds two n- digit binary numbers, so has 2 · n inputs, as well as usually via a further carry input. Since the result may contain a possible carry-over, there are n 1 outputs. The advantage of the CLA adder, the delay of the circuit is only logarithmically with the number of its inputs, wherein at the same time only the number of linear logic gates in terms of the number of its inputs. Its complexity is in the Landau notation that is expressed for the delay circuit and the circuit size. The CLA adder is so fast as a Conditional Sum adder whose delay is also, and needs at the same time similar to a carry-ripple adder only a few components. However Conditional Sum adder need compared with the CLA adder more components, carry-ripple adders have an exponentially greater delay from to. The CLA adder is, however, asymptotically fast and cheap at the same time.

Operation

The CLA adder is a special application of a parallel prefix computation which can be implemented by a circuit with cost and delay. To make the refined application of the parallel prefix computation easier to understand, their application is first presented on the example of a fast incrementer.

Fast incrementer by CLA -Art

An incrementer added to a - digit binary number and the value has inputs and outputs, and an additional output for a possible transfer at the highest priority.

A carry from place to occurs in this case only if all, that is, when advocating the transfer. Therefore, the incrementer for each result bit if and only if either propagate or for.

Using a parallel prefix computation can "propagate" for all the functions simultaneously compute by exploiting that the logical AND function is an associative binary operation on binary numbers.

Parallel prefix computation

To each associative two -digit shortcut to a set is its parallel -digit prefix function defined as follows:

With for

As circuit can be recursively constructed from:

For then shall be:

Example: for thus shall

CLA adder

Be and the digits of the two numbers to be added and the input carry. Is referred to with the carry from place to place. Then, for the -th to be calculated sum bit. If all carry bits are known, can be calculate in parallel, with constant circuit delay and linear component costs.

To calculate, it is not enough to consider only whether the input carry is propagated as the incrementer. As a carry is propagated to the - th position, when either or, further, a carry is generated when.

One writes if the- th position propagates a carry:

Next one writes if the- th position generates a carry:

Both propagation and generation can be no knowledge of the unearned charge!

To all carry-outs at the same time to compute efficiently, we define an associative link ( proof of associativity by recalculation) that can be used in a parallel prefix computation:

The two components explained as follows. It is the transfer, if the - th digit generated or if the - th digit and propagating the - th digit has a carry-over, that is, when. Successive points propagate together a carry when. The link is therefore suitable to all be calculated as follows; which are purely auxiliary variables:

. or in other words:

With the now present intermediate results can finally be the sum of and easy to calculate. The following applies: