- ベストアンサー
フーリエ変換と高速フーリエ変換
- みんなの回答 (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) になっている場合が例示されています. 細かいテクニックは色々あるようですが, 私はそちらの専門家ではないので詳細をつっこまれるとボロが出ます. 演算量が減る原理ということで,お答えしました. 式が書きにくいんで,ミスプリが心配です.
その他の回答 (3)
- ametsuchi
- ベストアンサー率31% (81/257)
siegmund先生のいわれるとおりで、わたし如きシロートの出る幕はないのですが、やさしい解説が以下のURLに付いていますので参照してください。 手元の資料によれば、N log N ではなく、N/2 log N となっていますが、「オーダー」とおっしゃられているので、間違いではないでしょう。 FFTが、現場でどれだけ約に立っているか、身近に接する機会も多いでしょう。コンピュータの処理能力の向上とともに、音声・画像など、これから益々重要になってきますが、FFT抜きではとても考えられないことです。
- siegmund
- ベストアンサー率64% (701/1090)
高速フーリエ変換は数値計算の話で, 離散的なxについて関数値が知られているとき, これを離散的フーリエ変換しようとするものです. N個のxの値について関数値が知られているとき, 離散的フーリエ変換の式そのもので計算しますと N^2 回のオーダーの乗算が必要ですが, アルゴリズムの工夫により N log N のオーダーの乗算回数で結果が得られます. 1965年にクーリーとチューキーが開発した手法です.
- nanashisan
- ベストアンサー率9% (16/172)
計算回数を減らせるようアルゴリズムが工夫してあるからです。
関連するQ&A
- 多次元高速フーリエ変換について
高速フーリエ変換fftによって、計算量のオーダーが n^2 からnlogn まで落とせるんですよね? それで、3次元のフーリエ変換って、 1次元のフーリエ変換を3回やれば n^2*nlogn=n^3lognのオーダーでできると思うのですが、 これ以上速いオーダーではできませんか?
- ベストアンサー
- 数学・算数
- エクセルでのフーリエ変換のやり方
例えばですが、時間とその流速が分かっていたとして、その流速のフーリエ変換をしたい場合、エクセルではどうすれば良いのでしょうか? FFT(高速フーリエ変換)以外のやり方が教えて欲しいです。
- 締切済み
- 物理学
- 高速フーリエ変換のこと。
高速フーリエ変換に公式みたいなものはありますか? いろいろな本を見たのですが、「例えば8点では・・・」というように 具体的なやり方は書いてあるのですが、公式がいまいち分かりません。 もし公式があるのならば教えてください。お願いします。
- 締切済み
- 数学・算数
- 高速フーリエ変換での質問
高速フーリエ変換を勉強している者ですが、数式がさっぱり分からない状態です。 高速フーリエ変換を理解するには高校数学くらいだと何を学べばいいんでしょうか? それだと足りないと思うので、それ以外に何を理解する必要があるのでしょうか? 学んだばかりで正直全くわからない状態でのスタートなのですがよろしくお願いします。
- ベストアンサー
- 数学・算数
- 高速フーリエ変換とフーリエ変換の違い
高速フーリエ変換とフーリエ変換の違いについて教えて下さい。 高速フーリエ変換は何か近似を行うことによって、計算速度を速くしているのでしょうか? もし、何かの極限で出てくる結果が違う場合などがあれば教えて下さい。
- ベストアンサー
- 物理学
- 2次元離散フーリエ変換について
2次元離散フーリエ変換の2次元FFTを用いて、縦256×横256 縦1024×横1024の場合の画像を大きさを求めてもらいたいです。 2次元フーリエ変換について調べたのですが理解することが出来ませんでした。 お手数ですが回答お願いします
- 締切済み
- 情報工学
- C言語プログラムの離散フーリエ変換
C言語プログラムの離散フーリエ変換について教えてください。「C言語による画像再構成の基礎」という本のプログラムをもとに二次元画像をDFT(通常の離散フーリエ変換)→InveresFFT(逆高速フーリエ変換)すると画像が左右反転、上下反転してしまいます。DFT→InverseDFTやFFT→InverseFFTだとそのようにはなりません。通常のDFTとFFTのアルゴリズムの違いからしかたがないのでしょうか?それともプログラムの変更で修正できるのでしょうか?どうしてもDFT→InverseFFTでがぞうをもとに戻したいのです。 サンプルページ http://www.iryokagaku.co.jp/frame/03-honwosagasu/370/370-dl.html P4-14fourier2d1d.c (離散フーリエ変換DFT) P4-15fft.c(高速フーリエ変換)プログラムです
- 締切済み
- C・C++・C#
- フーリエ変換? FIT curveって??
生物リズム学論文を読んでいたら、FFT-NLLS(The fast Fourier transform-nonlinear least squares method )という解析方法がでてきました。 ネットで調べて 「FFT=高速フーリエ変換」、 「フーリエ変換を行うことにより、解析したい音・振動の波形が、どのような周波数と振幅を持つ波形の合成で成り立っているかを知ること(スペクトル分析)ができる」 ということはわかったのですが、 ・「NLLs」とはどんな意味なのか? ・このFFTによって得られる「FIT curve」がどんな物なのか、日本語ではなんというのか がわかりません。FIT curveは近似値曲線のような物でしょうか?? どなたか詳しい方教えてください、よろしくお願いします!!
- ベストアンサー
- 数学・算数
お礼
非常に詳しい説明を有難うございます。よくわかりました。