n 倍 FFT 卷积和圆形重叠

Question

问题描述

我采用了卷积定理来有效地计算卷积。假设有两个长度为 N 的实数信号 s1 和 s2。然后我可以获得卷积

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_max，但如果不是绝对必要，我宁愿不必使用大量内存，并且我不希望每次 k 更改时都再次评估 FT。

问题

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

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

Answer 1

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

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