高速フーリエ変換
N = PQ とする。N 次離散フーリエ変換を、以下のようにP 次離散フーリエ変換とQ 次離散フーリエ変換に分解する。
N 次離散フーリエ変換:
F ( n ) = ∑ k = 0 N − 1 f ( k ) exp  ( − 2 π i n k N ) {\displaystyle F(n)=\sum _{k=0}^{N-1}f(k)\exp \left(-2\pi i{\frac {nk}{N}}\right)}
を、n = 0, 1, ..., N − 1 について計算することを考える。n, k を次のように書き換える。ただし 0 ≤ n ≤ N − 1 また 0 ≤ k ≤ N − 1 である。
n = s Q + r 0 ≤ s ≤ P − 1 , 0 ≤ r ≤ Q − 1 k = q P + p 0 ≤ p ≤ P − 1 , 0 ≤ q ≤ Q − 1 {\displaystyle {\begin{aligned}n&=sQ+r\qquad 0\leq s\leq P-1,\,0\leq r\leq Q-1\\k&=qP+p\qquad 0\leq p\leq P-1,\;0\leq q\leq Q-1\end{aligned}}}
すると