Rader's FFT algorithm


Rader's FFT algorithm

Rader's algorithm (1968) 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 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 (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 p^m (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 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 cases of Cooley-Tukey's recursive decomposition of the DFT (Frigo and Johnson, 2005).

Algorithm

Recall that the DFT is defined by the formula

: X_k = sum_{n=0}^{N-1} x_n e^{-frac{2pi i}{N} nk }qquadk = 0,dots,N-1.

If "N" is a prime number, then the set of non-zero indices "n" = 1,...,"N"–1 forms a group under multiplication modulo "N". One consequence of the number theory of such groups is that there exists a generator of the group (sometimes called a primitive root), an integer "g" such that "n" = "g""q" (mod "N") for any non-zero index "n" and for a unique "q" in 0,...,"N"–2 (forming a bijection from "q" to non-zero "n"). Similarly "k" = "g"–"p" (mod "N") for any non-zero index "k" and for a unique "p" in 0,...,"N"–2, where the negative exponent denotes the multiplicative inverse of "g""p" modulo "N". That means that we can rewrite the DFT using these new indices "p" and "q" as:

: X_0 = sum_{n=0}^{N-1} x_n,

: X_{g^{-p = x_0 + sum_{q=0}^{N-2} x_{g^q} e^{-frac{2pi i}{N} g^{-(p-q)} }qquadp = 0,dots,N-2.

(Recall that "x""n" and "X""k" are implicitly periodic in "N", and also that "e"2πi=1. Thus, all indices and exponents are taken modulo "N" as required by the group arithmetic.)

The final summation, above, is precisely a cyclic convolution of the two sequences "a""q" and "b""q" of length "N"–1 ("q" = 0,...,"N"–2) defined by:

:a_q = x_{g^q}:b_q = e^{-frac{2pi i}{N} g^{-q} }.

Evaluating the convolution

Since "N"–1 is composite, this convolution can be performed directly via the convolution theorem and more conventional FFT algorithms. However, that may not be efficient if "N"–1 itself has large prime factors, requiring recursive use of Rader's algorithm. Instead, one can compute a length-("N"–1) cyclic convolution exactly by zero-padding it to a length of at least 2("N"–1)–1, say to a power of two, which can then be evaluated in O("N" log "N") time without the recursive application of Rader's algorithm.

This algorithm, then, requires O("N") additions plus O("N" log "N") time for the convolution. In practice, the O("N") additions can often be performed by absorbing the additions into the convolution: if the convolution is performed by a pair of FFTs, then the sum of "x""n" is given by the DC (0th) output of the FFT of "a""q" plus "x"0, and "x"0 can be added to all the outputs by adding it to the DC term of the convolution prior to the inverse FFT. Still, this algorithm requires intrinsically more operations than FFTs of nearby composite sizes, and typically takes 3–10 times as long in practice.

If Rader's algorithm is performed by using FFTs of size "N"–1 to compute the convolution, rather than by zero padding as mentioned above, the efficiency depends strongly upon "N" and the number of times that Rader's algorithm must be applied recursively. The worst case would be if "N"–1 were 2"N"2 where "N"2 is prime, with "N"2–1 = 2"N"3 where "N"3 is prime, and so on. In such cases, supposing that the chain of primes extended all the way down to some bounded value, the recursive application of Rader's algorithm would actually require O("N"2) time. Such "N"j are called Sophie Germain primes, and such a sequence of them is called a Cunningham chain of the first kind. The lengths of Cunningham chains, however, are observed to grow more slowly than log2("N"), so Rader's algorithm applied in this way is probably not Ω("N"2), though it is possibly worse than O("N" log "N") for the worst cases. Fortunately, a guarantee of O("N" log "N") complexity can be achieved by zero padding.

References

* C. M. Rader, "Discrete Fourier transforms when the number of data samples is prime," "Proc. IEEE" 56, 1107–1108 (1968).
* S. Chu and C. Burrus, "A prime factor FTT ["sic"] 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.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Cooley–Tukey FFT algorithm — The Cooley–Tukey algorithm, named after J.W. Cooley and John Tukey, is the most common fast Fourier transform (FFT) algorithm. It re expresses the discrete Fourier transform (DFT) of an arbitrary composite size N = N1N2 in terms of smaller DFTs… …   Wikipedia

  • Bluestein's FFT algorithm — (1968), commonly called the chirp z transform algorithm (1969), is a fast Fourier transform (FFT) algorithm that computes the discrete Fourier transform (DFT) of arbitrary sizes (including prime sizes) by re expressing the DFT as a convolution.… …   Wikipedia

  • Cooley-Tukey FFT algorithm — The Cooley Tukey algorithm, named after J.W. Cooley and John Tukey, is the most common fast Fourier transform (FFT) algorithm. It re expresses the discrete Fourier transform (DFT) of an arbitrary composite size N = N 1 N 2 in terms of smaller… …   Wikipedia

  • Rader — is a surname, and may refer to:In law:* Dennis Rader, American serial killer * Randall Ray Rader, circuit judgeIn religion:* Paul Rader, the 15th General of The Salvation ArmyIn sports:* Dave Rader (American football), coach of the University of… …   Wikipedia

  • Fast Fourier transform — A fast Fourier transform (FFT) is an efficient algorithm to compute the discrete Fourier transform (DFT) and its inverse. There are many distinct FFT algorithms involving a wide range of mathematics, from simple complex number arithmetic to group …   Wikipedia

  • Discrete Fourier transform — Fourier transforms Continuous Fourier transform Fourier series Discrete Fourier transform Discrete time Fourier transform Related transforms In mathematics, the discrete Fourier transform (DFT) is a specific kind of discrete transform, used in… …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • List of algorithms — The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.If you intend to describe a new algorithm,… …   Wikipedia

  • Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и …   Википедия

  • List of harmonic analysis topics — This is a list of harmonic analysis topics, by Wikipedia page. See also list of Fourier analysis topics and list of Fourier related transforms, which are more directed towards the classical Fourier series and Fourier transform of mathematical… …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.