|
'''Rader's algorithm''' (1968),<ref>C. M. Rader, "Discrete Fourier transforms when the number of data samples is prime," Proc. IEEE 56, 1107–1108 (1968).</ref> named for Charles M. Rader of [[MIT Lincoln Laboratory|MIT Lincoln Lab]], 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).
Since Rader's algorithm only depends upon the periodicity of the DFT kernel, it is directly applicable to any other transform (of prime order) with a similar property, such as a [[number-theoretic transform]] or the [[discrete Hartley transform]].
The algorithm can be modified to gain a factor of two savings for the case of DFTs of real data, using a slightly modified re-indexing/permutation to obtain two half-size cyclic convolutions of real data;<ref>S. (Chu &and C. Burrus, 1982"A prime factor FTT <nowiki>[</nowiki>''sic''<nowiki>]</nowiki> algorithm using distributed arithmetic," '' IEEE Transactions on Acoustics, Speech, and Signal Processing'' '''30''' (2), 217–227 (1982).</ref> an alternative adaptation for DFTs of real data, usinguses the [[discrete Hartley transform,]].<ref wasname=Frigo05>Matteo describedFrigo byand Steven G. Johnson, &"[http://fftw.org/fftw-paper-ieee.pdf FrigoThe Design and Implementation of FFTW3]," ''Proceedings of the IEEE'' '''93''' (2), 216–231 (20072005).</ref>
Winograd extended Rader's algorithm to include prime-power DFT sizes <math>p^m</math>,<ref>S. (Winograd, 1976"On Computing the Discrete Fourier Transform", ''Proc. National Academy of Sciences USA'', '''73'''(4), 1005–1006 (1976).</ref><ref>S. Winograd, 1978"On Computing the Discrete Fourier Transform", ''Mathematics of Computation'', '''32'''(141), 175–199 (1978).</ref> and today Rader's algorithm is sometimes described as a special case of [[Winograd's FFT algorithm]], also called the ''multiplicative Fourier transform algorithm'' (Tolimieri et al., 1997),<ref>R. Tolimieri, M. An, and C.Lu, "Algorithms for Discrete Fourier Transform and Convolution," Springer-Verlag, 2nd ed., 1997.</ref> which applies to an even larger class of sizes. However, for [[composite number|composite]] sizes such as prime powers, the [[Cooley–Tukey FFT algorithm]] is much simpler and more practical to implement, so Rader's algorithm is typically only used for large-prime [[Base case (recursion)|base case]]s of Cooley–Tukey's [[Recursion (computer science)|recursive]] decomposition of the DFT.<ref (Frigo and Johnson, 2005).name=Frigo05/>
==Algorithm==
==References==
* C. M. Rader, "Discrete Fourier transforms when the number of data samples is prime," ''Proc. IEEE'' '''56''', 1107–1108 (1968).
<references/>
* S. Chu and C. Burrus, "A prime factor FTT <nowiki>[</nowiki>''sic''<nowiki>]</nowiki> algorithm using distributed arithmetic," '' IEEE Transactions on Acoustics, Speech, and Signal Processing'' '''30''' (2), 217–227 (1982).
* Matteo Frigo and Steven G. Johnson, "[http://fftw.org/fftw-paper-ieee.pdf The Design and Implementation of FFTW3]," ''Proceedings of the IEEE'' '''93''' (2), 216–231 (2005).
* S. Winograd, "On Computing the Discrete Fourier Transform", ''Proc. National Academy of Sciences USA'', '''73'''(4), 1005–1006 (1976).
* S. Winograd, "On Computing the Discrete Fourier Transform", ''Mathematics of Computation'', '''32'''(141), 175–199 (1978).
* R. Tolimieri, M. An, and C.Lu, "Algorithms for Discrete Fourier Transform and Convolution," Springer-Verlag, 2nd ed., 1997.
[[Category:FFT algorithms]]
|
