Rader's FFT algorithm: Difference between revisions

Revision as of 03:18, 25 May 2013

Revision as of 12:20, 5 May 2014

Line 5:

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 (Chu & Burrus, 1982); an alternative adaptation for DFTs of real data, using the discrete Hartley transform, was described by Johnson & Frigo (2007).

Winograd extended Rader's algorithm to include prime-power DFT sizes <math>p^m</math> (Winograd 1976; Winograd 1978), 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), 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]]s of Cooley–Tukey's [[Recursion_Recursion (computer_sciencecomputer science)|recursive]] decomposition of the DFT (Frigo and Johnson, 2005).

==Algorithm==