Low-pass filter using FFT instead of convolution

Question

Implementing a low-pass FIR filter, when do you need to use FFT and IFFT instead of time-domain convolution?

The goal is to achieve the smallest processor time required for real-time calculations. As I know, FFT has O (n log n) complexity, but time-domain convolution has O (n²) complexity. To implement a low-pass filter in the frequency domain, you need to use FFT, then multiply each value with filter coefficients (which are translated into the frequency domain), and then do IFFT.

So the question is, when is it justifiable to use frequency filtering (FFT + IFFT) instead of using a direct convolution-based FIR filter? Say, if you have 32 fixed-point ratios, should you use FFT + IFFT or not? What about 128 odds? And so on...

Trying to optimize the existing source code (based on convolution based on the FIR filter), I'm completely confused, either I have to use FFT, or just optimize it to use SSE or not.

Answer 1

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

Thus, the skew point m, where it is useful to switch to FFT + IFFT, is related to the log (N) of the sample window.

In real time, the fact that the FFT is burst may be more important than the relative magnitude of the clock cycles, since it may not be acceptable to wait for 1024 sample points before filtering if the application is in the control loop, for example.

Now a lot of development has been done, this area and many codes are available, so here you can find a couple of solutions and benchmarking.

Answer 2

It depends on what architecture you are using and what 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 probably have a direct convolution, but for larger ones filter sizes may need to do a quick convolution in the frequency domain.

Of course, you must be sure that filtering is a performance bottleneck, since it makes no sense to do your best to quickly convolution if your implementation in the time domain is already fast enough.

Bottom line: start with a simple direct convolution, and then switch to a quick convolution later if you need it. (You will need to save the first implementation to verify the second implementation, so it will not be wasted. By any means.)