Rader's FFT Algorithm

Algorithm

Recall that the DFT is defined by the formula

$X_k = \sum_{n=0}^{N-1} x_n e^{-\frac{2\pi i}{N} nk } \qquad k = 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 = gq (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 gp modulo N. That means that we can rewrite the DFT using these new indices p and q as:

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

(Recall that x_n and X_k are implicitly periodic in N, and also that e2π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:

Read more about this topic: Rader's FFT Algorithm

Rader's FFT Algorithm - Algorithm