低通FIR滤波器与FFT卷积 - Overlap add，为什么和如何使用？

Question

首先，很抱歉我没有在这里发布代码。由于某些原因，当我试图将代码放到此页面时，所有的代码都乱了，而且可能太多了，无法接受。这是我的代码： http://pastebin.com/bmMRehbd

现在，从我得到的信息来看，我无法从这段代码中获得良好的结果，是因为我没有使用重叠相加。我尝试在互联网上阅读了几个来源，以了解为什么需要使用重叠相加，但我无法理解它。似乎实际过滤器起作用，因为任何高于给定截止值的内容确实被截断了。

我应该提到这是为vst2-sdk编写的代码。

有人能告诉我为什么需要添加它以及如何将重叠相加代码实现到给定的代码中吗？

我还应该提到，当涉及算法和数学时，我相当愚蠢。我是那种需要通过视觉来掌握自己正在做什么的人。要么通过代码解释：）然后我指的是实际重叠。

重叠相加理论：http://en.wikipedia.org/wiki/Overlap%E2%80%93add_method

感谢您能提供的所有帮助！

- Hiam

---

你所说的"overlap add"是指融合乘加运算吗？ - Jerry Coffin

我想我的意思是http://en.wikipedia.org/wiki/Overlap%E2%80%93add_method :) - Hiam

Answer 1

重叠相加方法（Overlap-Add method）用于处理每个FFT缓冲区的边界。问题在于，FFT域中的乘法导致时间域中的循环卷积。这意味着，在执行IFFT后，帧末端的结果会回到开头并破坏帧开头的输出样本。

可以更容易地理解：假设您有一个长度为N的滤波器。该滤波器与M个输入样本的线性卷积实际上返回M+N-1个输出样本。然而，在FFT域中进行的循环卷积导致输入和输出样本数量相同，即M个样本。线性卷积中额外的N-1个样本已经"包裹"到一起并破坏了前N-1个输出样本。

以下是一个示例（使用Matlab或Octave）：

a = [1,2,3,4,5,6];
b = [1,2,1];
conv(a,b)  %linear convolution

    1    4    8   12   16   20   17    6

ifft(fft(a,6).*fft(b,6))  %circular convolution

    18   10    8   12   16   20

请注意，在循环情况下，最后2个样本已绕回并添加到了前2个样本中。 重叠相加/重叠保存方法基本上是处理这种环绕的方法。由于循环卷积返回的未损坏的输出样本数量少于输入样本数量，因此需要FFT缓冲区的重叠。

- Jason B

---

这很好地解释了为什么我需要它，我只需要再考虑一下，看看如何将这些知识应用到代码中。 - Hiam

Answer 2

当您使用有限冲激响应滤波器执行卷积时，通过取两个输入信号的离散傅里叶变换的乘积的反离散傅里叶变换，您实际上正在实现循环卷积。我将在此称之为“在频域计算的卷积”。（如果您不知道什么是循环卷积，请 看看这个链接。基本上它是一个卷积，您假定该域是循环的，即将信号移出边界会使其“包裹”到域的另一侧。）

通常情况下，您希望使用快速傅里叶变换对大型信号执行卷积，因为它在计算上更高效。

重叠添加（以及其近亲重叠保存）是解决在频域中执行的卷积实际上是循环卷积的方法，但实际上我们很少想要执行循环卷积，而通常更希望进行线性卷积的方法。

重叠添加通过“零填充”输入信号的块，然后适当地使用在频域中执行的循环卷积的部分。重叠保存通过仅保留对应于线性卷积的信号部分并丢弃由循环移位“污染”的部分来实现此目的。

这里有两个来自维基百科的链接，分别是：

Overlap-add：这个链接有一个很好的图示，解释了正在发生的事情。

Overlap-save

Orfanidis的这本书讲得很好。请参见第9.9.2节。它不是信号处理的“事实标准”，但我认为它写得非常好，比其他书更好作为入门读物。

- Chris A.

---

是的，问题在于我无法理解维基百科文章中所讲述的算法，我无法将其融入我的代码中。我至少尝试了那么多 :) - Hiam

抱歉，如果有人付费或成绩取决于此，我才会编写此代码。这并不简单，需要考虑情况和数组大小等因素。不过那本书应该能帮助理解。 - Chris A.

有一件事让我感到困惑。如果我处理1024个数据样本，然后将其fft成一个数组。那么这个数组和滤波器数组的大小不应该都是1024吗？还是滤波器数组应该是两倍大小（2048）？ - Hiam

让我们在聊天中继续这个讨论：http://chat.stackoverflow.com/rooms/9692/discussion-between-chris-a-and-hiam - Chris A.

在这种情况下，我感到困惑的原因是实部和虚部是一个结构体。因此，当我分配数组大小时，我会分配1024个特定对象，对于普通数据，我会分配大小为1024的双精度数组，并且fft数组分配FFT_SCTRUCT，大小为1024。如所述，该结构体仍应保持实部和虚部。或者我想错了吗？这部分是我不理解重叠的原因之一 :)顺便感谢您的帮助！非常感激 - Hiam

Answer 3

首先要了解的是，时域卷积等价于频域乘法。在卷积中，你大约处于O(n*m)的位置，其中n是FIR长度，m是要过滤的样本数量。在频域中，使用FFT，你运行的是O(n * log n)。对于足够大的n，使用频域进行滤波的成本大大降低。然而，如果n相对较小，则收益减少到一个简单地在时域中进行过滤的点。这个断点是主观的，但是在50到100之间的数字可以作为你可能切换的点。

- sizzzzlerz

---

我可能太蠢了，但算法对我来说不是很友好。如果你能将你所说的转化为代码，那么我可能就能理解了 :) - Hiam

这是通过频域卷积的解释，而非为什么需要重叠相加的解释。 - Oliver Charlesworth

Answer 4

是的，卷积滤波器会“起作用”，在改变频率响应方面。但是，在频域中的乘法也会污染一端的时域数据与另一端的数据，反之亦然。重叠相加/保存扩展了FFT的大小并截掉了“污染”的末端，然后使用该末端数据来修复随后FFT窗口的开头。

- hotpaw2