Low pass filter using FFT instead of convolution implementation

Question

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.

Answer 1

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.

Answer 2

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