Content deleted Content added
m phrasing |
clarified modulo n |
||
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 [[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''<sup>''q''</sup> (mod ''n'') for all non-zero ''k'' and for some ''q'' in 0,...,''n''-2. Similarly ''j'' = ''g''<sup>-''p''</sup> (mod ''n'') for all non-zero ''j'' and for some ''p'' in 0,...,''n''-2, where the negative exponent denotes the multiplicative inverse of ''g''<sup>''p''</sup> 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>
Line 14:
\qquad
p = 0,\dots,n-2. </math>
(Recall that ''x''<sub>''k''</sub> and ''f''<sub>''j''</sub> are implicitly periodic in ''n'', and ''e''<sup>2πi</sup>=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''<sub>''q''</sub> and ''b''<sub>''q''</sub> of length ''n''-1 (''q'' = 0,...,''n''-2) defined by:
| |||