Linear interpolation operator

Abstract

A linear interpolation operator for determining the value y of a function of x when one knows the value y 1 corresponding to x 1 , and a value y 2 corresponding to x 2 (where x 2 <x≧x 1 ), comprises a first calculation circuit which determines the equation (x m +x M )/2; a second calculation which determines the equation (y m +y M )/2; a comparison circuit which compares x with (x m +x M )/2 so as to determine which one of the intervals [x m ,(x m +x M )2], [(x m +x M )/2, x M ] contains x and to feed back the limits of the selected interval into the first calculation circuit and the limits of the interval corresponding in y into the second calculation circuit.

I claim:  
     
       1. A linear interpolation operator apparatus for determining a value of y, wherein y is a function of x, x is in a range between a known lower value x 1  and a known higher value x 2 , and known values y 1  and y 2  correspond respectively to x 1  and x 2 , comprising: 
       first calculation means for determining (x m +x M )/2, wherein the initial value of a lower range limit x m =x 1  and the initial value of an upper range limit x M =x 2 ;  
       said first calculation means comprising input registers, an adder and a divider by two;  
       second calculation means for determining (y m +y M )/2, wherein the initial value of a lower range limit y m =y 1  and the initial value of an upper range limit y M =y 2 ;  
       said second calculation means comprising input registers, an adder and a divider by two;  
       input means for inputting x;  
       comparing means for comparing x with (x m +x M )/2, said comparing means comprising a comparator including a first input terminal coupled to said divider by two of said first calculation means, a second input terminal coupled to said input means and an output;  
       feedback means responsive to the output of said comparator for transmitting the output of said divider by two of each of said first and second calculation means to a respective input register to reset corresponding upper or lower range limits, said feedback means comprising controlling gates for transmitting said output of said divider by two as a function of the comparator output; and  
       output means coupled to said divider by two of said second calculation means for providing the value y after a predetermined number of cycles.  
     
     
       2. A linear interpolation operator apparatus according to  claim 1 , wherein the same calculation means are repetitively cycled. 
     
     
       3. A linear interpolation operator apparatus according to  claim 1 , wherein said first and second calculation means, respectively, are pipe-line connected, the output of one calculation means being transmitted to the next calculation means. 
     
     
       4. A linear interpolation operator apparatus according to claims  1  to barycentric calculations, wherein the value y=(aA+bB)/(A+B) is to be calculated, wherein the values of the parameters are chosen as follows: 
       
         
           x 1 =0; x 2 =a+b; y 1 =A; y 2 =B and x=b.  
         
       
     
     
       5. A linear interpolation operator apparatus according to any of claims  1 ,  2  and  3  to the calculation of the product of two numbers A and B divided by a third number C (y=A*B/C), wherein the values of the parameters are chosen as follows: 
       
         
           x 1 =0; x 2 =C; y 1 =0; y 2 =B and x=A.  
         
       
     
     
       6. A circuit for performing linear interpolation, given first and second x values and corresponding first and second y values, to generate a y value corresponding to an intermediate x value between the first and second x values, comprising: 
         first and second x - input registers, which initially contain the first and second x values;    
         first and second y - input registers, which initially contain the first and second y values;    
         a first circuit for calculating a midpoint between the values in the first and second x - input registers;    
         a second circuit for calculating a midpoint between the values in the first and second y - input registers;    
         a comparator circuit for comparing the intermediate x value with the calculated midpoint between the values in the first and second x - input registers;    
         a gating circuit for loading the calculated x and y midpoints into the first x - input register and the first y - input register, respectively, if the intermediate x value is greater than the calculated midpoint between the first and second x - input registers, and for loading the calculated x and y midpoints into the second x - input register and the second y - input register, respectively, if the intermediate x value is less than the calculated midpoint between the first and second x - input registers, in order to begin a following calculation cycle; and    
       
         output means, coupled to the second circuit for calculating a midpoint, for providing an output y value after a predetermined criteria has been satisfied.  
       
     
     
       7. The circuit of  claim 6 , wherein the predetermined criteria has been satisfied after a predetermined number of calculation cycles.  
     
     
       8. The circuit of  claim 6 , wherein the calculated x and y midpoints are one- half way between the values in the registers for both the x - registers and the y - registers, respectively, and wherein each circuit for calculating a midpoint comprise a summing circuit followed by a divide - by -   2  circuit.    
     
     
       9. The circuit of  claim 8 , wherein the divide- by -   2  circuits each comprise a circuit for shifting a binary number by one bit position.    
     
     
       10. The circuit of  claim 6 , wherein the first circuit for calculating a midpoint comprises: 
         a first summer for summing the values contained in the first and second x - input registers; and    
         a divide - by -   2  circuit connected to an output of the first summer for dividing such output by  2 ;    
       
         and wherein the second circuit for calculating a midpoint comprises:  
       
         a second summer for summing the values contained in the first and second y - input registers; and    
         a divide - by -   2  circuit connected to an output to the second summer for dividing such output by  2 .    
     
     
       11. The circuit of  claim 6 , wherein the predetermined criteria comprises a comparison between the values in the first and second y- input registers being less than a predetermined value.    
     
     
       12. The circuit of  claim 6 , wherein the predetermined criteria comprises a comparison between the intermediate x value and either of the values in the first and second x- input registers being less than a predetermined value.