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.

Answer 2

When you do a convolution (with a finite impulse response filter) by taking the inverse discrete Fourier transform of the product of the discrete Fourier transforms of two input signals, you are really implementing circular convolution. I'll hereby call this "convolution computed in the frequency domain." (If you don't know what a circular convolution is, look at this link. It's basically a convolution where you assume the domain is circular, i.e., shifting the signal off the sides makes it "wrap around" to the other side of the domain.)

You generally want to perform convolution by using fast Fourier transforms for large signals because it's computationally more efficient.

Overlap add (and its cousin Overlap save) are methods that work around the fact the convolutions done in the frequency domain are really circular convolutions, but that in reality we rarely ever want to do circular convolution, but typically rather linear convolutions.

Overlap add does it by "zero-padding" chunks of the input signal and then approrpriately using the portion of the circular convolutions (that were done in the frequency domain) appropriately. Overlap save does it by only keeping the portion of the signal that corresponds to linear convolution and tossing the part that was "corrupted" by the circular shifts.

Here are two links for from Wikipedia for both methods.

Overlap-add : This one has a nice figure explaining what's going on.

Overlap-save

This book by Orfanidis explains it well. See section 9.9.2. It's not the "de facto" standard on signal processing, but it's extremely well written and is a better introduction than other books, in my opinion.

Answer 3

First, understand that convolution in the time domain is equivalent to multiplication in the frequency domain. In convolution, you are at roughly O(n*m) where n is the FIR length and m is the number of samples to be filtered. In the frequency domain, using the FFT, you are running a O(n * log n). For large enough n, the cost of filtering is substantially less when doing it the frequency domain. If n is relatively small, however, the benefits decrease to the point its simpler to filter in the time domain. This breakpoint is subjective, however, figure 50 to 100 as being the point where you might switch.

Answer 4

Yes, a convolution filter will "work", in term of changing the frequency response. But this multiplication in the frequency domain will also contaminate time-domain data at one end with data from the other end, and vice-versa. Overlap add/save extends the FFT size and chops off the "contaminated" end, and then uses that end data to fix the beginning of the subsequent FFT window.