# Patent

## Title
Method and apparatus for performing lossy integer multiplier synthesis

## 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.

## Background
CROSS REFERENCE TO RELATED APPLICATIONS
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
1. Field
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.
2. Related Art
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.
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.
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.
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.
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=2n−1.
The scheme may be summarised algebraically:




  
    y
    =
    
      
        ⌊
        
          
            ab
            +
            
              
                2
                k
              
              ⁢
              
                f
                ⁡
                
                  (
                  
                    a
                    ,
                    b
                  
                  )
                
              
            
            -
            
              Δ
              k
            
          
          
            2
            n
          
        
        ⌋
      
      ⁢
      a
    
  
  ,
  b
  ,
  n
  ,
  
    k
    ∈
    N
  




The error introduced by doing so is:



  
    ɛ
    =
    
      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
            
            )
          
        
      
    
  



Where T=(ab+2kf (a·b)−ΔK)mod 2n. A design that exhibits faithful rounding is one such that:

∀a,b|ε|<2n 

Note that if the correct answer is exactly representable then this perfect answer must be returned by a faithfully rounded scheme, otherwise |ε|≧2n. 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'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<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<13. Further the schemes either find compensating functions heuristically or attempt to minimise the average absolute error or mean square error.
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
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.
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.
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


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


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
FIG. 1 shows a sum of addends array used in existing truncated multipliers;
FIG. 2 shows schematically an existing lossy multiplier synthesiser and RTL generator;
FIG. 3 shows a sum of addends array for a CCT multiplier embodying the invention;
FIG. 4 shows a sum of addends array for a VCT multiplier embodying the invention;
FIG. 5 shows a sum of addends array for an LMS multiplier embodying the invention; and,
FIG. 6 shows a block diagram of the synthesis of the three multiplier of FIGS. 3, 4 and 5 in parallel



DETAILED DESCRIPTION
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.
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 colk−1). LMS promotes elements from colk−1 but leaves the most extreme 4 elements behind as well as introducing a constant of 2n−k−1. Algebraically we can represent these as:



  
    
      
    
    ⁢
    
      
        
          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
              
            
          
          )
        
      
    
  



Faithful Rounding of CCT Multiplier Schemes
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.
In this case Δk−2kf(a,b)=Δk−2kC. To produce bounds on this object we need bounds on Δk (the value of the bits being discarded). When ak−1:0=bk−1:0=0 then Δk is entirely full of zeroes, hence Δk≧0. When ak−1:0=bk−1:0=2k−1 then Δk is entirely full of ones, hence Δk≦Σi=0k−1(2k−2i)=(k−1)2k+1. So we can provide the following tight bounds:

−C2k≦Δk−2kC≦(k−C−1)2k+1

T is bounded by 0≦T≦2n−2k and we will show that it can take any value when Δk takes its extreme values. If ak:0=2k then

T=((an−1:k+12k+1+2k)b+C2k)mod 2n 

T2−k−C=(2an−1:k+1+1)b mod 2n−k 

Now 2an−1:k−1+1 is odd hence coprime to 2n−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.
When Δk is maximal ak−1:0=bk−1:0=2k−1, under these conditions:

T=((an−1:k2k+2k−1)(bn−1:k2k+2k−1)+C2k−max(Δk))mod 2n 

T2−k−an−1:k(2k−1)−C−2k+k+1=bn−1:k(an−1:k2k+2k−1)mod 2n−k 

Now an−1:k2k+2k−1 is odd hence coprime to 2n−k hence regardless of the value of C we can always find an−1:k and bn−1:k such that any given T can be achieved when Δk is maximal.
So we can present the following tight bounds for the error of the CCT scheme:

−C2k≦εCCT≦2n−(C−k+2)2k+1

Given these bounds we work out the necessary and sufficient conditions for the faithful rounding of CCT multipliers:

|εCCT|<2n2n−k<C<k−2

