Rader's FFT algorithm: Difference between revisions

Revision as of 04:31, 18 July 2003

Revision as of 19:03, 21 July 2003

Line 1:

'''Rader's algorithm''' is a [[Fastfast Fourier Transformtransform]] (FFT) algorithm that computes the [[discrete Fourier transform]] (DFT) of [[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