Abstract:
Round-off error in fixed-point arithmetic is minimized by changing the magnitudes of two multipliers simultaneously. The dynamic range of an intermediate output is thus maximized to increase computation precision. A much smaller round-off error, caused by fixed-point arithmetic, thus results.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
       [0001]    N/A 
       STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT 
       [0002]    N/A 
       BACKGROUND OF THE INVENTION 
       [0003]    In an N-bit fixed-point computation, every integer value is in the range of [− 2   N-1 ,2 N-1- −1] If a given value exceeds 2 N-1 , an overflow occurs; if a given value is below −2 N-1 , an underflow occurs. Both overflow and underflow can be addressed by requiring that the input data be sufficiently small to avoid the possibility of overflow/underflow. To achieve these values, a single optimized multiplier is used. Thus, each multiplier in a fixed-point multiplication is either scaled up or scaled down by a power of the base. For example, the base is “2” in binary representation. After each multiplication, normalization of the intermediate output is performed. 
         [0004]    As each value is represented by a finite-length sequence of binary digits, rounding (or truncation) introduces a computation error which can often be treated in terms of an additive noise. Such a computation error is referred as rounding error. The dynamic range of the intermediate output is limited using a single multiplier, resulting in a sub-optimal round-off error. 
       BRIEF SUMMARY OF THE INVENTION 
       [0005]    A method for reducing round-off error in fixed-point arithmetic is provided. The method described herein changes the magnitudes of two multipliers simultaneously; the dynamic range of an intermediate output is thus maximized to increase computation precision. This method has a much smaller round-off error, caused by fixed-point arithmetic, than prior approaches. 
     
     
       BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS 
         [0006]    The invention will be more fully understood by reference to the following detailed description of the invention in conjunction with  FIG. 1 , which illustrates a method for reducing round-off error in fixed-point arithmetic, according to the presently disclosed invention. 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0007]    When multiplying two numbers A and B in a fixed-point process, existing techniques select the number with the smaller magnitude and scale it up as much as possible. For example, if |A|&gt;|B|, the existing technique would scale up the magnitude of B. To do this, the largest integer l is identified, such that 
         [0000]    
       
      
       b= 2   
       l 
       ·B+ε 
       2  
      
     
         [0000]    where l is a scaling factor, b is the rounded integer after scaling, 
         [0000]    
       
         
           
             
               
                 - 
                 
                   1 
                   2 
                 
               
               ≤ 
               
                 ɛ 
                 2 
               
               ≤ 
               
                 1 
                 2 
               
             
             , 
           
         
       
     
         [0000]    and most importantly b and A*b are in the range of └−2 N-1 ,2 N-1 −1┘ (i.e., there is no underflow or overflow). Then, 
         [0000]    
       
         
           
             
               A 
               · 
               B 
             
             = 
             
               
                 A 
                 · 
                 
                   
                     b 
                     - 
                     
                       ɛ 
                       2 
                     
                   
                   
                     2 
                     l 
                   
                 
               
               = 
               
                 
                   
                     A 
                     · 
                     b 
                   
                   
                     2 
                     l 
                   
                 
                 - 
                 
                   
                     A 
                     · 
                     
                       ɛ 
                       2 
                     
                   
                   
                     2 
                     l 
                   
                 
               
             
           
         
       
     
         [0000]    whereby the rounding error is 
         [0000]    
       
         
           
             
               
                 A 
                 · 
                 
                   ɛ 
                   2 
                 
               
               
                 2 
                 l 
               
             
             . 
           
         
       
     
         [0008]    The disadvantage of this known technique is that the scaling range is very limited, especially when one of the multipliers has a large magnitude, which leads to large rounding errors. 
         [0009]    In contrast, the presently disclosed technique, or process, provides an optimal setting for scaling factors such that the rounding error is minimized. An analytic formula which minimizes the rounding error is now illustrated. Assume a and b are scaled values of A and B, i.e., 
         [0000]        a= 2 k   ·A+ε   1 , and 
         [0000]        b= 2 l   ·B+ε   2    
         [0000]    where k,l are scaling factors (when k&gt;0, it is scaling up; when k&lt;0, it is scaling down), k+l is fixed, a,b are rounded integers after scaling, and 
         [0000]    
       
         
           
             
               
                 - 
                 
                   1 
                   2 
                 
               
               ≤ 
               
                 ɛ 
                 1 
               
             
             , 
             
               
                 ɛ 
                 2 
               
               ≤ 
               
                 
                   1 
                   2 
                 
                 . 
               
             
           
         
       
     
         [0010]    First, 
         [0000]    
       
         
           
             
               A 
               · 
               B 
             
             = 
             
               
                 
                   a 
                   - 
                   
                     ɛ 
                     1 
                   
                 
                 
                   2 
                   k 
                 
               
               · 
               
                 
                   b 
                   - 
                   
                     ɛ 
                     2 
                   
                 
                 
                   2 
                   l 
                 
               
             
           
         
       
       
         
           
             
               A 
               · 
               B 
             
             = 
             
               
                 
                   a 
                   · 
                   b 
                 
                 
                   2 
                   
                     k 
                     + 
                     l 
                   
                 
               
               + 
               
                 
                   
                     
                       - 
                       a 
                     
                      
                     
                         
                     
                      
                     
                       ɛ 
                       2 
                     
                   
                   - 
                   
                     b 
                      
                     
                         
                     
                      
                     
                       ɛ 
                       1 
                     
                   
                   + 
                   
                     
                       ɛ 
                       1 
                     
                      
                     
                       ɛ 
                       2 
                     
                   
                 
                 
                   2 
                   
                     k 
                     + 
                     I 
                   
                 
               
             
           
         
       
     
         [0000]    whereby the rounding error is 
         [0000]    
       
         
           
             
               
                 
                   
                     - 
                     a 
                   
                    
                   
                       
                   
                    
                   
                     ɛ 
                     2 
                   
                 
                 - 
                 
                   b 
                    
                   
                       
                   
                    
                   
                     ɛ 
                     1 
                   
                 
                 + 
                 
                   
                     ɛ 
                     1 
                   
                    
                   
                     ɛ 
                     2 
                   
                 
               
               
                 2 
                 
                   k 
                   + 
                   I 
                 
               
             
             , 
           
         
       
     
         [0000]    which is approximately equal to 
         [0000]    
       
         
           
             
               
                 
                   
                     - 
                     a 
                   
                    
                   
                       
                   
                    
                   
                     ɛ 
                     2 
                   
                 
                 - 
                 
                   b 
                    
                   
                       
                   
                    
                   
                     ɛ 
                     1 
                   
                 
               
               
                 2 
                 
                   k 
                   + 
                   1 
                 
               
             
             . 
           
         
       
     
       Since k+l is fixed, rounding error is minimized by minimizing −aε 2 −bε 1 . As 
       [0011]    
       
         
           
             
                
               
                 
                   
                     - 
                     a 
                   
                    
                   
                       
                   
                    
                   
                     ɛ 
                     2 
                   
                 
                 - 
                 
                   b 
                    
                   
                       
                   
                    
                   
                     ɛ 
                     1 
                   
                 
               
                
             
             ≤ 
             
               
                 
                    
                   a 
                    
                 
                 + 
                 
                    
                   b 
                    
                 
               
               2 
             
           
         
       
     
         [0000]    and a·b is in the fixed range of  2   k+l A·B, it follows that when |a| and |b| are closer in value, then 
         [0000]    
       
         
           
             
               
                  
                 a 
                  
               
               + 
               
                  
                 b 
                  
               
             
             2 
           
         
       
     
         [0000]    gets smaller, and so does |−aε 2 −bε 1 |. 
         [0012]    Thus, one would choose k and l, such that after scaling, the scaled values |a| and |b| are in the same range └2 n ,2 n+1 ), for some integer n, then the rounding error from a·b is minimized. 
         [0013]    With the above theoretical analysis, to derive appropriate settings which minimize the rounding error, an initial scaling factor pair (k 0 ,l 0 ) is defined, such that: 
         [0014]    1. The input value is scaled up as much as possible (up to the boundary of overflow/underflow); and 
         [0015]    2. After scaling, the two values |2 k     0   ·A| and |2 l     0   ·B| are as close to each other as possible. 
         [0016]    Next, the scaling factor pair is finely tuned via increasing or decreasing each value by one such that: 
         [0017]    1. There is no overflow/underflow; 
         [0018]    2. The value is scaled up as much as possible; and 
         [0019]    3. The rounding error is minimized. 
         [0020]    The rounding error is computed by directly computing (either addition or multiplication) the values with and without scaling. Usually after three or four fine tunings, the appropriate settings which minimize the rounding error will be derived, i.e., when the rounding error could not be further reduced. 
         [0021]    After all appropriate settings which minimize the rounding error for each multiplication are derived, the final output will be normalized to cancel out all scaling factors. 
         [0022]    The foregoing method for reducing round-off error in fixed-point arithmetic can be implemented by a wide variety of computing hardware and software, including specially programmed general purpose computing systems, custom-designed computing hardware including application specific integrated circuits (ASICs), etc. 
         [0023]    These and other embodiments of the invention illustrated above are intended by way of example and should not be viewed as limiting the scope of the disclosure or of the claims. The actual scope of the invention is to be limited solely by the scope and spirit of the following claims.