This can then be used to derive a constant to add to include in a truncated sum of addends array for k columns truncated
Faithful Rounding of VCT Multiplier Schemes
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.
In this case Δk−2kf(a,b)=Δk−2kcolk−1−2kC. We will provide tight bounds on this object.
We first claim that μ=Δk−2kcolk−1 takes its maximal value when colk−1=0 and colk−2 is an alternating binary sequence. To see that colk−1=0, consider that μ can be written as (for an arbitrary function g):

μ=2jaj(−2k−1−jbk−1−j+bk−2−j:0)+g(ak−1:j+1,aj−1:0,b)

If we set j=0 in this equation and maximise μ over a0 and bk−1 we find a0=1 and by symmetry b0=1. Then, in the general case, if we maximise μ over aj and bk−1−j keeping in mind that bk−2−j>0 as b0=1 then we find that μ is maximised when aj≠bk−1−j and hence colk−1=0.
To see that colk−2 is an alternating binary sequence consider the case when there are two adjacent zeroes in colk−2 so we have a location where:

aj−1bk−jaj−1bk−j−1=0 0

ajbk−j−1ajbk−j−2=0 0

Assuming that aj≠bk−1−j for all j and, by symmetry, we may assume aj−1=1 solving the above equations means aj:j−1=“11” and bk−j:k−j−2=0. If however we set aj:j−1=“01” and bk−j:k−j−2=“010” we would actually increase μ by:




  
    
      
        2
        
          k
          -
          2
        
      
      +
      
        
          2
          
            k
            -
            j
            -
            1
          
        
        ⁢
        
          a
          ⁡
          
            [
            
              j
              -
              
                2
                ⁢
                
                  :
                
                ⁢
                0
              
            
            ]
          
        
      
      -
      
        
          2
          j
        
        ⁢
        
          b
          ⁡
          
            [
            
              k
              -
              j
              -
              
                3
                ⁢
                
                  :
                
                ⁢
                0
              
            
            ]
          
        
      
    
    >
    
      
        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
              
            
            ]
          
        
      
    
    >
    0
  




Hence when μ is maximal, adjacent zeroes never appear in colk−2. Further if adjacent ones were to appear in colk−2 then there would be a one in column colk−1, which contradicts the previous assumption. Conclude that colk−1=0 and colk−2 is an alternating binary sequence when μ is maximal. These two conditions uniquely determine a and b, from which can be calculated the bounds:




  μ
  ≤
  
    
      
        
          (
          
            
              3
              ⁢
              
                
              
              ⁢
              k
            
            -
            2
          
          )
        
        ⁢
        
          2
          
            k
            -
            1
          
        
      
      +
      
        
          (
          
            -
            1
          
          )
        
        k
      
    
    9
  




The lower bound on μ is achieved when aj=bk−1−j for all j, a0=b0 and the interior of a and b are alternating binary sequences. We will demonstrate each of these properties in turn.
First recall that we can write for some function g:

μ=2jaj(−2k−1−jbk−1−j+bk−2−j:0)+g(ak−1:j+1,aj−1:0,b)

If aj≠bk−1−j and aj=1 then μ can be decreased by 2k−1−j−bk−2−j:0>0 by setting bk−1−j=1, hence μ being minimal implies aj=bk−1−j for all j.
Secondly if a0=bk−1=0 then μ can be decreased by 2k−1−bk−2:0>0 by setting a0=1.
Finally we need to show that the interior of a and b are alternating binary sequences when μ is minimal. First we introduce some notation:




  
    
      
        
          γ
          ⁡
          
            (
            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
              )
            
          
        
      
    
  




Where X=xm−1 . . . x1x0/2m<1 and Y=yq−1 . . . y1y0/2q<1, we will then show various strings within a never occur:

    
    
        γ(010)−γ(000)=(X+Y)/2−1<0 so “000” never occurs
        γ(101)−γ(111)=−(X+Y)<0 when k>3 so “111” never occurs
        If “1001” were feasible then γ(1001)≦γ(1010),γ(0101),γ(1011),γ(1101) this would imply

0≦1+X−4Y 

0≦1+Y−4×

0≦−1+X+2Y 

0≦−1+Y+2X 

But the only solution to this is X=Y=1⁄3 which is not possible given that X and Y are finite binary numbers. Hence “1001” never occurs.

    
    


