3

少し勉強した後、いくつかの入力から DFT (離散フーリエ変換) を計算する小さなアプリを作成しました。十分に機能しますが、かなり遅いです。

FFT (高速フーリエ変換) を使用すると計算が高速になると読みましたが、どのように違うのでしょうか? さらに重要なことに、C++ でそれらを実装するにはどうすればよいでしょうか?

4

5 に答える 5

4

アルゴリズムを手動で実装する必要がない場合は、西部で最速のフーリエ変換を見ることができます

C で開発されているにもかかわらず、正式には C++ で動作します ( FAQから) 。

質問2.9。C++ から FFTW を呼び出すことはできますか?

確実に。FFTW は、任意の C++ コンパイラでコンパイルおよび/またはリンクする必要があります。さらに、C++ テンプレート クラスは、FFTW の複素数形式とビット互換である可能性があります (詳細については、FFTW のマニュアルを参照してください)。

于 2010-04-03T22:31:51.423 に答える
3

FFT は、n^2 の DFT に比べて n*log(n) 複雑です。

これについては多くの文献があり、最初に確認することを強くお勧めします. http://en.wikipedia.org/wiki/Fast_Fourier_transform (外部リンクを確認してください)

ライブラリが必要な場合は、たとえば既存のライブラリを使用することをお勧めします。 http://www.fftw.org/ このライブラリは FFT を効率的に実装しており、独自のソフトウェア (MATLAB など) でも使用されています。

于 2010-04-03T22:39:05.260 に答える
1

Steven Smith の著書The Scientist and Engineer's Guide to Digital Signal Processing、特にDFT に関する第 8章とFFT に関する第 12 章は、私が今までできた 2 つの変換をよりよく説明しています。

ところで、本全体は無料で入手でき (上記のリンク)、信号処理の非常に優れた入門書です。

C++ コードのリクエストに関しては、西洋で最も高速なフーリエ変換 (すでに superexsl で引用されています) または TI やアナログ デバイスなどの DSP ライブラリのみを使用しました。

于 2010-04-04T02:39:43.263 に答える
1

正しく実装された DFT の結果は、正しく実装された FFT の結果と本質的に同じです (丸め誤差のみが異なります)。他の人がここで指摘しているように、主な違いはパフォーマンスです。DFT には O(n^2) 操作があり、FFT には O(nlogn) 操作があります。

私が今までに見つけた最高の、最も読みやすい出版物 (私がまだ参照しているもの) は、E Oran Brigham によるThe Fast Fourier Transform and its Applicationsです。最初の数章では、フーリエ変換の連続形式と離散形式の概要を詳しく説明しています。次に、彼はそれを使用して、基数 2 (n は 2 の累乗) および混合基数の場合 (ただし、後者は前者よりもやや浅い論文です)のCooley-Tukey アルゴリズムに基づく DFT の高速バージョンを開発します。.

入力 X に対して線形時間演算を実行し、結果を再帰的に半分に分割し、2 つの半分に対して同様の線形時間演算を実行する基数 2 アルゴリズムの基本的なアプローチ。混合基数の場合も同様ですが、X を毎回等しい部分に分割する必要があるため、n に大きな素因数がない場合に役立ちます。

于 2010-04-04T03:58:01.850 に答える
0

いくつかのアルゴリズムが説明されているこの素晴らしい説明を見つけました。

FastFourierTransform

実施については、

  • 最初に、実装が正しい結果を返すことを確認します（フーリエ変換が組み込まれているmatlabまたはオクターブからの出力を比較してください）
  • 必要に応じて最適化し、プロファイラーを使用する
  • 不要な for ループを使用しない
于 2010-04-03T22:35:46.853 に答える