Rader's FFT algorithm: Difference between revisions

Revision as of 15:19, 3 August 2021

Revision as of 07:49, 18 May 2022

Line 15:

k = 0,\dots,N-1. </math>

If ''N'' is a prime number, then the set of non-zero indices <math>n \in{} \{1,\dots,N-1\}</math> forms a [[group (mathematics)|group]] under multiplication [[modular arithmetic|modulo]] ''N''. One consequence of the [[number theory]] of such groups is that there exists a [[generating set of a group|generator]] of the group (sometimes called a [[Primitive root modulo n|primitive root]], which can be found quickly by exhaustive search or slightly better algorithms<ref>Donald E. Knuth, ''The Art of Computer Programming, vol. 2: Seminumerical Algorithms'', 3rd edition, section 4.5.4, p. 391 (Addison–Wesley, 1998).</ref>). This generator is an integer ''g'' such that <math>n = g^q \pmod N</math> for any non-zero index ''n'' and for a unique <math>q \in{} \{0,\dots,N-2\}</math> (forming a [[bijection]] from ''q'' to non-zero ''n''). Similarly, <math>k = g^{-p} \pmod N</math> for any non-zero index ''k'' and for a unique <math>p \in{} \{0,\dots,N-2\}</math>, where the negative exponent denotes the [[modular multiplicative inverse|multiplicative inverse]] of <math>g^p \mod N</math>. That means that we can rewrite the DFT using these new indices ''p'' and ''q'' as:

:<math> X_0 = \sum_{n=0}^{N-1} x_n,</math>