Addition circuits

Abstract

A method of designing an addition circuit, and an addition circuit designed according to the method are described. The design technique is optimised to facilitate design of an addition circuit of minimum depth. The design technique takes into account the number of logical stages of the addition circuit and the manner in which those stages are connected by spanning paths to create fan-out nodes. The number of fan-out nodes per level can be optimized. For bit lengths n, the number (m+2) of logical stages is n=2 m+1 and for bit lengths n not of a binary order, the number (m+2) of logical stages is n bo =2 m+1 , where n bo is the next largest binary order after n.

What is claimed is:  
     
         1 . An addition circuit for adding together two binary numbers each having a length of n bits, comprising: 
 an array of logical nodes that are arranged so that each set of logical nodes extending widthwise of the circuit form a logical stage and each set of nodes extending depthwise of the circuits forms an addition path, with each pair of adjacent addition paths forming a column;    spanning paths arranged to interconnect selected logical nodes so that adjacent logical stages are connected via an interconnection level, each spanning path extending from a node in one stage across at least one column being connected to a number f of fan-out nodes in a subsequent stage, the circuit having the following configuration parameters: 
 i) for each interconnection level the number f of fan-out nodes lies in the range 1 to 2 j , where j is the interconnection level index lying between 0 and m, 2 j  is the maximum fan-out number for that level, and there are m+2 logical stages;  
 ii) the fan-out f of nodes at each level is always no greater than the number f of fan-out nodes at a subsequent level;  
 iii) the number of columns across which a spanning path extends within an interconnection level is 2 j ; and  
   at least one level has a fan-out number f<2 j  and at least one level has a fan-out number f>1.    
     
     
         2 . An addition circuit as claimed in  claim 1  wherein for bit lengths n of a binary order the number (m+2) of logical stages is derived from the following equation:  
         n= 2 m+1 .  
     
     
         3 . An addition circuit according to  claim 1  wherein for bit lengths n which are not binary orders, the number (m+2) of logical stages is derived from the following equation:  
         n   bo =2 m+1    
       where n bo  is the next largest binary order after n.  
     
     
         4 . An addition circuit according to  claim 1  wherein each logical node receives at least two signals representing bits of the same significance (i) in the binary numbers to be added, and comprises at least one logic gate.  
     
     
         5 . An addition circuit according to  claim 1  wherein each spanning path conveys one or more signals from a node of one significance in one logical stage to a node of a different significance in a subsequent logical stage.  
     
     
         6 . An addition circuit according to  claim 1  wherein the fan-out f=1 for more than one level.  
     
     
         7 . An addition circuit according to  claim 6  wherein f=1 for all levels except the mth level.  
     
     
         8 . An addition circuit according to  claim 1  wherein at least one level has maximum fan-out (f=2 j ) where j=m.  
     
     
         9 . An addition circuit according to  claim 1  wherein the fan-out f=2 for at least two levels  
     
     
         10 . A method of designing an addition circuit for adding together two binary numbers each of bit length n, the method comprising: 
 determining the number (m+2) of logical stages in the addition circuit according to the following: 
 for bit length n of a binary order, n=2 m+1    
 and for bit lengths which are not binary orders n bo =2 m+1  where n bo  is the next largest binary order after n;  
   for each of said logical stages allocating a set of virtual nodes, said virtual nodes forming potential addition paths depthwise of the circuit and adjacent addition paths forming a column;    determining for each logical stage its expected input capacitance; and    defining spanning paths wherein the spanning paths constitute an interconnection level between adjacent logical stages, wherein definition of the spanning paths is carried out in accordance with the following configuration parameters and depending on the expected input capacitance of each stage: 
 i) for each interconnection level the number f of fan-out nodes in a subsequent stage to which a node of a preceding stage is connected lies in the range 1 to 2 j , where j is the interconnection level index lying between 0 and m and 2 j  is the maximum fan-out number for that level,  
 ii) the fan-out f of nodes at each level is always no greater than the fan-out f of nodes at a subsequent level,  
 iii) the number of columns across which a spanning path extends within an interconnection level is 2 j , and  
   at least one level has a fan-out number f<2 j  and at least one level has a fan-out number f>1.    
     
     
         11 . An addition circuit for an integrated circuit, comprising: 
 a plurality of nodes, the nodes arranged in rows and columns, each row forming a logical stage, and each column forming an addition path;    a plurality of spanning paths connecting nodes in one column with nodes in one or more adjacent columns and in one or more subsequent stages; and    the number (m+2) of logical stages comprises: 
 for bit lengths n of a binary order, n=2 m+1 .  
   
     
     
         12 . The circuit of  claim 11  wherein the number (m+1) of stages further comprises: 
 for bit lengths n that are not binary orders, n bo =2 m+1 .  
 
     
     
         13 . The circuit of  claim 11  wherein spanning paths comprise metal lines arranged to interconnect selected nodes so that the adjacent logical stages are connected via an interconnection level, the circuit comprising the following configuration parameters: 
 i) for each interconnection level the number f of fan-out nodes lies in the range of 1 to 2 j , where j is the interconnection level index lying between 0 and m, 2 j  is the maximum fan-out number for that level, and there are m+2 logical stages;  
 ii) the fan-out f of nodes at each level is always no greater than the number f of fan-out nodes at a subsequent level;  
 iii) the number of columns across which a spanning path extends within an interconnection level is 2 j ; and at least one level has a fan-out number f<2 j  and at least one level has a fan-out number f>1.  
 
     
     
         14 . The circuit of  claim 13  wherein the number (m+1) of stages comprises: 
 for bit lengths n that are not binary orders, n bo =2 m+1 .  
 
     
     
         15 . The circuit of  claim 14  wherein the plurality of spanning paths comprise metal lines, and wherein each node comprises at least one logic gate coupled to bits of the same significance in each operand by one or more metal wires.  
     
     
         16 . A method for designing an addition circuit, comprising: 
 determining the bit-length n of the operands to be added;    determining the number (m+2) of logical stages in the addition circuits, comprising: 
 for bit length n of a binary order, n=2 m+1 ;  
 determining the addition path for each operand bit to form one or more columns;  
 determining the expected input capacitance for each logical stage; and  
 defining a plurality of spanning paths connecting nodes in one column with one or more nodes in adjacent columns and in subsequent stages in accordance with the following configuration parameters: 
 i) for each interconnection level the number f of fan-out nodes in a subsequent stage to which a node of a preceding stage is connected lies in the range 1 to 2 j , where j is the interconnection level index lying between 0 and m and 2 j  is the maximum fan-out number for that level,  
 ii) the fan-out f of nodes at each level is always no greater than the fan-out f of nodes at a subsequent level,  
 iii) the number of columns across which a spanning path extends within an interconnection level is 2 j , and at least one level has a fan-out number f<2 j  and at least one level has a fan-out number f>1.  
 
   
     
     
         17 . The method of  claim 16  wherein determining the number of logical stages further comprises: 
 for bit lengths n that are not binary orders, n bo =2 m+1  where n bo  is the next largest binary order after n.  
 
     
     
         18 . The method of  claim 16  wherein determining the expected input capacitance comprises: 
 determining the required output drive strength of the addition circuit;  
 defining the size of the logic gates required to implement the nodes of the final stage; and  
 determining the input capacitance of the final stage.