Abstract:
A method is provided for deriving an RTL a logic circuit performing a multiplication as the sum of addends operation with a desired rounding position. In this, an error requirement to meet for the design rounding position is derived. For each of the CCT and the VCT implementation a number columns to discard is derived and a constant to include in the sum addends. For an LMS implementation, a number of columns to discard is derived. After discarding the columns and including the constants as appropriate, an RTL representation of the sum of addends operation is derived for each of the CCT, VCT and LMS implementations and a logic circuit synthesized for each of these. The logic circuit which gives the best implementation is selected for manufacture.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application claims priority from GB App. No. 1111243.0, entitled “Method and Apparatus for Performing Lossy Integer Multiplier Synthesis”, filed on Jun. 30, 2011, which is incorporated by reference herein in its entirety for all purposes. 
       BACKGROUND 
       [0002]    1. Field 
         [0003]    Some aspects herein relate to methods and apparatus for use in the synthesis and manufacture of integer multipliers that are correct up to a given error tolerance and which perform multiplication as a sum of addends with faithful rounding. 
         [0004]    2. Related Art 
         [0005]    When modern integrated circuits (IC) designs are produced, these usually start with a high level design specification which captures the basic functionality required but does not include the detail of implementation. High level models of this type are usual written using high level programming language to derive some proof of concept and validate the model, and can be run on general purpose computers or on dedicated processing devices. Once this has been completed and the model has been reduced to register transfer level (RTL) using commercially available tools, or manually, this RTL model can then be optimised to determine a preferred implementation of the design in silicon. 
         [0006]    The implementation of some types of multiplier in hardware often involve the determination of a number of partial products which are then summed, each shifted by one bit relative to the previous partial product. Visually this can be considered as a parallelogram array of bits as shown in  FIG. 1 , where the black circles represent bits. 
         [0007]    When a function such as a multiplier is to be produced and manufactured in hardware a circuit to perform the multiplication is derived in Register Transfer Level (RTL) and from this a netlist of gates to produce a hardware circuit is derived. There are many applications in which the full result of a fixed point multiplication is not required, but an appropriately rounded result can be returned. A common approach is to use faithful rounding, which produces a result which is rounded to the required machine precision value above or below the precise result, but not always to the nearest one of these values. 
         [0008]    A challenge is to create the most effective trade off between silicon area and error properties. Even for simple truncation schemes there are a wealth of design options and trade offs that can be made. Gathering error statistics for even modestly sized multipliers is extremely time consuming. In order to facilitate high level datapath synthesis capable of searching the design space of single or interconnected truncated multipliers in an acceptable time, analytic formulae must be found. The structure of the majority of truncated multiplication schemes of two n by n bit inputs a and b producing an n bit output y is as follows: truncate the multiplier sum of addends array by removing the value contained in the least significant k columns, denoted Δ k , prior to the addition of the partial products [1]. A hardware-efficient function of the two multiplicands f(a,b) is then introduced into the remaining columns. Once the resultant array is summed, a further n−k columns are truncated, the result is then the approximation to the multiplication to the required precision. The structure of this general multiplier truncation scheme can be found in  FIG. 1 . This shows k columns of the array being truncated, and n bits being truncated from the sum of addends to produce a result of the required precision. 
         [0009]    This formulation covers all the truncation schemes cited in this paper, as well as trivially incorporating non truncation schemes such as round to nearest, up: k=0 and f=2 n-1 . 
         [0010]    The scheme may be summarised algebraically: 
         [0000]    
       
         
           
             
               y 
               = 
               
                 
                   ⌊ 
                   
                     
                       ab 
                       + 
                       
                         
                           2 
                           k 
                         
                          
                         
                           f 
                            
                           
                             ( 
                             
                               a 
                               , 
                               b 
                             
                             ) 
                           
                         
                       
                       - 
                       
                         Δ 
                         k 
                       
                     
                     
                       2 
                       n 
                     
                   
                   ⌋ 
                 
                  
                 a 
               
             
             , 
             b 
             , 
             n 
             , 
             
               k 
               ∈ 
               N 
             
           
         
       
     
         [0011]    The error introduced by doing so is: 
         [0000]    
       
         
           
             ɛ 
             = 
             
               ab 
               - 
               
                 
                   2 
                   n 
                 
                  
                 
                   ⌊ 
                   
                     
                       ab 
                       + 
                       
                         
                           2 
                           k 
                         
                          
                         
                           f 
                            
                           
                             ( 
                             
                               a 
                               , 
                               b 
                             
                             ) 
                           
                         
                       
                       - 
                       
                         Δ 
                         k 
                       
                     
                     
                       2 
                       n 
                     
                   
                   ⌋ 
                 
               
             
           
         
       
       
         
           
             ɛ 
             = 
             
               
                 ( 
                 
                   
                     ( 
                     
                       ab 
                       + 
                       
                         
                           2 
                           k 
                         
                          
                         
                           f 
                            
                           
                             ( 
                             
                               a 
                               , 
                               b 
                             
                             ) 
                           
                         
                       
                       - 
                       
                         Δ 
                         k 
                       
                     
                     ) 
                   
                    
                   mod 
                    
                   
                       
                   
                    
                   
                     2 
                     n 
                   
                 
                 ) 
               
               + 
               
                 Δ 
                 k 
               
               - 
               
                 
                   2 
                   k 
                 
                  
                 
                   f 
                    
                   
                     ( 
                     
                       a 
                       , 
                       b 
                     
                     ) 
                   
                 
               
             
           
         
       
       
         
           
             ɛ 
             = 
             
               T 
               + 
               
                 Δ 
                 k 
               
               - 
               
                 
                   2 
                   k 
                 
                  
                 
                   f 
                    
                   
                     ( 
                     
                       a 
                       , 
                       b 
                     
                     ) 
                   
                 
               
             
           
         
       
     
         [0012]    Where T=(ab+2 k f (a·b)−Δ K )mod 2 n . A design that exhibits faithful rounding is one such that: 
         [0000]      ∀ a,b|ε|&lt; 2 n  
 
         [0013]    Note that if the correct answer is exactly representable then this perfect answer must be returned by a faithfully rounded scheme, otherwise |ε|≧2 n . Early truncation schemes considered f being constant, [1] and [2] referred to as Constant Correction Truncated schemes (CCT). Following these, the proposal to make f a function of a and b appeared, termed Variable Correction Truncation (VCT) where the most significant column that is truncated is used as the compensating value for f, [3]. A hybrid between CCT and column promoting VCT has been proposed which only uses some of the partial product bits of the promoted column, termed Hybrid Correction Truncation [4]. Arbitrary functions of the most significant truncated column have been considered along with their linearization, one of these linearisations requires promoting all but the four most extreme partial products bits and adding a constant, called LMS truncation due to the fact it targets the least mean square error, [5] [6]. Forming approximations to the carries produced by Δ k  has also been put forward, termed carry prediction [7]. Apart from the AND array, a negative two&#39;s complement array has also been considered [8]. The particular case of constant multipliers have also been considered [9]. Further modified Booth multipliers have been studied while applying CCT and VCT [10]. Faithfully rounded integer multipliers have also been constructed by truncating, deleting and rounding the multiplication during the array construction, reduction and final integer addition, [11]. In terms of applications, DSP has been the main focus area but they also appear in creating floating point multipliers, where a 1 ulp accuracy is permitted [12]. The evaluation of transcendental functions has also been considered, utilising truncated multipliers as well as truncated squarers [13]. When surveying how the statistics of the error has been analysed, in general, exhaustive simulation is performed or error bounds were given without proof. In the original CCT paper, [1], the maximum error was stated without a full proof. In advanced compensation schemes such as [7], it is commented that it is difficult to know what kind of error is being generated and while exhaustive searches were conducted for n&lt;9, for sizes above this, the only option was to resort to random test vectors. In [14], finding the best compensation function requires searching a space exponential in n and is only feasible for n&lt;13. Further the schemes either find compensating functions heuristically or attempt to minimise the average absolute error or mean square error. 
         [0014]    The issue with truncating bits in sum of products operations is that it is complex to determine the effect of truncation and usually error statistics need to be gathered which is time consuming and can lead to many iterations being required during RTL synthesis to produce just one sum of addends unit. 
       SUMMARY 
       [0015]    It is desirable to be able to construct a sum of addends function which minimises hardware implementation cost as the output of RTL synthesis while maintaining a known error profile. In other words, it will be desirable to reduce the complexity of the synthesised logic as much as possible through truncation while maintaining a known error in the thus approximated result, without the time consuming data manipulation required to gather error statistics. 
         [0016]    Some aspects provide for the systematic creation of HDL for truncated multipliers which are known a priori to be faithfully rounded, without the need for any simulation or exploration, and as such are amenable to an industry standard synthesis flow. Thus such multipliers may be synthesised and manufactured. Approaches such as [11] are, as such, not viable option as it modifies the multiplier synthesis directly. We also seek the most hardware efficient multiplier structure for a given architecture, so we require the necessary and sufficient conditions for faithfully rounding. 
         [0017]    In accordance with one aspect, there is provided a method for deriving in RTL a logic circuit for performing a multiplication as a sum of addends operation with a desired rounding precision comprising the steps of:
   a) determining an error requirement to be met for the desired rounding precision;   b) determining a number of columns k to be discarded from the sum of addends and a constant to include in the sum of addends for each of a CCT and VCT implementation of the sum of addends which meets the error requirement, and further determining a number of columns to discard for an LMS implementation of the sum of addends which meets the error requirement;   c) for each of the CCT, VCT and LMS implementations, discarding the said number of columns;   d) for each of the CCT and VCT implementations, including the said constant in the sum of addends;   e) deriving an RTL representation of the sum of addends operation for each of the CCT, VCT and LMS implementations, after steps c) and d) have been performed;   f) synthesizing a logic circuit for each of the respective RTL representations; and,   g) selecting one of the logic circuit for manufacture   
 
         [0025]    In accordance with another aspect, there is provided a method for manufacturing in integrated circuit for performing a multiplication as a sum of addends operation with a desired rounding precision comprising the steps of
   a) determining an error requirement to be met for the desired rounding precision;   b) determining a number of columns k to be discarded from the sum of addends and a constant to include in the sum of addends for each of a CCT and VCT implementation of the sum of addends which meets the error requirement, and further determining a number of columns to discard for an LMS implementation of the sum of addends which meets the error requirement;   c) for each of the CCT, VCT and LMS implementations, discarding the said number of columns;   d) for each of the CCT and VCT implementations, including the said constant in the sum of addends;   e) deriving an RTL representation of the sum of addends operation for each of the CCT, VCT and LMS implementations, after steps c) and d) have been performed;   f) synthesizing a logic circuit for each of the respective RTL representations; and,   g) selecting one of the logic circuit for manufacture   
 
         [0033]    In accordance with a further aspect, there is provided a computer program product which when run on a computing system causes it to perform a method for deriving in RTL a logic circuit for performing a multiplication as sum of addends operation with a desired rounding precision comprising the steps of:
   a. determining an error requirement to be met for the desired rounding precision;   b. determining a number of columns k to be discarded from the sum of addends and a constant to include in the sum of addends for each of a CCT and VCT implementation of the sum of addends which meets the error requirement, and further determining a number of columns to discard for an LMS implementation of the sum of addends which meets the error requirement;   c. for each of the CCT, VCT and LMS implementations, discarding the said number of columns;   d. for each of the CCT and VCT implementations, including the said constant in the sum of addends;   e. deriving an RTL representation of the sum of addends operation for each of the CCT, VCT and LMS implementations, after steps c) and d) have been performed;   f. synthesizing a logic circuit for each of the respective RTL representations; and,   g. selecting one of the logic circuit for manufacture   
 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0041]      FIG. 1  shows a sum of addends array used in existing truncated multipliers; 
           [0042]      FIG. 2  shows schematically an existing lossy multiplier synthesiser and RTL generator; 
           [0043]      FIG. 3  shows a sum of addends array for a CCT multiplier embodying the invention; 
           [0044]      FIG. 4  shows a sum of addends array for a VCT multiplier embodying the invention; 
           [0045]      FIG. 5  shows a sum of addends array for an LMS multiplier embodying the invention; and, 
           [0046]      FIG. 6  shows a block diagram of the synthesis of the three multiplier of  FIGS. 3 ,  4  and  5  in parallel 
       
    
    
     DETAILED DESCRIPTION 
       [0047]    The task of creating faithfully rounded multipliers which introduce an error into the synthesis falls under the category of lossy synthesis as opposed to a traditional synthesis which would be classed as lossless. The structure of the proposed lossy multiplier synthesiser is found in  FIG. 2 . This comprises a lossy multiplier RTL generator to which is provided a known error constraint for the multiplication. This provides a plurality of alternative RTL outputs to an RTL synthesiser  22  which produces a netlist of gates for the manufacture of each RTL output with known synthesis constraints. These netlists of gates are then provided to a selection unit  24  which selects the best of the netlists, which is usually the one which can be manufactured with fewest gates and therefore less silicon. 
         [0048]    Embodiments may provide the creation of three faithfully rounded multiplier schemes for the CCT, VCT and LMS architectures (so in this case the error requirement will be faithful rounding). CCT uses a single constant as compensation. Column promoting truncated multiplication (VCT) takes f(a,b) to be the most significant column of Δ k  (notated col k−1 ). LMS promotes elements from col k−1  but leaves the most extreme 4 elements behind as well as introducing a constant of 2 n-k−1 . Algebraically we can represent these as: 
         [0000]    
       
         
           
             
                 
             
              
             
               
                 
                   f 
                   CCT 
                 
                  
                 
                   ( 
                   
                     a 
                     , 
                     b 
                   
                   ) 
                 
               
               = 
               C 
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 
                   f 
                   VCT 
                 
                  
                 
                   ( 
                   
                     a 
                     , 
                     b 
                   
                   ) 
                 
               
               = 
               
                 C 
                 + 
                 
                   
                     ∑ 
                     
                       i 
                       = 
                       0 
                     
                     
                       k 
                       - 
                       1 
                     
                   
                    
                   
                       
                   
                    
                   
                     
                       a 
                       i 
                     
                      
                     
                       b 
                       
                         k 
                         - 
                         1 
                         - 
                         i 
                       
                     
                   
                 
               
             
           
         
       
       
         
           
             
               
                 f 
                 LMS 
               
                
               
                 ( 
                 
                   a 
                   , 
                   b 
                 
                 ) 
               
             
             = 
             
               
                 2 
                 
                   n 
                   - 
                   k 
                   - 
                   1 
                 
               
               + 
               
                 
                   ∑ 
                   
                     i 
                     = 
                     2 
                   
                   
                     k 
                     - 
                     3 
                   
                 
                  
                 
                     
                 
                  
                 
                   
                     a 
                     i 
                   
                    
                   
                     b 
                     
                       k 
                       - 
                       1 
                       - 
                       i 
                     
                   
                 
               
               + 
               
                 
                   1 
                   2 
                 
                  
                 
                   ( 
                   
                     
                       
                         a 
                         0 
                       
                        
                       
                         b 
                         
                           k 
                           - 
                           1 
                         
                       
                     
                     + 
                     
                       
                         a 
                         1 
                       
                        
                       
                         b 
                         
                           k 
                           - 
                           2 
                         
                       
                     
                     + 
                     
                       
                         a 
                         
                           k 
                           - 
                           2 
                         
                       
                        
                       
                         b 
                         1 
                       
                     
                     + 
                     
                       
                         a 
                         
                           k 
                           - 
                           1 
                         
                       
                        
                       
                         b 
                         0 
                       
                     
                   
                   ) 
                 
               
             
           
         
       
     
         [0049]    Faithful Rounding of CCT Multiplier Schemes 
         [0050]      FIG. 3  shows the sum of addends array for a CCT multiplier to implement a AND b with k columns truncated and n bits to discard from the result to produce the desired precision. 
         [0051]    In this case Δ k −2 k f(a,b)=Δ k −2 k C. To produce bounds on this object we need bounds on Δ k  (the value of the bits being discarded). When a k−1:0 =b k−1:0 =0 then Δ k  is entirely full of zeroes, hence Δ k ≧0. When a k−1:0 =b k−1:0 =2 k −1 then Δ k  is entirely full of ones, hence Δ k ≦Σ t=0   k−1 (2 k −2 i )=(k−1)2 k +1. So we can provide the following tight bounds: 
         [0000]      − C 2 k ≦Δ k −2 k   C ≦( k−C− 1)2 k +1
 
         [0052]    T is bounded by 0≦T≦2 n −2 k  and we will show that it can take any value when Δ k  takes its extreme values. If a k:0 =2 k  then 
         [0000]        T =(( a   n-1:k+1 2 k+1 +2 k ) b+C 2 k )mod 2 n    
         [0000]        T 2 −k   −C =(2 a   n-1:k+1 +1) b  mod 2 n-k    
         [0053]    Now 2a n-1:k−1 +1 is odd hence coprime to 2 n-k  (hence regardless of the value of C we can always find a and b such that any given T can be achieved when Δ k  is minimal. 
         [0054]    When Δ k  is maximal a k−1:0 =b k−1:0 =2 k −1, under these conditions: 
         [0000]        T =(( a   n-1:k 2 k +2 k −1)( b   n-1:k 2 k +2 k −1)+ C 2 k −max(Δ k ))mod 2 n  
 
         [0000]        T 2 −k   −a   n-1:k (2 k −1)− C− 2 k   +k+ 1 =b   n-1:k ( a   n-1:k 2 k +2 k −1)mod  2   n-k  
 
         [0055]    Now a n-1:k 2 k +2 k −1 is odd hence coprime to 2 n-k  hence regardless of the value of C we can always find a n-1:k  and b n-1:k  such that any given T can be achieved when Δ k  is maximal. 
         [0056]    So we can present the following tight bounds for the error of the CCT scheme: 
         [0000]      − C 2 k ≦ε CCT ≦2 n −( C−k+ 2)2 k +1
 
         [0057]    Given these bounds we work out the necessary and sufficient conditions for the faithful rounding of CCT multipliers: 
         [0000]      |ε CCT |&lt;2 n           2 n-k   &lt;C&lt;k− 2
 
         [0058]    This can then be used to derive a constant to add to include in a truncated sum of addends array for k columns truncated 
         [0059]    Faithful Rounding of VCT Multiplier Schemes 
         [0060]      FIG. 4  shows the sum of addends array for a VCT multiplier. In this, the constant to include in the least significant column of the sum of addends is the bits of the most significant of the truncated columns, shifted by one bit. Thus a total of T columns are truncated from the result, giving a y bit result. 
         [0061]    In this case Δ k −2 k f(a,b)=Δ k −2 k col k−1 −2 k C. We will provide tight bounds on this object. 
         [0062]    We first claim that μ=Δ k −2 k col k−1  takes its maximal value when col k−1 =0 and col k−2  is an alternating binary sequence. To see that col k−1 =0, consider that μ can be written as (for an arbitrary function g): 
         [0000]      μ=2 j   a   j (−2 k−1-j   b   k−1-j   +b   k−2-j:0 )+ g ( a   k−1:j+1   ,a   j-1:0   ,b )
 
         [0063]    If we set j=0 in this equation and maximise μ over a 0  and b k−1  we find a 0 =1 and by symmetry b 0 =1. Then, in the general case, if we maximise μ over a j  and b k−1-j  keeping in mind that b k−2-j &gt;0 as b 0 =1 then we find that μ is maximised when a j ≠b k−1-j  and hence col k−1 =0. 
         [0064]    To see that col k−2  is an alternating binary sequence consider the case when there are two adjacent zeroes in col k−2  so we have a location where: 
         [0000]        a   j-1   b   k−j   a   j-1   b   k−j-1 =0 0 
         [0000]        a   j   b   k−j-1    a   j   b   k−j-2 =0 0 
         [0065]    Assuming that a j ≠b k−1-j  for all j and, by symmetry, we may assume a j-1 =1 solving the above equations means a j:j-1 =“11” and b k−j:k−j-2 =0. If however we set a j:j-1 =“01” and b k−j:k−j-2 =“010” we would actually increase μ by: 
         [0000]    
       
         
           
             
               
                 
                   2 
                   
                     k 
                     - 
                     2 
                   
                 
                 + 
                 
                   
                     2 
                     
                       k 
                       - 
                       j 
                       - 
                       1 
                     
                   
                    
                   
                     a 
                      
                     
                       [ 
                       
                         j 
                         - 
                         
                           2 
                            
                           
                             : 
                           
                            
                           0 
                         
                       
                       ] 
                     
                   
                 
                 - 
                 
                   
                     2 
                     j 
                   
                    
                   
                     b 
                      
                     
                       [ 
                       
                         k 
                         - 
                         j 
                         - 
                         
                           3 
                            
                           
                             : 
                           
                            
                           0 
                         
                       
                       ] 
                     
                   
                 
               
               &gt; 
               
                 
                   2 
                   
                     k 
                     - 
                     2 
                   
                 
                 + 
                 
                   
                     2 
                     
                       k 
                       - 
                       j 
                       - 
                       1 
                     
                   
                    
                   
                     a 
                      
                     
                       [ 
                       
                         j 
                         - 
                         
                           2 
                            
                           
                             : 
                           
                            
                           0 
                         
                       
                       ] 
                     
                   
                 
                 - 
                 
                   
                     2 
                     j 
                   
                    
                   
                     ( 
                     
                       
                         2 
                         
                           k 
                           - 
                           j 
                           - 
                           2 
                         
                       
                       - 
                       1 
                     
                     ) 
                   
                 
               
             
             = 
             
               
                 
                   2 
                   j 
                 
                 + 
                 
                   
                     2 
                     
                       k 
                       - 
                       j 
                       - 
                       1 
                     
                   
                    
                   
                     a 
                      
                     
                       [ 
                       
                         j 
                         - 
                         
                           2 
                            
                           
                             : 
                           
                            
                           0 
                         
                       
                       ] 
                     
                   
                 
               
               &gt; 
               0 
             
           
         
       
     
         [0066]    Hence when μ is maximal, adjacent zeroes never appear in col k−2 . Further if adjacent ones were to appear in col k−2  then there would be a one in column col k−1 , which contradicts the previous assumption. Conclude that col k−1 =0 and col k−2  is an alternating binary sequence when μ is maximal. These two conditions uniquely determine a and b, from which can be calculated the bounds: 
         [0000]    
       
         
           
             μ 
             ≤ 
             
               
                 
                   
                     ( 
                     
                       
                         3 
                          
                         
                             
                         
                          
                         k 
                       
                       - 
                       2 
                     
                     ) 
                   
                    
                   
                     2 
                     
                       k 
                       - 
                       1 
                     
                   
                 
                 + 
                 
                   
                     ( 
                     
                       - 
                       1 
                     
                     ) 
                   
                   k 
                 
               
               9 
             
           
         
       
     
         [0067]    The lower bound on μ is achieved when a j =b k−1-j  for all j, a 0 =b 0  and the interior of a and b are alternating binary sequences. We will demonstrate each of these properties in turn. 
         [0068]    First recall that we can write for some function g: 
         [0000]      μ=2 j   a   j (−2 k−1-j   b   k−1-j   +b   k−2-j:0 )+ g ( a   k−1:j+1   ,a   j-1:0   ,b )
 
         [0069]    If a j ≠b k−1-j  and a j =1 then μ can be decreased by 2 k−1-j −b k−2-j:0 &gt;0 by setting b k−1-j =1, hence μ being minimal implies a j =b k−1-j  for all j. 
         [0070]    Secondly if a 0 =b k−1 =0 then μ can be decreased by 2 k−1 −b k−2:0 &gt;0 by setting a 0 =1. 
         [0071]    Finally we need to show that the interior of a and b are alternating binary sequences when μ is minimal. First we introduce some notation: 
         [0000]    
       
         
           
             
               
                 
                   
                     γ 
                      
                     
                       ( 
                       z 
                       ) 
                     
                   
                   = 
                     
                    
                   
                     
                       1 
                       
                         2 
                         
                           k 
                           - 
                           1 
                         
                       
                     
                      
                     
                       μ 
                        
                       
                         ( 
                         
                           a 
                           = 
                           
                             
                               x 
                               0 
                             
                              
                             
                               x 
                               1 
                             
                              
                             
                                 
                             
                              
                             … 
                              
                             
                                 
                             
                              
                             
                               x 
                               
                                 m 
                                 - 
                                 1 
                               
                             
                              
                             
                               z 
                               
                                 p 
                                 - 
                                 1 
                               
                             
                              
                             
                                 
                             
                              
                             … 
                              
                             
                                 
                             
                              
                             
                               z 
                               1 
                             
                              
                             
                               z 
                               0 
                             
                              
                             
                               y 
                               
                                 q 
                                 - 
                                 1 
                               
                             
                              
                             
                                 
                             
                              
                             … 
                              
                             
                                 
                             
                              
                             
                               y 
                               1 
                             
                              
                             
                               y 
                               0 
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     
                       f 
                        
                       
                         ( 
                         z 
                         ) 
                       
                     
                     + 
                     
                       
                         g 
                          
                         
                           ( 
                           z 
                           ) 
                         
                       
                        
                       X 
                     
                     + 
                     
                       
                         h 
                          
                         
                           ( 
                           z 
                           ) 
                         
                       
                        
                       Y 
                     
                     + 
                     
                       γ 
                        
                       
                         ( 
                         0 
                         ) 
                       
                     
                   
                 
               
             
           
         
       
     
         [0072]    Where X=x m-1  . . . x 1 x 0 /2 m &lt;1 and Y=y q-1  . . . y 1 y 0 /2 q &lt;1, we will then show various strings within a never occur:
       γ(010)−γ(000)=(X+Y)/2−1&lt;0 so “000” never occurs   γ(101)−γ(111)=−(X+Y)&lt;0 when k&gt;3 so “111” never occurs   If “1001” were feasible then γ(1001)≦γ(1010),γ(0101),γ(1011),γ(1101) this would imply       
 
         [0000]      0≦1 +X− 4 Y  
 
         [0000]      0≦1 +Y− 4×
 
         [0000]      0≦−1 +X+ 2 Y  
 
         [0000]      0≦−1 +Y+ 2 X  
 
         [0000]    But the only solution to this is X=Y=⅓ which is not possible given that X and Y are finite binary numbers. Hence “1001” never occurs. 
         [0076]    If “0110” were feasible then γ(0110)≦γ(0101),γ(1010), γ(0010),γ(0100) this would imply: 
         [0000]      0≦−2+4 Y−X  
 
         [0000]      0≦−2+4 X−Y  
 
         [0000]      0≦2−2 X−Y  
 
         [0000]      0≦2−2 Y−X  
 
         [0000]    But the only solution to this is X=Y=⅔ which is not possible given that X and Y are finite binary numbers. Hence “0110” never occurs. 
         [0077]    The fact that these strings never occur implies that the interior of a and b are alternating binary sequences. The fact that a j =b k−1-j  for all j, a 0 =b 0  and the interior of a and b are alternating binary sequences uniquely determine a and b, from which can be calculated the bounds: 
         [0000]    
       
         
           
             μ 
             ≤ 
             
               
                 
                   
                     ( 
                     
                       
                         3 
                          
                         
                             
                         
                          
                         k 
                       
                       + 
                       7 
                     
                     ) 
                   
                    
                   
                     2 
                     
                       k 
                       - 
                       1 
                     
                   
                 
                 + 
                 
                   
                     ( 
                     
                       - 
                       1 
                     
                     ) 
                   
                   k 
                 
               
               9 
             
           
         
       
     
         [0078]    We are now in a position to tightly bound Δ k −2 k col k−1 −2 k C: 
         [0000]    
       
         
           
             
               - 
               
                 
                   
                     
                       2 
                       
                         k 
                         - 
                         1 
                       
                     
                      
                     
                       ( 
                       
                         
                           3 
                            
                           
                               
                           
                            
                           k 
                         
                         + 
                         
                           18 
                            
                           
                               
                           
                            
                           C 
                         
                         + 
                         7 
                       
                       ) 
                     
                   
                   + 
                   
                     
                       ( 
                       
                         - 
                         1 
                       
                       ) 
                     
                     k 
                   
                 
                 9 
               
             
             ≤ 
             
               
                 Δ 
                 k 
               
               - 
               
                 
                   2 
                   k 
                 
                  
                 
                   col 
                   
                     k 
                     - 
                     1 
                   
                 
               
               - 
               
                 
                   2 
                   k 
                 
                  
                 C 
               
             
             ≤ 
             
               
                 
                   
                     2 
                     
                       k 
                       - 
                       1 
                     
                   
                    
                   
                     ( 
                     
                       
                         3 
                          
                         
                             
                         
                          
                         k 
                       
                       - 
                       
                         18 
                          
                         
                             
                         
                          
                         C 
                       
                       - 
                       2 
                     
                     ) 
                   
                 
                 + 
                 
                   
                     ( 
                     
                       - 
                       1 
                     
                     ) 
                   
                   k 
                 
               
               9 
             
           
         
       
     
         [0079]    We will now show that T can take any value whenever μ is extreme. If μ is maximal then col k−1 =0 and col k−2  is an alternating binary sequence. These conditions uniquely determine a k−1:0  and b k−1:0  up to swapping. When k is odd these conditions imply a k−1:0 =(2 k−1 1)/3 and b k−1:0 =(2 k +1)/3, T is then defined by: 
         [0000]    
       
         
           
             T 
             = 
             
               
                 ( 
                 
                   
                     
                       ( 
                       
                         
                           
                             a 
                             
                               
                                 n 
                                 - 
                                 1 
                               
                               : 
                               k 
                             
                           
                            
                           
                             2 
                             k 
                           
                         
                         + 
                         
                           
                             
                               2 
                               
                                 k 
                                 - 
                                 1 
                               
                             
                             - 
                             1 
                           
                           3 
                         
                       
                       ) 
                     
                      
                     
                       ( 
                       
                         
                           
                             b 
                             
                               
                                 n 
                                 - 
                                 1 
                               
                               : 
                               k 
                             
                           
                            
                           
                             2 
                             k 
                           
                         
                         + 
                         
                           
                             
                               2 
                               k 
                             
                             + 
                             1 
                           
                           3 
                         
                       
                       ) 
                     
                   
                   + 
                   
                     C 
                      
                     
                         
                     
                      
                     
                       2 
                       k 
                     
                   
                   - 
                   
                     max 
                      
                     
                       ( 
                       μ 
                       ) 
                     
                   
                 
                 ) 
               
                
               mod 
                
               
                   
               
                
               
                 2 
                 n 
               
             
           
         
       
       
         
           
             
               
                 T 
                  
                 
                     
                 
                  
                 
                   2 
                   
                     - 
                     k 
                   
                 
               
               - 
               C 
               - 
               
                 
                   
                     2 
                     k 
                   
                   - 
                   
                     3 
                      
                     
                         
                     
                      
                     k 
                   
                   + 
                   1 
                 
                 18 
               
               - 
               
                 
                   a 
                   
                     
                       n 
                       - 
                       1 
                     
                     : 
                     k 
                   
                 
                  
                 
                   
                     
                       2 
                       k 
                     
                     + 
                     1 
                   
                   3 
                 
               
             
             = 
             
               
                 
                   b 
                   
                     
                       n 
                       - 
                       1 
                     
                     : 
                     k 
                   
                 
                  
                 
                   ( 
                   
                     
                       
                         a 
                         
                           
                             n 
                             - 
                             1 
                           
                           : 
                           k 
                         
                       
                        
                       
                         2 
                         k 
                       
                     
                     + 
                     
                       
                         
                           2 
                           
                             k 
                             - 
                             1 
                           
                         
                         - 
                         1 
                       
                       3 
                     
                   
                   ) 
                 
               
                
               mod 
                
               
                   
               
                
               
                 2 
                 
                   n 
                   - 
                   k 
                 
               
             
           
         
       
     
         [0080]    Now a n-1:k 2 k +(2 k−1 −1)/3 is odd hence coprime to 2 n-k  (hence regardless of the value of C we can always find a and b such that any given T can be achieved when μ is maximal and k is odd. Similarly when k is even we have a k−1:0 =b k−1:0 =(2 k −1)/3 or a k−1:0 =b k−1:0 =(2 k−1 +1)/3 and the argument proceeds in an identical manner. Hence we conclude that regardless of the value of C we can always find a and b such that any given T can be achieved when μ is maximal. 
         [0081]    If μ is minimal then a 0 =b 0 =1, a 1 =b k−1-j  for all j and the interior of col k−1  is an alternating binary sequence. These conditions uniquely determine a k−1:0  and b k−1:0  up to swapping. When k is even these conditions imply a k−1:0 =(5*2 k−1 −1)/3 and b k−1:0 =(2 k+1 +1)/3, T is then defined by: 
         [0000]    
       
         
           
             T 
             = 
             
               
                 ( 
                 
                   
                     
                       ( 
                       
                         
                           
                             a 
                             
                               
                                 n 
                                 - 
                                 1 
                               
                               : 
                               k 
                             
                           
                            
                           
                             2 
                             k 
                           
                         
                         + 
                         
                           
                             
                               5 
                               * 
                               
                                 2 
                                 
                                   k 
                                   - 
                                   1 
                                 
                               
                             
                             - 
                             1 
                           
                           3 
                         
                       
                       ) 
                     
                      
                     
                       ( 
                       
                         
                           
                             b 
                             
                               
                                 n 
                                 - 
                                 1 
                               
                               : 
                               k 
                             
                           
                            
                           
                             2 
                             k 
                           
                         
                         + 
                         
                           
                             
                               2 
                               
                                 k 
                                 + 
                                 1 
                               
                             
                             + 
                             1 
                           
                           3 
                         
                       
                       ) 
                     
                   
                   + 
                   
                     C 
                      
                     
                         
                     
                      
                     
                       2 
                       k 
                     
                   
                   - 
                   
                     min 
                      
                     
                       ( 
                       μ 
                       ) 
                     
                   
                 
                 ) 
               
                
               mod 
                
               
                   
               
                
               
                 2 
                 n 
               
             
           
         
       
       
         
           
             
               
                 T 
                  
                 
                     
                 
                  
                 
                   2 
                   
                     - 
                     k 
                   
                 
               
               - 
               C 
               - 
               
                 
                   
                     5 
                     * 
                     
                       2 
                       
                         k 
                         + 
                         1 
                       
                     
                   
                   + 
                   
                     3 
                      
                     
                         
                     
                      
                     k 
                   
                   + 
                   8 
                 
                 18 
               
               - 
               
                 
                   a 
                   
                     
                       n 
                       - 
                       1 
                     
                     : 
                     k 
                   
                 
                  
                 
                   
                     
                       2 
                       
                         k 
                         + 
                         1 
                       
                     
                     + 
                     1 
                   
                   3 
                 
               
             
             = 
             
               
                 
                   b 
                   
                     
                       n 
                       - 
                       1 
                     
                     : 
                     k 
                   
                 
                  
                 
                   ( 
                   
                     
                       
                         a 
                         
                           
                             n 
                             - 
                             1 
                           
                           : 
                           k 
                         
                       
                        
                       
                         2 
                         k 
                       
                     
                     + 
                     
                       
                         
                           5 
                           * 
                           
                             2 
                             
                               k 
                               - 
                               1 
                             
                           
                         
                         - 
                         1 
                       
                       3 
                     
                   
                   ) 
                 
               
                
               mod 
                
               
                   
               
                
               
                 2 
                 
                   n 
                   - 
                   k 
                 
               
             
           
         
       
     
         [0082]    Now a n-1:k 2 k +(5*2 k−1 −1)/3 is odd hence coprime to 2 n-k  hence regardless of the value of C we can always find a and b such that given T can be achieved when μ is minimal and k is even. Similarly when k is odd we have a k−1:0 =b k−1:0 =(2 k+1 −1)/3 or a k−1:0 =b k−1:0 =(5*2 k−1 +1)/3 and the argument proceeds in an identical manner. Hence we conclude that regardless of the value of C we can always find a and b such that any given T can be achieved when μ is minimal. 
         [0083]    Given T can take any value when μ is extreme allows us to state the error the VCT scheme: 
         [0000]    
       
         
           
             
               - 
               
                 
                   
                     
                       2 
                       
                         k 
                         - 
                         1 
                       
                     
                      
                     
                       ( 
                       
                         
                           3 
                            
                           
                               
                           
                            
                           k 
                         
                         + 
                         
                           18 
                            
                           
                               
                           
                            
                           C 
                         
                         + 
                         7 
                       
                       ) 
                     
                   
                   + 
                   
                     
                       ( 
                       
                         - 
                         1 
                       
                       ) 
                     
                     k 
                   
                 
                 9 
               
             
             ≤ 
             
               ɛ 
               VCT 
             
             ≤ 
             
               
                 2 
                 n 
               
               + 
               
                 
                   
                     
                       2 
                       
                         k 
                         - 
                         1 
                       
                     
                      
                     
                       ( 
                       
                         
                           3 
                            
                           
                               
                           
                            
                           k 
                         
                         - 
                         
                           18 
                            
                           
                               
                           
                            
                           C 
                         
                         - 
                         20 
                       
                       ) 
                     
                   
                   + 
                   
                     
                       ( 
                       
                         - 
                         1 
                       
                       ) 
                     
                     k 
                   
                 
                 9 
               
             
           
         
       
     
         [0084]    Given these bounds we work out the necessary and sufficient conditions for the faithful rounding of VCT multipliers: 
         [0000]      |ε VCT |&lt;2 n           3*2 n-k+1   −k− 2&lt;6 C&lt;k− 7
 
         [0085]    Thus for a given error we can derive a number of columns k to discard from the sum of addends and a constant C to add from the most significant columns discarded 
       Faithful Rounding of LMS Multiplier Schemes 
       [0086]      FIG. 5  shows the sum of addends array for a for an LMS multiplier. In this, some of the bits from the least significant non-truncated column is shifted to the next least significant column for inclusion in the sum of addends 
         [0087]    The error bounds on this scheme were first reported in [16] and can be summarised by: 
         [0000]    
       
         
           
             
               
                 - 
                 
                   2 
                   
                     n 
                     - 
                     1 
                   
                 
               
               - 
               
                 
                   1 
                   9 
                 
                  
                 
                   ( 
                   
                     
                       
                         2 
                         
                           k 
                           - 
                           4 
                         
                       
                        
                       
                         ( 
                         
                           
                             24 
                              
                             
                                 
                             
                              
                             k 
                           
                           - 
                           19 
                           + 
                           
                             3 
                              
                             
                               
                                 ( 
                                 
                                   - 
                                   1 
                                 
                                 ) 
                               
                               k 
                             
                           
                         
                         ) 
                       
                     
                     - 
                     3 
                     + 
                     
                       4 
                        
                       
                         
                           ( 
                           
                             - 
                             1 
                           
                           ) 
                         
                         k 
                       
                     
                   
                   ) 
                 
               
             
             ≤ 
             
               ɛ 
               LMS 
             
             ≤ 
             
               
                 
                   2 
                   
                     n 
                     - 
                     k 
                     - 
                     1 
                   
                 
                 9 
               
                
               
                 ( 
                 
                   
                     
                       2 
                       k 
                     
                      
                     
                       ( 
                       
                         
                           3 
                            
                           
                               
                           
                            
                           k 
                         
                         + 
                         1 
                       
                       ) 
                     
                   
                   + 
                   
                     8 
                      
                     
                       
                         ( 
                         
                           - 
                           1 
                         
                         ) 
                       
                       k 
                     
                   
                 
                 ) 
               
             
           
         
       
     
         [0088]    As stated in [16], in absolute value, the most negative error dominates. From this condition we can derive the necessary and sufficient condition for faithful rounding of the LMS scheme: 
         [0000]      |ε LMS |&lt;2 n           9*2 n-k+1 &lt;6 k+ 3+(−1) k  
 
       Lossy Multiplier RTL Generator 
       [0089]    Now we have the necessary and sufficient conditions for faithful rounding of the CCT, VCT and LMS truncated multiplier schemes we can show how to construct a lossy multiplier RTL generator. In each case we want to choose the value of k and C which minimises the hardware costs. The cost of the hardware is directly related to the number of bits that need to be summed. So we wish to maximise the size of k and minimise the number of ones in the binary expansion of C while maintaining the property that the multiplier is faithfully rounded. So we can create the following algorithms which define the conditions which are required to achieve this for the known error bounds: 
         [0090]    Where the parameters are calculated as follows: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       k 
                       CCT 
                     
                     = 
                       
                      
                     
                       max 
                        
                       
                         ( 
                         
                           k 
                           : 
                           
                             ∃ 
                             
                               
                                 C 
                                  
                                 
                                     
                                 
                                  
                                 
                                   s 
                                   . 
                                   t 
                                   . 
                                   
                                       
                                   
                                    
                                   
                                     2 
                                     
                                       n 
                                       - 
                                       k 
                                     
                                   
                                 
                               
                               &gt; 
                               C 
                               &gt; 
                               
                                 k 
                                 - 
                                 2 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                    
                   
                       
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     max 
                      
                     
                       ( 
                       
                         k 
                         : 
                         
                           
                             2 
                             n 
                           
                           &gt; 
                           
                             
                               ( 
                               
                                 k 
                                 - 
                                 1 
                               
                               ) 
                             
                              
                             
                               2 
                               k 
                             
                           
                         
                       
                       ) 
                     
                   
                 
               
             
           
         
       
       
         
           
             
               C 
               CCT 
             
             = 
             
               min 
                
               
                   
               
                
               
                 Hamm 
                  
                 
                   ( 
                   
                     C 
                     : 
                     
                       
                         2 
                         
                           n 
                           - 
                           
                             k 
                             CCT 
                           
                         
                       
                       &gt; 
                       C 
                       &gt; 
                       
                         
                           k 
                           CCT 
                         
                         - 
                         2 
                       
                     
                   
                   ) 
                 
               
             
           
         
       
       
         
           
             
               k 
               VCT 
             
             = 
             
               max 
                
               
                 ( 
                 
                   k 
                   : 
                   
                     ∃ 
                     
                       
                         
                           C 
                            
                           
                               
                           
                            
                           
                             s 
                             . 
                             t 
                             . 
                             
                                 
                             
                              
                             3 
                           
                           * 
                           
                             2 
                             
                               n 
                               - 
                               k 
                               + 
                               1 
                             
                           
                         
                         - 
                         k 
                         - 
                         2 
                       
                       &gt; 
                       
                         6 
                          
                         
                             
                         
                          
                         C 
                       
                       &gt; 
                       
                         k 
                         - 
                         7 
                       
                     
                   
                 
                 ) 
               
             
           
         
       
       
         
           
             
               C 
               VCT 
             
             = 
             
               min 
                
               
                   
               
                
               
                 Hamm 
                  
                 
                   ( 
                   
                     C 
                     : 
                     
                       
                         
                           3 
                           * 
                           
                             2 
                             
                               n 
                               - 
                               
                                 k 
                                 VCT 
                               
                               + 
                               1 
                             
                           
                         
                         - 
                         
                           k 
                           VCT 
                         
                         - 
                         2 
                       
                       &gt; 
                       
                         6 
                          
                         
                             
                         
                          
                         C 
                       
                       &gt; 
                       
                         
                           k 
                           VCT 
                         
                         - 
                         7 
                       
                     
                   
                   ) 
                 
               
             
           
         
       
       
         
           
             
               k 
               LMS 
             
             = 
             
               max 
                
               
                 ( 
                 
                   k 
                   : 
                   
                     
                       2 
                       
                         n 
                         - 
                         k 
                         + 
                         1 
                       
                     
                     &gt; 
                     
                       
                         6 
                          
                         
                             
                         
                          
                         k 
                       
                       + 
                       3 
                       + 
                       
                         
                           ( 
                           
                             - 
                             1 
                           
                           ) 
                         
                         k 
                       
                     
                   
                 
                 ) 
               
             
           
         
       
     
         [0091]    Where minHamm(x:condition) calculates the smallest value within the set of all x that meet the condition with smallest Hamming weight. So as an embodiment of the invention consider the case where n=8. The Lossy Multiplier RTL Generator will first calculate all the relevant parameters:
       k CCT =5 C CCT =4 k VCT =6 C VCR r=0 k LMS =6       
 
         [0093]    And then produce the CCT, VCT and LMS RTL which use those parameters. The lossy synthesiser will then use standard RTL synthesis to produce the gate level netlists. From which the netlist which exhibits the best quality of results according to the synthesis constraints can be chosen. 
         [0094]    Thus the steps taken to achieve this are:
   1. Determine a faithful rounding precision and error bounds required for a multiplier.   2. Determine k and C for a CCT implementation.   3. Determine k and C for a VCT implementation.   4. Determine k for an LMS implementation.   5. Derive an RTL representation of each of the CCT, VCT and LMS implementations.   6. Use RTL synthesis to produce gate level netlists for each of the implementations.   7. Select the netlist which gives the best implementation according to desired factors such as number of gates, amount of silicon, power consumption, speed of operation.   8. Manufacture the thus selected netlist as a multiplier in an integrated circuit.   
 
         [0103]    In the embodiments described above the derivation of k and C and the RTL generation and synthesis can take place on a general purpose computer loaded with appropriate software. Alternatively, it can take place on a programmable RTL generator loaded with appropriate software. 
       Alternative Implementations 
       [0104]    1) In the embodiment above it was assumed that error requirement was faithful rounding. The error bounds can be used to calculate the necessary and sufficient conditions where a different error requirement is needed. Say we had the generic requirement: 
         [0000]      ∀ a,b|ε|&lt;α 2 n  
 
         [0105]    Where α&gt;½ this would then give us the following necessary and sufficient conditions on k and C for this to hold: 
         [0000]    
       
         
           
             
                 
             
              
             
               
                 
                    
                   
                     ɛ 
                     CCT 
                   
                    
                 
                 &lt; 
                 
                   α 
                    
                   
                       
                   
                    
                   
                     2 
                     n 
                   
                 
               
               ⇔ 
               
                 
                   α 
                    
                   
                       
                   
                    
                   
                     2 
                     
                       n 
                       - 
                       k 
                     
                   
                 
                 &gt; 
                 C 
                 &gt; 
                 
                   
                     
                       ( 
                       
                         1 
                         - 
                         α 
                       
                       ) 
                     
                      
                     
                       2 
                       
                         n 
                         - 
                         k 
                       
                     
                   
                   + 
                   k 
                   - 
                   2 
                 
               
             
           
         
       
       
         
           
             
               
                  
                 
                   ɛ 
                   VCT 
                 
                  
               
               &lt; 
               
                 α 
                  
                 
                     
                 
                  
                 
                   2 
                   n 
                 
               
             
             ⇔ 
             
               
                 
                   9 
                    
                   α 
                    
                   
                       
                   
                    
                   
                     2 
                     
                       n 
                       - 
                       k 
                     
                   
                 
                 - 
                 
                   
                     3 
                     8 
                   
                    
                   k 
                 
                 - 
                 
                   17 
                   8 
                 
                 - 
                 
                   
                     
                       ( 
                       
                         - 
                         1 
                       
                       ) 
                     
                     k 
                   
                   
                     2 
                     
                       k 
                       + 
                       2 
                     
                   
                 
               
               &gt; 
               C 
               &gt; 
               
                 
                   
                     ( 
                     
                       1 
                       - 
                       α 
                     
                     ) 
                   
                    
                   
                     2 
                     
                       n 
                       - 
                       k 
                       - 
                       1 
                     
                   
                 
                 - 
                 
                   k 
                   3 
                 
                 - 
                 
                   10 
                   9 
                 
                 + 
                 
                   
                     
                       ( 
                       
                         - 
                         1 
                       
                       ) 
                     
                     k 
                   
                   
                     9 
                     * 
                     
                       2 
                       
                         k 
                         + 
                         2 
                       
                     
                   
                 
               
             
           
         
       
       
         
           
             
               
                  
                 
                   ɛ 
                   LMS 
                 
                  
               
               &lt; 
               
                 α 
                  
                 
                     
                 
                  
                 
                   2 
                   n 
                 
               
             
             ⇔ 
             
               
                 
                   ( 
                   
                     
                       2 
                        
                       α 
                     
                     - 
                     1 
                   
                   ) 
                 
                  
                 
                   2 
                   
                     n 
                     - 
                     k 
                     + 
                     3 
                   
                 
               
               &gt; 
               
                 
                   24 
                    
                   
                       
                   
                    
                   k 
                 
                 - 
                 19 
                 + 
                 
                   3 
                    
                   
                     
                       ( 
                       
                         - 
                         1 
                       
                       ) 
                     
                     k 
                   
                 
                 + 
                 
                   
                     
                       4 
                        
                       
                         
                           ( 
                           
                             - 
                             1 
                           
                           ) 
                         
                         k 
                       
                     
                     - 
                     3 
                   
                   
                     2 
                     
                       k 
                       - 
                       4 
                     
                   
                 
               
             
           
         
       
     
         [0000]    So the parameter creation part of the Lossy Multiplier RTL Generator will take α as an extra input. The Lossy Multiplier RTL Generator can be designed to cope with more complex error constraints and is not limited to faithful rounding
 
2) The Lossy Multiplier RTL Generator can also produce an error report detailing the worst case error, worst case error vectors and other properties of the error.
 
In the case of CCT it can be shown that when 2C−k+1&lt;2 n-k  there are 2 n-k  worst case error vectors, these are constrained by:
 
         [0000]        a   k−1:0   =b   k−1:0 =2 k −1
 
         [0000]        b   n-1:k   =−p (2 k   +C−k+a   n-1:k (2 k −1))mod 2 n-k  
 
         [0000]    Where pa=1 mod 2 n-k . Otherwise there are (k+x+1)2 n-1  worst case error vectors where x is the number of times 2 divides C, for m=0, 1, 2 . . . , k+x these are constrained by: 
         [0000]        a   m =1  b   k+x-m-1:0   =a   m-1:0 =0 
         [0000]        a   n-k−x+m-1:m   b   n-m-1:k+x-m   +C/ 2 x =0 mod 2 n-k−x    
         [0000]    In the case of VCT it can be shown that there are always 2 n-k+1  worst case error vectors which are constrained by: 
         [0000]        b   n-1:k   =−p ( C+X/ 18 +a   n-1:k   b   k−1:0 )mod 2 n-k    
         [0000]    Where pa=1 mod 2 n-k  and a k−1:0 , b k−1:0  and X are defined in Table 1. 
         [0000]                                          TABLE 1                   X values for VCT worst case error vectors            4C + 3 &lt;                       2 n−k+1     k odd?   a k−1:0     b k−1:0     X               Yes   Yes   00101 . . . 10101   01010 . . . 01011   2 k -3k + 19       Yes   Yes   01010 . . . 01011   00101 . . . 10101   2 k -3k + 19       Yes   No   01010 . . . 10101   01010 . . . 10101   2 k+1 -3k + 16       Yes   No   00101 . . . 01011   00101 . . . 01011   2 k−1 -3k + 22       No   Yes   10101 . . . 10101   10101 . . . 10101   2 k+3  + 3k − 1       No   Yes   11010 . . . 01011   11010 . . . 01011   2 k−1 25 + 3k + 17       No   No   11010 . . . 10101   10101 . . . 01011   2 k+1 5 + 3k + 8       No   No   10101 . . . 01011   11010 . . . 10101   2 k+1 5 + 3k + 8                    
3) Instead of simply an n by n multiplication returning an n bit answer, we can generalize this to an n by m multiplication returning a p bit answer. In the case of CCT it can be shown that the necessary and sufficient conditions for faithfully rounding are:
 
         [0000]    
       
         
           
             
               
                  
                 
                   ɛ 
                   CCT 
                 
                  
               
               &lt; 
               
                 2 
                 
                   n 
                   + 
                   m 
                   - 
                   p 
                 
               
             
             ⇔ 
             
               
                 
                   
                     
                       2 
                       
                         n 
                         + 
                         M 
                         - 
                         p 
                         - 
                         k 
                       
                     
                     &gt; 
                     C 
                     &gt; 
                     
                       
                         min 
                          
                         
                           ( 
                           
                             n 
                             , 
                             m 
                             , 
                             k 
                           
                           ) 
                         
                       
                       - 
                       2 
                     
                   
                 
               
               
                 
                   
                     k 
                     ≤ 
                     
                       min 
                        
                       
                         ( 
                         
                           
                             max 
                              
                             
                               ( 
                               
                                 n 
                                 , 
                                 m 
                               
                               ) 
                             
                           
                           , 
                           
                             n 
                             + 
                             m 
                             - 
                             p 
                           
                         
                         ) 
                       
                     
                   
                 
               
             
           
         
       
     
         [0000]    4) Integer multiplication is used in many other datapath components, for example they are central to floating point multipliers. For example it can be shown that the following code will result used as the integer part of a floating point multiplier will be correct to 1 unit in the last place if truncmult(A,B,n+2) returns a faithful rounding of the top n+2 bits of product of A and B: 
         [0000]        A[n: 0]=(1 &lt;&lt;n )+mant a    
         [0000]        B[n: 0]=(1 &lt;&lt;n )+mant b    
         [0000]        C[n+ 1:0 ]=truncmult ( A,B,n+ 2) 
         [0000]      mantout[n−1:0 ]=C[n+ 1 ]?C[n: 1 ]:C[n− 1:0]
 
         [0106]      FIG. 6  shows schematically how the method described above can be implemented in the RTL generator of  FIG. 2 . For a given multiplier, a required bitwidth n for a rounding accuracy is supplied in parallel to each of a CCT parameter creating unit  60 , a VCT parameter creation unit  62 , and an LMS parameter creation unit  64 . These also receive the error requirements as shown in  FIG. 2  and using the create respectively C and k for the VCT and CCT units and k for the LMS unit. These values are then supplied to respective CCT, VCT and LMS RTL synthesis units ( 66 ,  68 ,  70 ) which produces a netlist for each scheme. This is passed to the selection unit  24  of  FIG. 2  which is controlled to select the best netlist for manufacture. 
         [0107]    As discussed above, all this can be implemented in dedicated RTL generators or in programmable generators or in software on a general purpose computer. Once the best netlist has been selected, it can be incorporated in the design of an integrated circuit. 
       BIBLIOGRAPHY 
       [0000]    
       
         [1] M. J. Schulte and J. Earl E. Swartzlander, “Truncated multiplication with correction constant,” in Workshop on VLSI Signal Processing, vol. VI, no. 20-22, October 1993, pp. 388-396. 
         [2] S. S. Kidambi, F. EI-Guibaly, and A. Antoniou, “Area-efficient multipliers for digital signal processing applications,” IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, vol. 43, no. 2, pp. 90-95, February 1996. 
         [3] E. J. King and J. Earl E. Swartzlander, “Data-dependent truncation scheme for parallel multipliers,” in Thirty-First Asilomar Conference on Signals, Systems &amp; Computers, vol. 2, no. 2-5, November 1997, pp. 1178-1182. 
         [4] J. E. Stine and O. M. Duverne, “Variations on truncated multiplication,” in Euromicro Symposium on Digital System Design, September 2003, pp. 112-119. 
         [5] N. Petra, D. De Caro, V. Garofalo, E. Napoli, and A. Strollo, “Truncated binary multipliers with variable correction and minimum mean square error,” Circuits and Systems I: Regular Papers, IEEE Transactions on, vol. 57, no. 6, pp. 1312-1325, june 2010. 
         [6], “Design of fixed-width multipliers with linear compensation function,” Circuits and Systems I: Regular Papers, IEEE Transactions on, vol. 58, no. 5, pp. 947-960, may 2011. 
         [7] R. Michard, A. Tisserandt, and N. Veyrat-Charvillon, “Carry predicition and selection for truncated multiplication,” in IEEE Workshop on Signal Processing Systems Design and Implementation, 2006, pp. 339-344. 
         [8] H. Park and J. Earl E. Swartzlander, “Truncated multiplications for the negative two&#39;s complement number system,” in 49th IEEE International Midwest Symposium on Circuits and Systems, 2006, pp. 204-208. 
         [9] S.-M. Kim, J.-G. Chung, and K. K. Parhi, “Low error fixed-width csd multiplier with efficient sign extension,” IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, vol. 50, no. 12, pp. 984-993, 2003. 
         [10] T.-B. Juang and S.-F. Hsiao, “Low-error carry-free fixed-width multipliers with low-cost compensation circuits,” IEEE Transactions on Circuits and Systems II, vol. 52, no. 6, pp. 299-303, June 2005. 
         [11] H.-J. Ko and S.-F. Hsiao, “Design and application of faithfully rounded and truncated multipliers with combined deletion, reduction, truncation, and rounding,” Circuits and Systems II: Express Briefs, IEEE Transactions on, vol. 58, no. 5, pp. 304-308, may 2011. 
         [12] K. E. Wires, M. J. Schulte, and J. E. Stine, “Variable-correction truncated floating point multipliers,” in Thirty-Fourth Asilomar Conference on Signals, Systems and Computers, vol. 2, 2000, pp. 1344-1348. 
         [13] E. G. W. III and M. J. Schulte, “Efficient function approximation using truncated multipliers and squarers,” in 17th IEEE Symposium on Computer Arithmetic, June 2005, pp. 232-239. 
         [14] A. Strollo, N. Petra, and D. DeCaro, “Dual-tree error compensation for high performance fixed-width multipliers,” Circuits and Systems II: Express Briefs, IEEE Transactions on, vol. 52, no. 8, pp. 501-507, aug. 2005. 
         [15] V. Garofalo, N. Petra, and E. Napoli, “Analytical calculation of the maximum error for a family of truncated multipliers providing minimum mean square error,” Computers, IEEE Transactions on, vol. PP, no. 99, p. 1, 2010. 
         [16] V. Garofalo, “Truncated binary multipliers with minimum mean square error: analytical characterization, circuit implementation and applications,” Ph.D. dissertation.