Rader's FFT algorithm: Difference between revisions

Revision as of 22:02, 6 June 2003

Revision as of 22:07, 6 June 2003

Line 7:

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

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