-PR-
解決済み

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

  • すぐに回答を!
  • 質問No.67469
  • 閲覧数768
  • ありがとう数6
  • 気になる数0
  • 回答数4
  • コメント数0

お礼率 20% (5/25)

フーリエ変換を高速で行えるFFT(高速フーリエ変換)というのがありますが、
具体的にどういうものなのでしょうか?何故に速くなるのですか?ちなみにフーリエ変換は理解しています。
通報する
  • 回答数4
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

質問者が選んだベストアンサー

  • 回答No.4
レベル13

ベストアンサー率 64% (700/1089)

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) になっている場合が例示されています.

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

お礼率 20% (5/25)

非常に詳しい説明を有難うございます。よくわかりました。
投稿日時 - 2001-04-26 23:24:04
関連するQ&A
-PR-
-PR-

その他の回答 (全3件)

  • 回答No.1
レベル10

ベストアンサー率 9% (16/172)

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


  • 回答No.2
レベル13

ベストアンサー率 64% (700/1089)

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

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

ベストアンサー率 31% (81/257)

siegmund先生のいわれるとおりで、わたし如きシロートの出る幕はないのですが、やさしい解説が以下のURLに付いていますので参照してください。 手元の資料によれば、N log N ではなく、N/2 log N となっていますが、「オーダー」とおっしゃられているので、間違いではないでしょう。 FFTが、現場でどれだけ約に立っているか、身近に接する機会も多いでしょう。コンピュータの処理能力の向上 ...続きを読む
siegmund先生のいわれるとおりで、わたし如きシロートの出る幕はないのですが、やさしい解説が以下のURLに付いていますので参照してください。

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

FFTが、現場でどれだけ約に立っているか、身近に接する機会も多いでしょう。コンピュータの処理能力の向上とともに、音声・画像など、これから益々重要になってきますが、FFT抜きではとても考えられないことです。
このQ&Aで解決しましたか?
関連するQ&A
-PR-
-PR-
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


新大学生・新社会人のパソコンの悩みを解決!

いま みんなが気になるQ&A

関連するQ&A

-PR-

ピックアップ

-PR-
ページ先頭へ