If “0110” were feasible then γ(0110)≦γ(0101),γ(1010), γ(0010),γ(0100) this would imply:

0≦−2+4Y−X 

0≦−2+4X−Y 

0≦2−2X−Y 

0≦2−2Y−X 

But the only solution to this is X=Y=2⁄3 which is not possible given that X and Y are finite binary numbers. Hence “0110” never occurs.

The fact that these strings never occur implies that the interior of a and b are alternating binary sequences. The fact that aj=bk−1−j for all j, a0=b0 and the interior of a and b are alternating binary sequences uniquely determine a and b, from which can be calculated the bounds:




  μ
  ≤
  
    
      
        
          (
          
            
              3
              ⁢
              
                
              
              ⁢
              k
            
            +
            7
          
          )
        
        ⁢
        
          2
          
            k
            -
            1
          
        
      
      +
      
        
          (
          
            -
            1
          
          )
        
        k
      
    
    9
  




We are now in a position to tightly bound Δk−2kcolk−1−2kC:




  
    -
    
      
        
          
            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
  




We will now show that T can take any value whenever μ is extreme. If μ is maximal then colk−1=0 and colk−2 is an alternating binary sequence. These conditions uniquely determine ak−1:0 and bk−1:0 up to swapping. When k is odd these conditions imply ak−1:0=(2k−11)/3 and bk−1:0=(2k+1)/3, T is then defined by:



  
    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
        
      
    
  



