フーリエ変換と高速フーリエ変換

フーリエ変換を高速で行えるＦＦＴ（高速フーリエ変換）というのがありますが、
具体的にどういうものなのでしょうか？何故に速くなるのですか？ちなみにフーリエ変換は理解しています。

No.4 ベストアンサー 回答者： siegmund 回答日時： 2001/04/25 00:07

siegmund です．

質問をよく見ましたら，
「何故に速くなるのですか？」もありましたね．
ちょっと早合点しちゃいました．

m=0 から m=N-1 までのＮ個のｍの値に対して f(m) が与えられたとして
(前の回答ではｘと書きましたが，離散的なのでｍにしました)
離散フーリエ変換は
(1)　　F(k) = Σ(m=0～N-1) f(m) W^(km)
です．ただし，W = exp(2πi/N) です．
(1)のままやると，N^2 回の乗算が必要です．

ところが，N = N1×N2 と因数分解できるとき
(3)　　φ(k1,m2) = W^(k1m2) Σ(m1=0～N1-1) f(N2m1+m2) W^(N2k1m1)
(4)　　F(k1+N1k2) = Σ(m2=0～N2-1) φ(k1,m2) W^(N1k2m2)
と分解できます．
ただし，
(5)　　k1=0,1,・・・,N1-1
(6)　　m2=0,1,・・・,N2-1
(7)　　k2=0,1,・・・,N2-1
です．
(3)の乗算は N1×N2 回
(4)はこの各々に対して N2 回ですから，全体で N1(N2)^2 回の乗算で，
もとの N^2 = N1^2×N2^2 回の乗算に対して 1/N1 になりました．

ametsuchi さんご紹介のＨＰの「1.2.1 基本的な考え方」では，
この分解が N=2×(N/2) になっている場合が例示されています．

細かいテクニックは色々あるようですが，
私はそちらの専門家ではないので詳細をつっこまれるとボロが出ます．
演算量が減る原理ということで，お答えしました．
式が書きにくいんで，ミスプリが心配です．

この回答へのお礼

非常に詳しい説明を有難うございます。よくわかりました。

お礼日時：2001/04/26 23:24

No.3 回答者： ametsuchi 回答日時： 2001/04/24 09:25

siegmund先生のいわれるとおりで、わたし如きシロートの出る幕はないのですが、やさしい解説が以下のURLに付いていますので参照してください。

手元の資料によれば、N log N ではなく、N/2 log N となっていますが、「オーダー」とおっしゃられているので、間違いではないでしょう。

FFTが、現場でどれだけ約に立っているか、身近に接する機会も多いでしょう。コンピュータの処理能力の向上とともに、音声・画像など、これから益々重要になってきますが、FFT抜きではとても考えられないことです。

参考URL：http://momonga.t.u-tokyo.ac.jp/~ooura/fftman/

No.2 回答者： siegmund 回答日時： 2001/04/24 00:32

高速フーリエ変換は数値計算の話で，

離散的なｘについて関数値が知られているとき，
これを離散的フーリエ変換しようとするものです．

Ｎ個のｘの値について関数値が知られているとき，
離散的フーリエ変換の式そのもので計算しますと N^2 回のオーダーの乗算が必要ですが，
アルゴリズムの工夫により N log N のオーダーの乗算回数で結果が得られます．
1965年にクーリーとチューキーが開発した手法です．

No.1 回答者： nanashisan 回答日時： 2001/04/23 23:48

計算回数を減らせるようアルゴリズムが工夫してあるからです。