Multidimensional rational approximations with an application to linear transforms

Abstract

We discuss two new algorithms for the calculation of simultaneous rational approximations with specific computational characteristics. These approximations are used for efficient calculation of linear transforms. We develop an application in compression using the discrete cosine transform (DCT): however, the methods are also applicable to other integer transforms. To facilitate efficient multiplierless implementation for small field programmable gate arrays (FPGAs) or other low-cost processing elements, the rational approximations must have controlled precision (bits), and the numerators must use a minimum number of adds and shifts over the coefficient vector (minimum "length" representation). Our first method uses successive approximation of the coefficients in a suboptimal algorithm with low computational complexity to achieve low-length representations. The convergence of this method is analyzed, along with the closeness of the approximations. The suitability of this method for computational implementation, along with the quality of its representations, are evaluated in the context of continued fraction algorithms. The method is shown to be suitable for real-time computation for algorithms such as JPEG-2000. The second method, which finds the lowest length representation, requires more computation but is tractable for offline computation. This method employs search tree pruning and provides a lower bound for the representation length at each iteration. The computational complexity of this method is analyzed and compared with experimental results.