Parallel adder with carry precalculation

4-bit carry-look-ahead adder with carry-in and carry-out

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

The CLA adder adds two n-digit binary numbers, so it has 2 · n inputs and, as a rule, an additional carry input . Since the result may include a carry, there are n + 1 outputs. The advantage of the CLA adder is that the delay of the circuit is only logarithmic to the number of its inputs, with only a linear number of logic gates measured by the number of its inputs. Expressed in Landau notation , its complexity is therefore for the circuit delay and for the circuit size . The CLA adder is therefore as fast as a conditional sum adder , whose delay is also , and at the same time, similar to a carry ripple adder , requires only a few components. Compared to the CLA adder, however, conditional sum adders need more components, and carry ripple adders have an exponentially greater delay of . The CLA adder, on the other hand, is asymptotically fast and cheap at the same time. ${\displaystyle {\mathcal {O}}(\log(n))}$ ${\displaystyle {\mathcal {O}}(n)}$ ${\displaystyle {\mathcal {O}}(\log(n))}$ ${\displaystyle {\mathcal {O}}(n)}$ ${\displaystyle {\mathcal {O}}(n^{\log _{2}(3)})}$ ${\displaystyle {\mathcal {O}}(n)}$

idea

An adder can perform most of its calculations even if the incoming carry is not yet available. To do this, the two summands are first added without taking them into account. The result can then be seen directly what effect the incoming transfer will have on the outgoing one. The table shows the relationship using the example of a 4-bit adder.

Relationship between incoming and outgoing transfers of a 4-bit adder

Total without taking the incoming carry forward into account	more detailed	outgoing	comment
	transfer
0 0000 to 0 1110	any	0	The incoming carry is absorbed .
0 1111	0	0	The incoming carry is propagated unchanged .
	1	1
1 0000 to 1 1110	any	1	A carry is always generated .

Each adder indicates at a special output whether it will absorb, propagate or generate the incoming carry. This special output replaces the carry output of an ordinary adder. The actual carry can then easily be calculated from this information and the incoming carry. The great advantage of this special output is that it can be hierarchically combined with just a few logic gates without having to recalculate the total or know the actual carry, as the following table shows.

Combination of two adding units to form a wider adding unit

higher quality adder	low-order adder	combined adder
absorbed	any	absorbed
generated	any	generated
propagated	absorbed	absorbed
	generated	generated
	propagated	propagated

functionality

The CLA adder is a special application of a parallel prefix calculation which can be implemented by a circuit with costs and delay . In order to make the ingenious application of the parallel prefix calculation easier to understand, its application will first be explained using the example of a fast incrementer . ${\displaystyle \operatorname {PP} _{n}^{\circ }}$ ${\displaystyle {\mathcal {O}}(n)}$ ${\displaystyle {\mathcal {O}}(\log(n))}$

Fast CLA-style incrementer

An incrementer adds the value to a -digit binary number and has inputs as well as outputs and a further output for a possible carry with the highest priority. ${\displaystyle \operatorname {Inc} _{n}}$ ${\displaystyle n}$ ${\displaystyle 1}$ ${\displaystyle n}$ ${\displaystyle n}$

${\displaystyle \operatorname {Inc} _{n}\colon \{0,1\}^{n}\to \{0,1\}^{n+1}}$

${\displaystyle \operatorname {Inc} _{n}(x_{n-1}\ldots x_{0})=(y_{n}\ldots y_{0})}$

A carryover from position to only occurs when all are, i.e. H. when they propagate the transfer . In the case of the incrementer, the following applies for each result bit if and only if either propagate or for . ${\displaystyle i}$ ${\displaystyle i+1}$ ${\displaystyle x_{0}=\ldots =x_{i}=1}$ ${\displaystyle x_{0}\ldots x_{i}}$ ${\displaystyle y_{i+1}=1}$ ${\displaystyle x_{0}\ldots x_{i}}$ ${\displaystyle x_{i+1}=1}$ ${\displaystyle 0\leq i<n}$

Using a parallel prefix calculation , one can calculate the functions " propagate" at the same time by taking advantage of the fact that the logical AND function is an associative two-digit link on the binary numbers. ${\displaystyle \operatorname {PP} _{n}^{\wedge }}$ ${\displaystyle i}$ ${\displaystyle x_{0}\ldots x_{i}}$ ${\displaystyle =x_{0}\wedge x_{1}\wedge \ldots \wedge x_{i}}$ ${\displaystyle \wedge }$

Parallel prefix calculation

For each associative two-digit link on a set , its -digit parallel prefix function is defined as follows: ${\displaystyle {\circ }\colon A\times A\to A}$ ${\displaystyle A}$ ${\displaystyle n}$ ${\displaystyle \operatorname {PP} _{n}^{\circ }}$

${\displaystyle \operatorname {PP} _{n}^{\circ }\colon A^{n}\to A^{n}}$

${\displaystyle \operatorname {PP} _{n}^{\circ }(x_{n-1}\ldots x_{0})=(y_{n-1}\ldots y_{0})}$with for ${\displaystyle y_{i}=x_{i}\circ \ldots \circ x_{0}}$ ${\displaystyle 0\leq i<n}$

