使用FFT而不是卷积实现的低通滤波器

Question

6

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

目标是实现实时计算所需的最低CPU时间。据我所知，FFT的复杂度约为O（n log n），而时域卷积的复杂度为O（n²）。要在频域中实现低通滤波器，应该使用FFT，然后将每个值与滤波系数相乘（这些系数被转换为频域），然后进行IFFT。

那么，问题是什么时候使用基于频率的（FFT + IFFT）过滤器而不是使用直接卷积的FIR过滤器？例如，如果有32个定点系数，应该使用FFT + IFFT吗？128个系数呢？等等...

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

- psihodelia

2个回答

6

这取决于你使用的架构和其他因素，但对于1D DSP而言，通常的"经验法则"是如果滤波器大小很小，比如小于100个项，那么直接卷积可能更好，但对于更大的滤波器大小，频域中快速卷积可能更值得一试。

当然，首先需要确定过滤是否是性能瓶颈，因为如果你的时域实现已经足够快，那么进行快速卷积就没有必要再做额外的努力了。

总之：首先从简单的直接卷积开始，如果有必要的话再切换到快速卷积。（你需要保留第一个实现以验证第二个实现，所以这并不是徒劳的努力。）

- Paul R

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter Tillemans · Accepted Answer

卷积实际上是O（m*n），其中m是有限冲激响应的宽度，N是采样窗口的大小。

因此，当有限冲激响应的宽度m达到与采样窗口大小log(N)相关的临界点时，改用FFT + IFFT是有用的。

在实时操作中，FFT是批量处理的事实可能比相对的时钟周期更重要，因为如果应用程序处于规则循环中，等待1024个采样点进行滤波可能是不可接受的。

现在，在这个领域已经做了大量的开发，并且提供了大量的代码，所以尝试一些解决方案并进行基准测试非常关键。