Carry-select adder

The carry-select adder (from English carry carry , select ( select ) select) or CSCA for short is an accelerated adding network that is used to add multi-digit binary numbers .

functionality

Example of a 9-bit carry select adder

The CSCA divides the entire word length n into M blocks .

In the example shown, the block widths are 2, 3 and 4 bits .
It is therefore an addition of two 2 + 3 + 4 = 9-bit binary numbers.

The principle of this adding network can be described with the term “parallelized pre-calculation”, because each of the blocks consists of two carry-ripple adders (CRA for short), which simultaneously perform the calculation for their bit portion of the binary numbers. A carry bit is applied to one of the CRAs (c = 1), while the carry input of the other is set to c = 0. Thus, for each block, both possible cases are calculated in parallel and applied to a multiplexer . This finally switches to the correct solution variant depending on the most significant transfer bit of the previous block, which ideally has already been calculated.

Terms

In order to obtain an optimal runtime , it makes sense to let the arbitrarily variable block word width grow, since this way the calculation in the block is synchronized with the creation of the final transmission bit.

In the following calculation example it is assumed that this is exactly the case when the word width increase corresponds to 1 bit per block (see example).

Total word width = n
Number of blocks = K
Variable block word width = with k = 0.1, ..., K-1 ${\ displaystyle m_ {k}}$
Header word width = ${\ displaystyle m_ {0}}$
Word width increase = [in bit / block] ${\ displaystyle \ sigma _ {m}}$

${\ displaystyle n = \ sum _ {k = 0} ^ {K-1} \, m_ {k} = m_ {0} + (m_ {0} +1) + (m_ {0} +2) +. .. + (m_ {0} + K-1)}$
${\ displaystyle n = K \ cdot m_ {0} + (1 + 2 + ... + K-1) = K \ cdot m_ {0} + K \ cdot {\ frac {K-1} {2}} }$

${\ displaystyle 0 = K ^ {2} + K \ cdot (2m_ {0} -1) -2n}$

${\ displaystyle K = - {\ frac {2m_ {0} -1} {2}} \ pm {\ sqrt {\ left ({\ frac {2m_ {0} -1} {2}} \ right) ^ { 2} + 2n}}}$

Applied to our specific example ( ): ${\ displaystyle n = 9, m_ {0} = 2, \ sigma _ {m} = 1}$

${\ displaystyle K = - {\ frac {3} {2}} + {\ sqrt {{\ frac {9} {4}} + {\ frac {72} {4}}}} = 3}$ (0,1,2 - corresponds to three blocks)

Addition time:

${\ displaystyle \ tau _ {CSCA} (n) = \ tau _ {CRA} (m_ {0}) + (K-1) \ cdot \ tau _ {block}}$

${\ displaystyle \ tau _ {CSCA} (n) = O ({\ sqrt {n}})}$

With

${\ displaystyle \ tau _ {CRA} (n) = \ tau _ {half adder} + (n-1) \ cdot \ tau _ {carry ripple} + \ tau _ {half adder}}$