Lowpass FIR Filter with FFT Convolution - Overlap add, why and how

Question

First off, sorry for not posting the code here. For some reason all the code got messed upp when i tried to enter the code i had onto this page, and it probably was too much anyhow to post, to be acceptable. Here is my code: http://pastebin.com/bmMRehbd

Now from what im being told, the reason why i can't get a good result out of this code is because i'm not using overlap add. I have tried to read on several sources on the internet as to why i need to use overlap add, but i can't understand it. It seems like the actuall filter works, cause anything above the given cutoff, gets indeed cutoff.

I should mention this is code made to work for vst2-sdk.

Can someone tell me why i need to add it and how i can implement a overlap add code into the given code?

I should also mention that i'm pretty stupid when it comes to algoritms and maths. I'm one of those persons who need to visually get a grip of what i'm doing. That or getting stuff explained by code :), and then i mean the actual overlap.

Overlad add theory: http://en.wikipedia.org/wiki/Overlap%E2%80%93add_method

Thanks for all the help you can give!

Answer 1

The overlap-add method is needed to handle the boundaries of each fft buffer. The problem is that multiplication in the FFT domain results in circular convolution in the time domain. This means that after perfoming the IFFT, the results at the end of the frame wrap around and corrupt the output samples at the beginning of the frame.

It may be easier to think about it this way: Say you have a filter of length N. Linear convolution of this filter with M input samples actually returns M+N-1 output samples. However, the circular convolution done in the FFT domain results in the same number of input and output samples, M. The extra N-1 samples from linear convolution have "wrapped" around and corrupted the first N-1 output samples.

Here's an example (matlab or octave):

a = [1,2,3,4,5,6];
b = [1,2,1];
conv(a,b)  %linear convolution

    1    4    8   12   16   20   17    6

ifft(fft(a,6).*fft(b,6))  %circular convolution

    18   10    8   12   16   20

Notice that the last 2 samples have wrapped around and added to the first 2 samples in the circular case.

The overlap-add/overlap-save methods are basically methods of handling this wraparound. The overlap of FFT buffers is needed since circular convolution returns fewer uncorrupted output samples than the number of input samples.