Now an−1:k2k+(2k−1−1)/3 is odd hence coprime to 2n−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 ak−1:0=bk−1:0=(2k−1)/3 or ak−1:0=bk−1:0=(2k−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.
If μ is minimal then a0=b0=1, a1=bk−1−j for all j and the interior of colk−1 is an alternating binary sequence. These conditions uniquely determine ak−1:0 and bk−1:0 up to swapping. When k is even these conditions imply ak−1:0=(5*2k−1−1)/3 and bk−1:0=(2k+1+1)/3, T is then defined by:



  
    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
        
      
    
  



Now an−1:k2k+(5*2k−1−1)/3 is odd hence coprime to 2n−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 ak−1:0=bk−1:0=(2k+1−1)/3 or ak−1:0=bk−1:0=(5*2k−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.
Given T can take any value when μ is extreme allows us to state the error the VCT scheme:




  
    -
    
      
        
          
            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
    
  




Given these bounds we work out the necessary and sufficient conditions for the faithful rounding of VCT multipliers:

|εVCT|<2n3*2n−k+1−k−2<6C<k−7

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
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
The error bounds on this scheme were first reported in [16] and can be summarised by:




  
    
      -
      
        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
          
        
      
      )
    
  




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:

|εLMS|<2n9*2n−k+1<6k+3+(−1)k 

Lossy Multiplier RTL Generator

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:
Where the parameters are calculated as follows:



  
    
      
        
          
            
              k
              CCT
            
            =
            
            ⁢
            
              max
              ⁡
              
                (
                
                  k
                  :
                  
                    ∃
                    
                      
                        C
                        ⁢
                        
                          
                        
                        ⁢
                        
                          s
                          .
                          t
                          .
                          
                            
                          
                          ⁢
                          
                            2
                            
                              n
                              -
                              k
                            
                          
                        
                      
                      >
                      C
                      >
                      
                        k
                        -
                        2
                      
                    
                  
                
                )
              
            
          
          ⁢
          
            
          
        
      
    
    
      
        
          =
          
          ⁢
          
            max
            ⁡
            
              (
              
                k
                :
                
                  
                    2
                    n
                  
                  >
                  
                    
                      (
                      
                        k
                        -
                        1
                      
                      )
                    
                    ⁢
                    
                      2
                      k
                    
                  
                
              
              )
            
          
        
      
    
  




  
    
      C
      CCT
    
    =
    
      min
      ⁢
      
        
      
      ⁢
      
        Hamm
        ⁡
        
          (
          
            C
            :
            
              
                2
                
                  n
                  -
                  
                    k
                    CCT
                  
                
              
              >
              C
              >
              
                
                  k
                  CCT
                
                -
                2
              
            
          
          )
        
      
    
  




  
    
      k
      VCT
    
    =
    
      max
      ⁡
      
        (
        
          k
          :
          
            ∃
            
              
                
                  C
                  ⁢
                  
                    
                  
                  ⁢
                  
                    s
                    .
                    t
                    .
                    
                      
                    
                    ⁢
                    3
                  
                  *
                  
                    2
                    
                      n
                      -
                      k
                      +
                      1
                    
                  
                
                -
                k
                -
                2
              
              >
              
                6
                ⁢
                
                  
                
                ⁢
                C
              
              >
              
                k
                -
                7
              
            
          
        
        )
      
    
  




  
    
      C
      VCT
    
    =
    
      min
      ⁢
      
        
      
      ⁢
      
        Hamm
        ⁡
        
          (
          
            C
            :
            
              
                
                  3
                  *
                  
                    2
                    
                      n
                      -
                      
                        k
                        VCT
                      
                      +
                      1
                    
                  
                
                -
                
                  k
                  VCT
                
                -
                2
              
              >
              
                6
                ⁢
                
                  
                
                ⁢
                C
              
              >
              
                
                  k
                  VCT
                
                -
                7
              
            
          
          )
        
      
    
  




  
    
      k
      LMS
    
    =
    
      max
      ⁡
      
        (
        
          k
          :
          
            
              2
              
                n
                -
                k
                +
                1
              
            
            >
            
              
                6
                ⁢
                
                  
                
                ⁢
                k
              
              +
              3
              +
              
                
                  (
                  
                    -
                    1
                  
                  )
                
                k
              
            
          
        
        )
      
    
  



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:

    
    
        kCCT=5 CCCT=4 kVCT=6 CVCRr=0 kLMS=6
    
    


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.
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.


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
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:

∀a,b|ε|<α2n 

Where α>1⁄2 this would then give us the following necessary and sufficient conditions on k and C for this to hold:



  
    
      
    
    ⁢
    
      
        
          
          
            ɛ
            CCT
          
          
        
        <
        
          α
          ⁢
          
            
          
          ⁢
          
            2
            n
          
        
      
      ⇔
      
        
          α
          ⁢
          
            
          
          ⁢
          
            2
            
              n
              -
              k
            
          
        
        >
        C
        >
        
          
            
              (
              
                1
                -
                α
              
              )
            
            ⁢
            
              2
              
                n
                -
                k
              
            
          
          +
          k
          -
          2
        
      
    
  




  
    
      
        
        
          ɛ
          VCT
        
        
      
      <
      
        α
        ⁢
        
          
        
        ⁢
        
          2
          n
        
      
    
    ⇔
    
      
        
          9
          ⁢
          α
          ⁢
          
            
          
          ⁢
          
            2
            
              n
              -
              k
            
          
        
        -
        
          
            3
            8
          
          ⁢
          k
        
        -
        
          17
          8
        
        -
        
          
            
              (
              
                -
                1
              
              )
            
            k
          
          
            2
            
              k
              +
              2
            
          
        
      
      >
      C
      >
      
        
          
            (
            
              1
              -
              α
            
            )
          
          ⁢
          
            2
            
              n
              -
              k
              -
              1
            
          
        
        -
        
          k
          3
        
        -
        
          10
          9
        
        +
        
          
            
              (
              
                -
                1
              
              )
            
            k
          
          
            9
            *
            
              2
              
                k
                +
                2
              
            
          
        
      
    
  




  
    
      
        
        
          ɛ
          LMS
        
        
      
      <
      
        α
        ⁢
        
          
        
        ⁢
        
          2
          n
        
      
    
    ⇔
    
      
        
          (
          
            
              2
              ⁢
              α
            
            -
            1
          
          )
        
        ⁢
        
          2
          
            n
            -
            k
            +
            3
          
        
      
      >
      
        
          24
          ⁢
          
            
          
          ⁢
          k
        
        -
        19
        +
        
          3
          ⁢
          
            
              (
              
                -
                1
              
              )
            
            k
          
        
        +
        
          
            
              4
              ⁢
              
                
                  (
                  
                    -
                    1
                  
                  )
                
                k
              
            
            -
            3
          
          
            2
            
              k
              -
              4
            
          
        
      
    
  



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<2n−k there are 2n−k worst case error vectors, these are constrained by:

ak−1:0=bk−1:0=2k−1

bn−1:k=−p(2k+C−k+an−1:k(2k−1))mod 2n−k 

Where pa=1 mod 2n−k. Otherwise there are (k+x+1)2n−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:

am=1bk+x−m−1:0=am−1:0=0

an−k−x+m−1:mbn−m−1:k+x−m+C/2x=0 mod 2n−k−x 

In the case of VCT it can be shown that there are always 2n−k+1 worst case error vectors which are constrained by:

bn−1:k=−p(C+X/18+an−1:kbk−1:0)mod 2n−k 

Where pa=1 mod 2n−k and ak−1:0, bk−1:0 and X are defined in Table 1.








TABLE 1







X values for VCT worst case error vectors











4C + 3 <






2n−k+1
k odd?
ak−1:0
bk−1:0
X





Yes
Yes
00101 . . . 10101
01010 . . . 01011
2k-3k + 19


Yes
Yes
01010 . . . 01011
00101 . . . 10101
2k-3k + 19


Yes
No
01010 . . . 10101
01010 . . . 10101
2k+1-3k + 16


Yes
No
00101 . . . 01011
00101 . . . 01011
2k−1-3k + 22


No
Yes
10101 . . . 10101
10101 . . . 10101
2k+3 + 3k − 1


No
Yes
11010 . . . 01011
11010 . . . 01011
2k−125 + 3k + 17


No
No
11010 . . . 10101
10101 . . . 01011
2k+15 + 3k + 8


No
No
10101 . . . 01011
11010 . . . 10101
2k+15 + 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:





  
    
      
      
        ɛ
        CCT
      
      
    
    <
    
      2
      
        n
        +
        m
        -
        p
      
    
  
  ⇔
  
    
      
        
          
            2
            
              n
              +
              M
              -
              p
              -
              k
            
          
          >
          C
          >
          
            
              min
              ⁡
              
                (
                
                  n
                  ,
                  m
                  ,
                  k
                
                )
              
            
            -
            2
          
        
      
    
    
      
        
          k
          ≤
          
            min
            ⁡
            
              (
              
                
                  max
                  ⁡
                  
                    (
                    
                      n
                      ,
                      m
                    
                    )
                  
                
                ,
                
                  n
                  +
                  m
                  -
                  p
                
              
              )
            
          
        
      
    
  




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:

A[n:0]=(1<<n)+manta 

B[n:0]=(1<<n)+mantb 

C[n+1:0]=truncmult(A,B,n+2)

mantout[n−1:0]=C[n+1]?C[n:1]:C[n−1:0]

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.
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


    [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 & 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'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.

## Claims

1. A non-transitory machine readable medium storing instructions for causing a machine to perform a method for deriving a Register Transfer Language (RTL) representation for a logic circuit for performing a multiplication as a sum of addends operation with a desired rounding precision, the method comprising:
determining an error requirement to be met for the desired rounding precision;
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;
discarding columns according to the determined respective number of columns for each of the CCT, VCT and LMS implementations;
including the constant in the sum of addends for each of the CCT and VCT implementations;
deriving an RTL representation of the sum of addends operation for each of the CCT, VCT and LMS implementations, after performing the discarding and the including of the constant;
synthesizing a respective netlist for each of the respective RTL representations; and
selecting one of the synthesized netlists for production of a logic circuit.

2. A non-transitory machine readable medium storing instructions for causing a machine to perform a method for deriving RTL for a logic circuit according to claim 1, wherein k and C are selected by maximizing the size of k and minimizing the number of binary ones in the binary expansion of C.

3. A non-transitory machine readable medium storing instructions for causing a machine to perform a method for deriving RTL for a logic circuit according to claim 2, wherein kCCT is a minimum hamming weight for all possible values of C that satisfy the condition that C be less than 2(n−kCCT) and greater than (kCCT−2).

4. A non-transitory machine readable medium storing instructions for causing a machine to perform a method for deriving RTL for a logic circuit according to claim 1, wherein the number of columns k for the CCT (kCCT) implementation is a maximum of all values of k that satisfy the condition that 2n is greater than (k−1)2k.

5. A non-transitory machine readable medium storing instructions for causing a machine to perform a method for deriving RTL for a logic circuit according to claim 1, wherein the number of columns k for the VCT implementation is a maximum of all values of k that satisfy the condition that 2n is greater than (k−1)2k.

6. A non-transitory machine readable medium storing instructions for causing a machine to perform a method for deriving RTL for a logic circuit according to claim 1, wherein the number of columns k for the VCT implementation and the constant for the VCT implementation are selected as kVCT=max(k:∃Cs.t.3*2n−k+1−k−2>6C>k−7) and CVCT=min hamm(C:3*2n−kVCT+1−kVCT−2>6C>kVCT−7).

7. A non-transitory machine readable medium storing instructions for causing a machine to perform a method for deriving RTL for a logic circuit according to claim 1, further comprising manufacturing an integrated circuit with the selected netlist.

8. A non-transitory machine readable medium storing instructions for causing a machine to perform a method for deriving RTL for a logic circuit according to claim 1, further comprising maximizing k for both CCT and VCT implementations.

9. A non-transitory machine readable medium storing instructions for causing a machine to perform a method for deriving RTL for a logic circuit according to claim 1, further comprising providing an additional error constraint on the selection of k and C parameters for one or more of the CCT, VCT and LMS implementations.

10. A non-transitory machine readable medium storing instructions for causing a machine to perform a method for deriving RTL for a logic circuit according to claim 1, further comprising producing an error report including a worse case error for the resulting lossy multiplier netlist.

11. A non-transitory machine readable medium storing instructions for causing a machine to perform a method for deriving RTL for a logic circuit according to claim 1, wherein for n=8, k for the CCT implementation is 5, C for the CCT implementation is 4, k for the VCT implementation is 6, C for the VCT implementation is 0, and k for the LMS implementation is 6.

12. A non-transitory machine readable medium storing machine executable instructions for a method, comprising:
determining an error requirement to be met for the desired rounding precision;
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;
for each of the CCT, VCT and LMS implementations, discarding columns according to the determined number of columns;
for each of the CCT and VCT implementations, including the constant in the sum of addends;
deriving an RTL representation of the sum of addends operation for each of the CCT, VCT and LMS implementations, after performing the discarding and including of the constant;
synthesizing a respective netlist for each of the respective RTL representations; and
selecting one of the synthesized netlists.

13. The machine readable medium of claim 12, wherein the method further comprises selecting k and C for the VCT implementation by maximizing the size of k and minimizing the number of binary ones in the binary expansion of C.

14. The machine readable medium of claim 12, wherein the method further comprises selecting k and C for the CCT implementation by maximizing the size of k and minimizing the number of binary ones in the binary expansion of C.

15. The machine readable medium of claim 12, wherein the number of columns k for the CCT (kCCT) implementation is a maximum of all values of k that satisfy the condition tha*2t 2n is greater than (k−1)2k.

16. The machine readable medium of claim 15, wherein according to claim 2, wherein kCCT is a minimum hamming distance for all possible values of C that satisfy the condition that C be less than 2(n−kCCT) and greater than (kCCT−2).

17. The machine readable medium of claim 12, wherein the number of columns k for the VCT implementation (kvct) is a maximum of all values of k that satisfy the condition that 2n is greater than (k−1)2k.

18. The machine readable medium of claim 12, wherein kvct and the constant for the VCT (CVCT) implementation are selected as kVCT=max(k:∃Cs.t.3*2n−k+1−k−2>6C>k−7) and CVCT=min hamm(C:3*2n−kVCT+1−kVCT−2>6C>kVCT−7).

19. The machine readable medium of claim 12, further comprising manufacturing an integrated circuit with the selected netlist.

20. The machine readable medium of claim 12, further comprising maximizing k for both CCT and VCT implementations.