direct Frequency domain FIR filtering vs Overlap-add method

Question

I'm trying to do bandpass filtering of a EEG signal samples at 250Hz and benchmarking the following 4 methods of FIR filtering for different filter orders. The length of the signal is 15000 samples.

1. Time Domain Approach (convolution)
2. Direct frequency domain approach
3. Overlap-add
4. Overlap-save

For follow the procedure listed in the following Wiki pages for overlap-add and overlap-save http://en.wikipedia.org/wiki/Overlap%E2%80%93add_method http://en.wikipedia.org/wiki/Overlap%E2%80%93save_method

For frequency domain approach I do FFT for the entire length of the signal, multiply with the frequency response of filter H and then IFFT the result.

For overlap and add, I chose M(overlap) to be 1+length_of_response and L to be twice of M.

Although one would expect Overlap-add to outperform Direct Frequency domain approach, this is not what I see in my benchmark results(see attached figure).

Please help me out in understanding where I might be going wrong.

Answer 1

An FFT of twice the filter order is kind of short. Take a look at the "Choice of FFT size" section from this article I wrote a while back.

Also your whole signal will fit into a reasonable size FFT, so I think the single FFT approach is fine in this case.

Answer 2

Actually I think the results you obtained are correct. Indeed the computation savings made with overlap-add and overlap-save methods generally increases with the FFT block size. What you are doing in your direct frequency domain approach, provided you use adequate zero padding to prevent circular convolution, is simply the overlap-add method performed with a single block, i.e. with the longest possible block length given your signal. Thus it should prove to be the less computationally intensive of all methods.