python - n-fold 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。

问题

是否可以执行以下操作之一

• 根据需要对信号进行 FFTk=1和“傅立叶空间中的零填充”？
• 防止 FFT 中的循环环绕？

Answer 1

1. 频域中的零填充是可能的，但需要比在时域中执行更多的计算工作（触发器）。IFFT、zeropad 和 re-FFT 为每个额外的快速卷积创建“空间”可能会更快。

2. 完整卷积的较长结果必须在某个地方，所以不，使用 FFT 时不可能防止循环卷积。即使补零也不会阻止循环重叠的计算，它只是确保结果中的重叠等于加零。