c - 使用 FFT 代替卷积实现的低通滤波器

Question

实现一个低通 FIR 滤波器，什么时候应该使用 FFT 和 IFFT 而不是时域卷积？

目标是实现实时计算所需的最低 CPU 时间。据我所知，FFT 的复杂度约为 O(n log n)，但时域中的卷积具有 O(n²) 的复杂度。要在频域中实现低通滤波器，应该使用 FFT，然后将每个值乘以滤波系数(转换到频域)，然后进行 IFFT。

那么，问题是什么时候可以使用基于频率的 (FFT+IFFT) 滤波而不是使用基于直接卷积的 FIR 滤波器？比如说，如果有32个定点系数，用还是不用FFT+IFFT？ 128个系数怎么样？等等……

尝试优化现有源代码(基于卷积的 FIR 滤波器)，我完全困惑，我应该使用 FFT 还是只优化它以使用 SSE 或不使用。

Answer 1

卷积实际上是 O(m*n)，其中 m 是有限脉冲响应的宽度，N 是样本窗口。

因此，更改为 FFT+IFFT 有用的 m 的临界点与样本窗口的 log(N) 有关。

在实时操作中，FFT 面向批处理的事实可能比时钟周期的相对数量更重要，因为在过滤之前等待 1024 个样本点可能是 Not Acceptable ，例如，如果应用程序处于调节循环中。

现在这个领域已经进行了大量开发，并且有大量代码可用，因此尝试几个解决方案和基准测试是这里的关键。