畳み込み積分の計算
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/09/24 14:21 UTC 版)
「レーダーのFFTアルゴリズム」の記事における「畳み込み積分の計算」の解説
畳み込み定理 により、FFTを用いて計算することができる。また、N-1は合成数のため、より高速なクーリーターキー型のFFTアルゴリズムが適用できる。しかしながら、N-1が大きな素数の素因数をもつ場合、レーダーのアルゴリズムを再帰的に使う必要がある。その代わりに、長さN-1のDFTをゼロ埋めによって2の冪乗にすることで、高速なクーリーターキーのアルゴリズムを用いることができる。ゼロ埋め後のデータサイズが最低2(N-1)-1以上あれば元のデータを完全に復元することができ、ゼロ埋めによる結果の変化は生じない。 畳み込み積分の計算にゼロ埋めを用いたFFTを用いることでのこのアルゴリズムは加算についてO(N)の計算時間とそれに加えと畳み込み積分についてとO(N log N)の計算時間で実行できる。しかしながら、このアルゴリズムは付近の合成数のサイズのFFTに比べ、およそ3から10倍の時間がかかる。 畳み込み積分の計算をゼロ埋めなしのFFTで行う場合、計算時間はNの性質に強く依存する。最悪の場合、N-1 が素数 N2 により N-1= N2 と表され、また N2–1が素数 N3 により N2–1 = N3 と表され、以下同様に続いていく場合である。このような場合、レーダーのアルゴリズムの再帰が連続することになり、O(N²)の計算時間がかかる可能性がある。このような性質をもつNは ソフィー・ジェルマン素数と呼ばれ、上記の数列は一次の Cunningham(ビル-カニンガム)チェーンと呼ばれる。しかしながら、これまでの研究ではカニンガムチェーンの成長はlog2(N)よりも遅いことが分かっているため、レーダーのアルゴリズムの再帰によりかかる計算時間はO(N²)よりかは速いと思われる。幸いにも、畳み込み計算にゼロ埋めを用いたFFTを使えば計算時間はO(N log N)のオーダーになることが保証されている。
※この「畳み込み積分の計算」の解説は、「レーダーのFFTアルゴリズム」の解説の一部です。
「畳み込み積分の計算」を含む「レーダーのFFTアルゴリズム」の記事については、「レーダーのFFTアルゴリズム」の概要を参照ください。
- 畳み込み積分の計算のページへのリンク
