Rader's FFT algorithm: Difference between revisions

Revision as of 21:28, 6 June 2003

Revision as of 22:02, 6 June 2003

Line 11:

:<math> f_0 = \frac{1}{n} \sum_{k=0}^{n-1} x_k,</math>

:<math> f_{g^{-p}} = \frac{x_0}{n} + \frac{1}{n} \sum_{q=0}^{n-2} x_{g^q} e^{-\frac{2\pi i}{n} g^{q-(p-q)} }

\qquad

p = 0,\dots,n-2. </math>

Line 18:

:<math>a_q = x_{g^q}</math>

:<math>b_q = e^{-\frac{2\pi i}{n} g^{-q} }.</math>

Since ''n''-1 is composite, this convolution can be performed directly via the [[convolution theorem]] and more conventional FFT algorithms. However, this may not be efficient if ''n''-1 itself has large prime factors, requiring recursive use of Rader's algorithm. Instead, one can compute a cyclic convolution exactly by zero-padding it into a linear convolution of at least twice the length, say to a power of two, which can then be evaluated in O(''n'' log ''n'') time without the recursive application of Rader's algorithm.