n倍FFT畳み込みと循環重複

Question

問題の説明

私は畳み込み定理を使用して畳み込みを効率的に計算しました。実数信号s1とs2の2つがそれぞれ長さNであると仮定します。その後、私はk singalsを持っている場合は、fft_sizeは円形の重複を避けるために

fft_size = int(2 ** np.ceil(np.log2(k * size - 1))) 

を読み取るように変更しなければならない

import numpy as np 
import numpy.fft as fft 

size = len(s1) 
fft_size = int(2 ** np.ceil(np.log2(2 * size - 1))) #The size for the FFT algorithm 

S1 = fft.rfft(s1, fft_size) #Take FTs 
S2 = fft.rfft(s2, fft_size) 

convolution = fft.irfft(S1 * S2) #Take IFT 

から畳み込みを得ることができます。

残念ながら、私は先験的にkを知らない。 1つの選択肢は最大値k_maxを選択することですが、絶対に必要でない場合は大量のメモリを使用する必要はなく、kを変更するたびにFTを評価したくない場合があります。

質問

は、それは次のよう

• のいずれかを実行することが可能です必要に応じてk=1ための信号と「フーリエ空間でゼロパッド」のFFTを取りますか？
• FFTで循環ラッピングを防止しますか？周波数領域での

Answer 1

1. ゼロパディングは可能ですが、時間領域でそれを行うよりもはるかに多くの計算量（フロップ）が必要です。追加の高速畳み込みごとに「部屋」を作成するためには、IFFT、ゼロパッド、および再FFTより高速かもしれません。

2. 完全な畳み込みの結果が長くなると、FFTを使用するときに循環畳み込みを防ぐことができません。ゼロパディングであっても、循環オーバーラップの計算が妨げられることはありません。結果のオーバーラップがゼロの加算と等価であることを確認します。