レーダーのFFTアルゴリズム
X k = ∑ n = 0 N − 1 x n e − 2 π i N n k k = 0 , ... , N − 1. {\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}nk}\qquad k=0,\dots ,N-1.}
N が素数の場合、n =1,...,N–1の添字はNを法とする乗算について群をなす。数論によるとこのような群については生成元(原始根)が存在し、これを gとすると、すべての n は q = 0,...,N–2 を用いて n = g (mod N) と表される。(qとnの間に全単射が存在する。) n と k の添字をこの置き換えを用いて新しい添字 q と p により表すと、定式は以下のように置き換えられる。
X 0 = ∑ n = 0 N − 1 x n , {\displaystyle X_{0}=\sum _{n=0}^{N-1}x_{n},}
X g − p = x 0 + ∑ q = 0 N − 2 x g q e − 2 π i N g − ( p − q ) p = 0 , ... , N − 2. {\displaystyle 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.}
上式は以下に示される長さ N–1(q =0,...,N–2) の数列 aq と bq の巡回畳み込み積分となっている。
a q = x g q {\displaystyle a_{q}=x_{g^{q}}}
b q = e − 2 π i N g − q . {\displaystyle b_{q}=e^{-{\frac {2\pi i}{N}}g^{-q}}.}