Fast and precise computations of discrete Fourier transforms using cyclotomic integers
Joe Buhler, Mohammad Amin Shokrollahi, Volker Stemann · 1997
Many applications of fast fourier transforms (FITs), such as computer-tomography, geophysical signal processing, high resohstion imaging radars, and prediction filters, require high precision output.The usual method of fixed point computation of FIT's of vectors of length 21 leads to an average loss of f/2 bits of precision.This phenomenon, often referredto as computationalnoise, causes major problems for arithmeticunits with limited precision which areoften used for real time applications.Severalresearchers have noted thatcalculation of ITT's with algebraic integersavoids computationalnoise entirely,see, e.g., [3].We will show thatcomplex numbers can be approximated accurately by cyclotomic integers, andcombine this idea with Chinese remainderingstmtegiesin the cyclotomic integersto, rotsgbly,give a O(b'" L log( L) ) algorithm to compute b-bit precision FIT's of length L. The firstpart of the paperwill describe the ~strategy,assuminggood approximationalgorithms;the second partpresentsanew, general,andefticient algorithmfor a~proximatingcomplex numbersby cyclotomic integersin Z[e2*'\2 ] whose coefficients, when expressedas polynomials in e'~ii'", are bounded in absolute value by some integer M. For fixed n our algorithm runs in time 0(log(A4)), and produces an approximation with worst case errorof 0(1/A42"-2'1).We will prove that this algorithm has optimal worst case emor by proving a correspondinglower bound on the worstcase errorof any approximationalgorithm for this task.Firstimplementationsof our algorithmsindicate thatthey are fast enough to be used for the design of low cost high speecfhigh precision FIT-chips.