4

私の質問は、Numpy の FFT 関数で使用されるアルゴリズムについてです。

Numpy のドキュメントには、Cooley-Tukey アルゴリズムを使用していると書かれています。ただし、ご存じのとおり、このアルゴリズムは点の数 N が 2 の累乗の場合にのみ機能します。

numpy は、FFT X[k] を計算するために入力ベクトル x[n] をパディングしますか? （出力にあるポイントの数もNなので、そうは思いません）。numpy が FFT 関数に使用するコードを実際に「見る」にはどうすればよいですか?

乾杯！

4

2 に答える 2

12

ドキュメントによると、numpy の FFT はFFTPACKに基づいています。

FFTPACK のドキュメントには、次の記述があります。

サブルーチン rffti(n,wsave)

サブルーチン rffti は、rfftf と rfftb の両方で使用される配列 wsave を初期化します。n の素因数分解と三角関数の表が計算され、wsave に保存されます。

標準の Cooley-Tukey アルゴリズムは「時間デシメーションを使用した基数 2」であり、サイズの FFT の計算を2*nサイズ n の 2 つの FFT とサイズ 2 の n FFT に再帰的に削減します。同じものの一般的な因数分解バージョンがあります。サイズm*nの FFT をサイズ m の n FFT とサイズ n の m FFT に変換するアルゴリズム。FFTPACK の準備ルーチンが入力サイズの素因数分解を計算するという事実は、これが彼らがしていることを示しているようです。したがって、素数の要素を使用しない限り、または要素数の素因数が非常に大きい場合を除き、かなり高速化されるはずです。

数年前、私は Cooley-Tukey のアルゴリズムの基数 2バージョンと一般因数分解バージョンの両方についてブログを書きました。それらを読むと、NumPy の内部で何が起こっているように見えるかを理解するのに役立つかもしれません。そこから取得した次の図は、CT FFT を示しています。

ここに画像の説明を入力

于 2012-12-12T14:57:42.207 に答える
2

私の経験では、アルゴリズムは自動パディングを行わないか、少なくともいくつかは行いません。たとえば、長さ == 2 のべき乗でない信号に対して scipy.signal.hilbert メソッドを実行すると、約 45 秒かかりました。このような長さになるまで自分で信号をゼロでパディングすると、100ms かかりました。

YMMV ですが、基本的に信号処理アルゴリズムを実行するたびに再確認する必要があります。

于 2013-10-12T02:52:34.407 に答える