Rader's FFT algorithm: Difference between revisions

Revision as of 23:02, 19 January 2004

Revision as of 15:32, 6 March 2004

Line 1:

'''Rader's algorithm''' (1968) is a [[fast Fourier transform]] (FFT) algorithm that computes the [[discrete Fourier transform]] (DFT) of [[prime number|prime]] sizes by re-expressing the DFT as a cyclic [[convolution]]. (The other algorithm for FFTs of prime sizes, [[Bluestein's FFT algorithm|Bluestein's algorithm]], also works by rewriting the DFT as a convolution.)

Recall that the DFT is defined by the formula