使用，而不是卷积执行的FFT的低通滤波器 [英] Low pass filter using FFT instead of convolution implementation

问题描述

实施的低通FIR滤波器，之一，当应该使用FFT和IFFT，而不是时域卷积？

Implementing a low pass FIR filter, when should one use FFT and IFFT instead of time-domain convolution?

的目标是实现实时计算所需的最低CPU时间。据我所知，FFT拥有大约为O（n log n）的复杂性，但卷积在时域是O（N²）的复杂性。为执行在频域中的低通滤波器，应该使用的FFT，然后乘以滤波系数（其被翻译成频域）的​​每个值，则使IFFT

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.

所以，问题是当它是有道理的使用基于频（FFT + IFFT）过滤，而不是使用直接卷积基于FIR滤波器的？再说了，如果有32个定点系数，应FFT + IFFT使用或不？怎么样128的系数？等等...

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...

试图优化一个已经存在的源$ C ​​$ C（基于卷积的FIR滤波器），我完全糊涂了，或者我应该使用FFT或者只是优化它使用SSE或没有。

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.

推荐答案

卷积实际上是O（M * n），其中m是有限脉冲响应的宽度，并且N采样窗口

Convolution is actually O(m*n) where m is the width of the finite impulse response, and N the sample window.

因此​​m的临界点是有用的改变的FFT + IFFT登录样本窗口（N）的关系。

So the tipping point of m where it is useful to change to FFT+IFFT is related to log(N) of the sample window.

在实时操作的事实，FFT是批次取向可能比时钟周期的相对量更重要的，因为它可能是不能接受的滤波之前的等待时间1024个样本点，如果应用程序是在一调节环路例如。

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.

现在很大的发展已经做的是code这个区域，大量可用，所以想了几个解决方案和基准测试在这里是关键。

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.

这篇关于使用，而不是卷积执行的FFT的低通滤波器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！