高速フーリエ変換

高速フーリエ変換は 離散フーリエ変換 を高速に計算するアルゴリズムである。 計算結果は 離散フーリエ変換 と同じになる。 だいたいFFTと呼ばれる。

Cooley-Tukeyのアルゴリズム

[math]\displaystyle{ N }[/math] が2の累乗の場合で考える。

DFTの定義を整理する

まず離散フーリエ変換の定義を思い出しておく。

[math]\displaystyle{ X[k] = \sum ^{N-1}_{n=0} x[n] e^{-i\frac{2\pi kn}{N}} }[/math]

[math]\displaystyle{ W_N = e^{-i\frac{2\pi}{N}} }[/math]

とすれば、

[math]\displaystyle{ X[k] = \sum ^{N-1}_{n=0} x[n] W_N^{kn} }[/math]

k の偶奇で分ける

[math]\displaystyle{ k }[/math] の偶奇で分けて [math]\displaystyle{ k = 2d + b ~(0 \le d \lt \frac{N}{2}, 0 \le b \lt 2) }[/math] とすると

[math]\displaystyle{ \begin{eqnarray} X[2d+b] &=& \sum ^{N-1}_{n=0} x[n] W_N^{(2d+b)n} \\ &=& \sum ^{N-1}_{n=0} x[n] W_N^{2dn}W_N^{bn} \\ &=& \sum ^{N-1}_{n=0} x[n] W_{N/2}^{dn}W_{N}^{bn} \end{eqnarray} }[/math]

nを半分ずつに分ける

こうすると、 [math]\displaystyle{ W_N }[/math] の累乗が[math]\displaystyle{ N }[/math]周期であるのに対し、 [math]\displaystyle{ W_{N/2} }[/math] の累乗は[math]\displaystyle{ \frac{N}{2} }[/math]周期である。

そこで [math]\displaystyle{ n }[/math] を半分ずつに分ける。

[math]\displaystyle{ \begin{eqnarray} X[2d+b] &=& \sum ^{N-1}_{n=0} x[n] W_{N/2}^{dn}W_{N}^{bn} \\ &=& \sum ^{N/2-1}_{n=0} x[n] W_{N/2}^{dn}W_{N}^{bn} + \sum ^{N-1}_{n=N/2} x[n] W_{N/2}^{dn}W_{N}^{bn} \\ &=& \sum ^{N/2-1}_{n=0} x[n] W_{N/2}^{dn}W_{N}^{bn} + \sum ^{N/2-1}_{n=0} x[n+N/2] W_{N/2}^{d(n+N/2)}W_{N}^{b(n+N/2)} \\ &=& \sum ^{N/2-1}_{n=0} x[n] W_{N/2}^{dn}W_{N}^{bn} + \sum ^{N/2-1}_{n=0} x[n+N/2] W_{N/2}^{dn}W_{N}^{b(n+N/2)} \\ &=& \sum ^{N/2-1}_{n=0} (x[n]W_N^{bn} + x[n+N/2]W_N^{b(n+N/2)}) W_{N/2}^{dn} \end{eqnarray} }[/math]

FFT

こうして、[math]\displaystyle{ X[k] }[/math]をもとの半分の長さのDFTで表すことができる。

同じことを繰り返して計算量を O(NlogN) に削減できる。