Carry-select adder

<h2 id="construction">Construction</h2>
<p>The carry-select adder generally consists of <a href="/facts/Ripple-carry_adder/Bc81gxBD">ripple-carry adders</a> and a <a href="/facts/Multiplexer/lVro0Sfz">multiplexer</a>. Adding two n-bit numbers with a carry-select adder is done with two adders (therefore two ripple-carry adders), in order to perform the calculation twice, one time with the assumption of the carry-in being zero and the other assuming it will be one. After the two results are calculated, the correct sum, as well as the correct carry-out, is then selected with the multiplexer once the correct carry-in is known.
</p><p>The number of bits in each carry select block can be uniform, or variable. The optimal delay occurs when variable size of the blocks is applied<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> 
  
    
      
        ⌊
        
          
            n
          
        
        ⌋
      
    
    {\displaystyle \lfloor {\sqrt {n}}\rfloor }
  
.  When variable, the block size should have a delay, from addition inputs A and B to the carry out, equal to that of the multiplexer chain leading into it, so that the carry out is calculated just in time. The 
  
    
      
        O
        (
        
          
            n
          
        
        )
      
    
    {\displaystyle O({\sqrt {n}})}
  
 delay is derived from uniform sizing, where the ideal number of full-adder elements per block is equal to the square root of the number of bits being added, since that will yield an equal number of MUX delays.
</p>
<h3>Basic building block</h3>
<p>Above is the basic building block of a carry-select adder, where the block size is 4. Two 4-bit ripple-carry adders are multiplexed together, where the resulting carry and sum bits are selected by the carry-in. Since one ripple-carry adder assumes a carry-in of 0, and the other assumes a carry-in of 1, selecting which adder had the correct assumption via the actual carry-in yields the desired result.
</p>
<h3>Uniform-sized adder</h3>
<p>A 16-bit carry-select adder with a uniform block size of 4 can be created with three of these blocks and a 4-bit ripple-carry adder. Since carry-in is known at the beginning of computation, a carry select block is not needed for the first four bits. The delay of this adder will be four full adder delays, plus three MUX delays.
</p>
<h3>Variable-sized adder</h3>
<p>A 16-bit carry-select adder with variable size can be similarly created. Here we show an adder with block sizes of 2-2-3-4-5, this is the special type of Variable-sized carry select adder, called as square root carry select adder.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> This break-up is ideal when the full-adder delay is equal to the MUX delay, which is unlikely. The total delay is two full adder delays, and four mux delays. We try to make the delay through the two carry chains and the delay of the previous stage carry equal.
</p>
<h3>Conditional sum adder</h3>
<p>A conditional sum adder<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> is a recursive structure based on the carry-select adder.  In the conditional sum adder, the MUX level chooses between two <i>n/2</i>-bit inputs that are themselves built as conditional-sum adder.  The bottom level of the tree consists of pairs of 2-bit adders (1 half adder and 3 full adders) plus 2 single-bit multiplexers.
</p><p>The conditional sum adder suffers from a very large <a href="/facts/Fan-out/lCm5joyw">fan-out</a> of the intermediate carry outputs. The fan out can be as high as <i>n/2</i> on the last level, where 
  
    
      
        
          c
          
            n
            
              /
            
            2
            −
            1
          
        
      
    
    {\displaystyle c_{n/2-1}}
  
 drives all multiplexers from 
  
    
      
        
          s
          
            n
            
              /
            
            2
          
        
      
    
    {\displaystyle s_{n/2}}
  
 to 
  
    
      
        
          s
          
            n
            −
            1
          
        
      
    
    {\displaystyle s_{n-1}}
  
.
</p>
<h2 id="combining-with-other-adder-structures">Combining with other adder structures</h2>
<p>The carry-select adder design can be complemented with a <a href="/facts/Carry-lookahead_adder/tqVWGB7d">carry-lookahead adder</a> structure to generate the MUX inputs, thus gaining even greater performance as a parallel prefix adder while potentially reducing area.
</p><p>An example is shown in the <a href="/facts/Kogge%25E2%2580%2593Stone_adder/5t7JbWQA">Kogge–Stone adder</a> article.
</p>
<h2 id="further-reading">Further reading</h2>
<ul><li> Savard, John J. G. (2018) [2006]. <a href="http://www.quadibloc.com/comp/cp0202.htm">"Advanced Arithmetic Techniques"</a>. <i>quadibloc</i>. <a href="https://web.archive.org/web/20180703001722/http://www.quadibloc.com/comp/cp0202.htm">Archived</a> from the original on 2018-07-03. Retrieved 2018-07-16.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>V. G. Oklobdzija and E. R. Barnes, "Some Optimal Schemes For ALU Implementation In VLSI Technology", Proceedings of the 7th Symposium on Computer Arithmetic ARITH-7, pp. 2-8. Reprinted in Computer Arithmetic, E. E. Swartzlander, (editor), Vol. II, pp. 137-142, 1985. <a href="https://www.acsel-lab.com/Publications/Papers/11-ALU-VLSI-ARITH85.pdf" target="_blank">https://www.acsel-lab.com/Publications/Papers/11-ALU-VLSI-ARITH85.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>V. G. Oklobdzija and E. R. Barnes, "On Implementing Addition in VLSI Technology", IEEE Journal of Parallel and Distributed Computing, No. 5, pp. 716-728, 1988. <a href="https://www.acsel-lab.com/Publications/Papers/15-add-Vlsi-pdc88.pdf" target="_blank">https://www.acsel-lab.com/Publications/Papers/15-add-Vlsi-pdc88.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Conditional-Sum Addition Logic. Sklansky J. IRE Transaction on Electronic Computer. 1960. p.226. <a href="http://bwrcs.eecs.berkeley.edu/Classes/icdesign/ee241_s10/Readings/Sklansky60.pdf" target="_blank">http://bwrcs.eecs.berkeley.edu/Classes/icdesign/ee241_s10/Readings/Sklansky60.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
</ol>

Carry-select adder open-in-new

Carry-select adder