Rader's FFT algorithm: Difference between revisions

Revision as of 00:41, 10 June 2003

Revision as of 05:30, 10 June 2003

Line 3:

Recall that the DFT is defined by the formula

:<math> f_j = \frac{1}{n} \sum_{k=0}^{n-1} x_k e^{-\frac{2\pi i}{n} jk }

\qquad

j = 0,\dots,n-1. </math>

Line 9:

If ''n'' is a prime number, then the set of non-zero indices ''k'' = 1,...,''n''-1 forms a [[group (mathematics)|group]] under multiplication [[modulo]] ''n''. One consequence of this is that there exists a [[generating set of a group|generator]] of the group, an integer ''g'' such that ''k'' = ''g''^''q'' (mod ''n'') for any non-zero ''k'' and for some ''q'' in 0,...,''n''-2. Similarly ''j'' = ''g''^-''p'' (mod ''n'') for any non-zero ''j'' and for some ''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:

:<math> f_0 = \frac{1}{n} \sum_{k=0}^{n-1} x_k,</math>

:<math> f_{g^{-p}} = \frac{x_0}{n} + \frac{1}{n} \sum_{q=0}^{n-2} x_{g^q} e^{-\frac{2\pi i}{n} g^{-(p-q)} }

\qquad

p = 0,\dots,n-2. </math>