An algorithm for computing the Nth roots of unity in bit-reversed order

1980/12/01 by R. Keys, Robert G. Keys
Computer Science · Engineering · #Digital Filter Design and Implementation #Advancements in PLL and VCO Technologies #Numerical Methods and Algorithms

paper · doi:10.1109/tassp.1980.1163476

Abstract

Many versions of the fast Fourier transform require that the user provide a table of the Nth roots of unity arranged in bit-reversed order. An algorithm for creating this table is given in this paper. The algorithm uses approximately N complex multiplications for a time series of length N. The algorithm's main advantage is its insensitivity to computational errors. The cumulative roundoff error is proportional to <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">log₂ N</tex> . Additionally, the algorithm can be easily implemented in a high-level computer language.

Citations

• An algorithm for the machine calculation of complex Fourier series

Related

• An Adaptation of the Fast Fourier Transform for Parallel Processing
• Cooley-Tukey FFT over ℚ_p via Unramified Cyclotomic Extension
• The Arithmetic Fourier Transform
• A nonuniform fast Fourier transform based on low rank approximation
• An in-place truncated Fourier transform and applications to polynomial\n multiplication