Rader's FFT algorithm: Difference between revisions

Revision as of 21:24, 6 June 2003

Revision as of 21:27, 6 June 2003

Line 1:

'''Rader's FFT algorithm''' is a [[Fast Fourier Transform]] (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