Rader's FFT algorithm: Difference between revisions

Revision as of 21:41, 20 June 2006

Revision as of 10:06, 22 June 2006

Line 28:

===Evaluating the convolution===

Since ''N''–1 is composite, this convolution can be performed directly via the [[convolution theorem]] and more conventional FFT algorithms. However, that may not be efficient if ''N''–1 itself has large prime factors, requiring recursive use of Rader's algorithm. If we knew the regular convolution for these two sequences, we could easilly compute the cyclic convolution in O(N) time. So, instead of the recursionInstead, one can compute a length-(''N''–1) cyclic convolution exactly by zero-padding it to a length of at least 2(''N''–1)–1, 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. (See [[Bluestein's FFT algorithm|Bluestein's algorithm]] for a more detailed discussion of this zero-padding trick.)

This algorithm, then, requires O(''N'') additions plus O(''N'' log ''N'') time for the convolution. In practice, the O(''N'') additions can often be performed by absorbing the additions into the convolution: if the convolution is performed by a pair of FFTs, then the sum of ''x''_''n'' is given by the DC (0th) output of the FFT of ''a''_''q'' plus ''x''₀, and ''x''₀ can be added to all the outputs by adding it to the DC term of the convolution prior to the inverse FFT. Still, this algorithm requires intrinsically more operations than FFTs of nearby composite sizes, and typically takes 3–10 times as long in practice.