使用FFT代替卷积实现的低通滤波器
实现低通 FIR 滤波器时，什么时候应该使用 FFT 和 IFFT 而不是时域卷积？
目标是实现实时计算所需的最低CPU时间。据我所知，FFT 的复杂度约为 O(n log n)，但时域中的卷积复杂度为 O(n²)。要在频域实现低通滤波器，应使用 FFT，然后将每个值乘以滤波系数（转换为频域），然后进行 IFFT。
那么，问题是何时使用基于频率 (FFT+IFFT) 的滤波而不是使用基于直接卷积的 FIR 滤波器是合理的？比如说，如果有32个定点系数，是否应该使用FFT+IFFT？ 128个系数怎么样？等等...
尝试优化现有的源代码（基于卷积的 FIR 滤波器），我完全困惑，要么我应该使用 FFT，要么只是优化它以使用 SSE 或不使用。
Implementing a low pass FIR filter, when should one use FFT and IFFT instead of time-domain convolution?
The goal is to achieve the lowest CPU time required for real-time calculations. As I know, FFT has about O(n log n) complexity, but convolution in the time domain is of O(n²) complexity. To implement a low pass filter in the frequency domain, one should use FFT, then multiply each value with filtering coefficients (which are translated into frequency domain), then make IFFT.
So, the question is when it is justified to use frequency-based (FFT+IFFT) filtering instead of using direct convolution based FIR filter? Say, if one have 32 fixed-point coefficients, should FFT+IFFT be used or not? How about 128 coefficients? And so on...
Trying to optimize an existed source code (convolution-based FIR filter), I am totally confused, either I should to use FFT or just optimize it to use SSE or not.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
卷积实际上是 O(m*n)，其中 m 是有限脉冲响应的宽度，N 是采样窗口。
因此，m 的临界点（其中有用的变为 FFT+IFFT）与样本窗口的 log(N) 有关。
在实时操作中，FFT 面向批量的事实可能比时钟周期的相对数量更重要，因为例如，如果应用程序处于调节环路中，则在滤波之前等待 1024 个采样点可能是不可接受的。
现在这个领域已经完成了大量的开发，并且有大量的代码可用，因此尝试一些解决方案和基准测试是这里的关键。
Convolution is actually O(m*n) where m is the width of the finite impulse response, and N the sample window.
So the tipping point of m where it is useful to change to FFT+IFFT is related to log(N) of the sample window.
In realtime operation the fact that FFT is batch oriented might be more important than the relative amount of clock cycles, as it may not be acceptable to wait 1024 sample points before filtering, if the application is in a regulation loop for example.
Now a lot of development has been done is this area and plenty of code is available, so trying a couple of solutions and benchmarking is key here.
这取决于您使用的架构和各种其他因素，但 1D DSP 的一般“经验法则”是，如果滤波器尺寸很小，比如少于 100 项，那么直接卷积可能会更好，但对于较大的滤波器尺寸，可能值得在频域中进行快速卷积。
当然，您首先需要确定过滤是性能瓶颈，因为如果您的时域实现已经足够快，那么进行快速卷积的所有额外努力是没有意义的。
底线：从简单的直接卷积开始，然后如果需要的话切换到快速卷积。 （您需要保留第一个实现来验证第二个实现，因此无论如何，这都不是浪费精力。）
It depends on what architecture you're using and various other factors, but the general "rule of thumb" for 1D DSP is that if the filter size is small, say less than 100 terms, you're probably better off with direct convolution, but for larger filter sizes it may be worth doing fast convolution in the frequency domain.
Of course you need to be certain that the filtering is a performance bottleneck first, as there is no point going to all the extra effort of doing fast convolution if your time domain implementation is fast enough already.
Bottom line: start with simple direct convolution and then switch to fast convolution later if you need it. (You'll need to keep the first implementation for validating the second implementation, so it's not wasted effort, by any means.)