最新閲覧日:

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

A 回答 (4件)

siegmund です.



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

m=0 から m=N-1 までのN個のmの値に対して f(m) が与えられたとして
(前の回答ではxと書きましたが,離散的なので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 さんご紹介のHPの「1.2.1 基本的な考え方」では,
この分解が N=2×(N/2) になっている場合が例示されています.

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

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

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

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



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

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

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

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


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

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

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

    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード


このカテゴリの人気Q&Aランキング

おすすめ情報

カテゴリ