Ptt: ページの作成:「高速フーリエ変換は離散フーリエ変換を高速に計算するアルゴリズムである。計算結果は離散フーリエ変換と同じになる。だいたいFFTと呼ばれる。 == Cooley-Tukeyのアルゴリズム == $N$ が2の累乗の場合で考える。 === DFTの定義を整理する === まず離散フーリエ変換の定義を思い出しておく。 $X[k] = \sum ^{N-1}_{n=0} x[n] e^{-i\frac{2\pi k…」$

2024-11-09T17:38:49Z

ページの作成:「高速フーリエ変換は離散フーリエ変換を高速に計算するアルゴリズムである。計算結果は離散フーリエ変換と同じになる。だいたいFFTと呼ばれる。 == Cooley-Tukeyのアルゴリズム == <math>N</math> が2の累乗の場合で考える。 === DFTの定義を整理する === まず離散フーリエ変換の定義を思い出しておく。 <math> X[k] = \sum ^{N-1}_{n=0} x[n] e^{-i\frac{2\pi k…」

新規ページ

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

== Cooley-Tukeyのアルゴリズム ==
<math>N</math> が2の累乗の場合で考える。

=== DFTの定義を整理する ===
まず[[離散フーリエ変換]]の定義を思い出しておく。

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

<math>
W_N = e^{-i\frac{2\pi}{N}}
</math>

とすれば、

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

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

<math>
\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>
W_N
</math>
の累乗が<math>N</math>周期であるのに対し、
<math>
W_{N/2}
</math>
の累乗は<math>\frac{N}{2}</math>周期である。

そこで <math>n</math> を半分ずつに分ける。

<math>
\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>X[k]</math>をもとの半分の長さのDFTで表すことができる。

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

高速フーリエ変換 - 版の履歴