The circuit can be constructed recursively from : ${\displaystyle \operatorname {PP} _{2n}^{\circ }}$ ${\displaystyle \operatorname {PP} _{n}^{\circ }}$

${\displaystyle \operatorname {PP} _{1}^{\circ }(x_{0})=(y_{0})=(x_{0})}$

For was then: ${\displaystyle \operatorname {PP} _{2n}^{\circ }(x_{2n-1},\ldots ,x_{0})=(y_{2n-1},\ldots ,y_{0})}$ ${\displaystyle (y'_{n-1},\ldots ,y'_{0})=\operatorname {PP} _{n}^{\circ }(x_{2n-1}\circ x_{2n-2},\ldots ,x_{1}\circ x_{0})}$

${\displaystyle y_{2i+1}=y'_{i}}$ For ${\displaystyle 0\leq i<n}$

${\displaystyle y_{2i}=y'_{i-1}\circ x_{2i}}$ For ${\displaystyle 0<i<n}$

${\displaystyle y_{0}=x_{0}}$

Example: therefore applies to ${\displaystyle n=2}$ ${\displaystyle \operatorname {PP} _{2}^{\circ }(x_{1},x_{0})=(y_{1},y_{0})=(x_{1}\circ x_{0},x_{0})}$

CLA adder

Let and be the digits of the two numbers to be added and the input carry. With denotes the carry bit from place to place . Then applies to the -th sum bit to be calculated . If all carry bits are known, they can be calculated in parallel, with constant switching delay and linear component costs. ${\displaystyle a_{0}\ldots a_{n-1}}$ ${\displaystyle b_{0}\ldots b_{n-1}}$ ${\displaystyle c_{-1}}$ ${\displaystyle c_{i}}$ ${\displaystyle i}$ ${\displaystyle i+1}$ ${\displaystyle i}$ ${\displaystyle s_{i}=a_{i}}$ ${\displaystyle \oplus }$ ${\displaystyle b_{i}\oplus c_{i-1}}$ ${\displaystyle c_{i}}$ ${\displaystyle s_{i}}$

In order to calculate this, it is not enough to check whether the input carry is being propagated, as with the incrementer. Because a carry is propagated at the -th place if either or are, a carry is still generated if . ${\displaystyle c_{i}}$ ${\displaystyle i}$ ${\displaystyle a_{i}=1}$ ${\displaystyle b_{i}=1}$ ${\displaystyle a_{i}=b_{i}=1}$

If the -th digit propagates a carry, you write : ${\displaystyle p_{i}=p_{i}(a,b)}$ ${\displaystyle i}$

${\displaystyle p_{i}=a_{i}\oplus b_{i}}$ For ${\displaystyle 0\leq i<n}$

If the -th digit generates a carry , you also write : ${\displaystyle g_{i+1}=g_{i+1}(a,b)}$ ${\displaystyle i}$

${\displaystyle g_{i}=a_{i}\wedge b_{i}}$ For ${\displaystyle 0\leq i<n}$

Both propagating and generating can be calculated without knowing the carries ! ${\displaystyle c_{j},j\leq i}$

To all transfers for calculating at the same time efficiently, one defines an associative link (proof associativity by recalculation) which are in a parallel prefix computation can use: ${\displaystyle c_{i}}$ ${\displaystyle 0\leq i<n}$ ${\displaystyle \circ \colon \{0,1\}^{2}\times \{0,1\}^{2}\to \{0,1\}^{2}}$

${\displaystyle (g',p')\circ (c,p)=(g'\vee p'\wedge c,p\wedge p')}$

The two components are explained as follows. It is the carry-over if the -th position generates or if the -th position propagates and the -th position has a carry-over, i.e. if . Successive passages together propagate a carryover if is. The link is therefore suitable for calculating all of them as follows; they are pure auxiliary variables: ${\displaystyle c_{i}=1}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle i-1}$ ${\displaystyle g_{i}\vee p_{i}\wedge c_{i-1}}$ ${\displaystyle i,i-1}$ ${\displaystyle p_{i}\wedge p_{i-1}=1}$ ${\displaystyle \circ }$ ${\displaystyle c_{i}}$ ${\displaystyle d_{i}}$

${\displaystyle (c_{i},d_{i})=(g_{i},p_{i})\circ \ldots \circ (g_{0},p_{0})\circ (c_{-1},1)}$, or in other words:

${\displaystyle ((c_{n-1},d_{n-1}),\ldots ,(c_{-1},d_{-1}))=\operatorname {PP} _{n+1}^{\circ }((g_{n-1},p_{n-1}),\ldots ,(g_{0},p_{0}),(c_{-1},1))}$

With the intermediate results now available, the sum of and can finally be easily calculated. The following applies: ${\displaystyle s}$ ${\displaystyle a}$ ${\displaystyle b}$

${\displaystyle s_{i}=p_{i}\oplus c_{i-1}}$ For ${\displaystyle 0\leq i<n}$

${\displaystyle s_{n}=c_{n-1}}$

literature

• Jörg Keller, Wolfgang J. Paul: Hardware Design. Formal design of digital circuits Teubner 1995/2005, ISBN 3-519-23047-X .

Web links

• Detailed introduction to the Flensburg University of Applied Sciences