Fast and precise Fourier transforms

Many applications of fast Fourier transforms (FFT's), such as computer tomo graphy, geophysical signal processing, high-resolution imaging radars, and prediction filters, require high-precision output. An error analysis reveal s that the usual method of fixed-point computation of FFT's of vectors of l ength 2(l) leads to an average loss of l/2 bits of precision. This phenomen on, often referred to as computational noise, causes major problems for ari thmetic units with limited precision which are often used for real-time app lications, Several researchers have noted that calculation of FFT's with al gebraic integers avoids computational noise entirely, see, e,g,, [1], We wi ll combine a new algorithm for approximating complex numbers by cyclotomic integers with Chinese remaindering strategies to give an efficient algorith m to compute b-bit precision FFT's of length L, More precisely, we will app roximate 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 provi ng 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.