n折FFT卷積和圓形重疊

Question

問題描述

我已經使用了卷積定理來有效地計算卷積。假設有兩個實際信號s1和s2各自長度爲N。然後，我可以從

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邊界處理的fft_size必須進行修改，以避免重疊圓形讀取

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

。

不幸的是，我不知道k先驗。一種選擇是選擇最大值k_max，但如果不是絕對必要的話，我寧願不必使用大量內存，我寧願每次k更改時都不要再評估FT。

問題

是否可以做以下

• 一個以信號k=1和「零墊在傅立葉空間」作爲必要的FFT？
• 防止FFT中的圓形包裹？

Answer 1

1. 零填充在頻域上是可行的，但需要比在時域上做更加的計算量（拖鞋）。 IFFT，zeropad和re-FFT可能會更快地爲每個額外的快速卷積創建「空間」。

2. 完整卷積的較長結果必須放在某個位置，所以不能，在使用FFT時不可能防止循環卷積。即使是零填充也不能阻止計算圓形重疊，它只是確保結果中的重疊等於零的加法。