Fast and precise Fourier transforms
Many applications of fast Fourier transforms (FFT's), such as computer tomography, geophysical signal processing, high-resolution imaging radars, and prediction filters, require high-precision output. An error analysis reveals that the usual method of fixed-point computation of FFT's of vectors of length 2(l) leads to an average loss of l/2 bits of precision. This phenomenon, often referred to as computational noise, causes major problems for arithmetic units with limited precision which are often used for real-time applications, Several researchers have noted that calculation of FFT's with algebraic integers avoids computational noise entirely, see, e,g,, [1], We will combine a new algorithm for approximating complex numbers by cyclotomic integers with Chinese remaindering strategies to give an efficient algorithm to compute b-bit precision FFT's of length L, More precisely, we will approximate complex numbers by cyclotomic integers in Z[e(2 pi i/2 pi)] whose coefficients, when expressed as polynomials in e(2 pi i/2n), are bounded in absolute value by some integer M. For fixed n our algorithm runs in time O(log(M)), and produces an approximation with worst case error of O(1/M2n-2-1). We will prove that this algorithm has optimal worst case error by proving a corresponding lower bound on the worst case error of any approximation algorithm for this task. The main tool for designing the algorithms is the use of the cyclotomic units, a subgroup of finite index in the unit group of the cyclotomic held, First implementations of our algorithms indicate that they are fast enough to be used for the design of low-cost high-speed/high-precision FFT chips.
fourier transforms signal processing chinese remaindering cyclotomic units continued fractions cyclotomic fields effective chebotarev theorem integer linear programming residue number systems