8

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!

Hiam
  • 303
  • 1
  • 4
  • 12

4 Answers4

4

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.

Chris A.
  • 6,817
  • 2
  • 25
  • 43
  • Yeah the problem is that i can't understand the algoritms they are telling me about at the wikipedia articles, i can't make it fit into my code. I have tried atleast that much :) – Hiam Apr 04 '12 at 18:00
  • The best reference I've seen for this is a book that I had while at Rutgers by Orfanidis. [Here's a link to the .pdf](http://www.ece.rutgers.edu/~orfanidi/intro2sp/orfanidis-i2sp.pdf) Section 9.9.2 explains it really well. – Chris A. Apr 04 '12 at 18:03
  • Sorry, I would only write the code for this if someone paid me or a grade depended on it. It's not simple and requires thinking about the cases and array sizes etc. That book should help with the understanding though. – Chris A. Apr 04 '12 at 18:10
  • Allthough that pdf is super awesome, it pretty much tells me what i already tried to understand on the wikipedia links. I'll try to continue read it in this paper, and see if i can see it from a diffrent angle, but until then, atleast thanks for a super awesome new source for learning! – Hiam Apr 04 '12 at 18:17
  • There is one thing that confuses me. If i process lets say 1024 samples of data, then fft that into a array. Shoudln't the size of both that array and the filter array be 1024? or should the filter array be double the size(2048)? – Hiam Apr 04 '12 at 18:20
  • Sorry, I didn't quite catch what you were asking. Can you explain your steps more clearly? At what point are you filtering? Keep in mind that the FFT is complex so you should be getting a real component and an imaginary component. This may account for the doubling in size. If you have Matlab or Octave, you can compare against this. – Chris A. Apr 04 '12 at 18:22
  • let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/9692/discussion-between-chris-a-and-hiam) – Chris A. Apr 04 '12 at 18:26
  • In this case why i'm getting confused, is because the real and imaginary component is a struct. so when i allocate the array size i allocate 1024 of the specific object, for the normal data an double array of size 1024, and the fft array allocation FFT_SCTRUCT with a size of 1024. The struct should as said, still hold both the real and imaginary part. Or am i thinking about this wrong? This is partly the reason why i dont understand the overlap :) Thanks for the help by the way! Much appricaited – Hiam Apr 04 '12 at 18:28
  • Sorry, this sounds like a separate detailed question that you'll want to post code for. Make sure to ask specific questions. You're much more likely to get help. – Chris A. Apr 04 '12 at 19:08
4

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.

Jason B
  • 12,835
  • 2
  • 41
  • 43
  • This explains why i need it very well, i just need to think about it a little more and see how i can adopt that knolwedge into code. – Hiam Apr 04 '12 at 18:37
0

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.

sizzzzlerz
  • 4,277
  • 3
  • 27
  • 35
  • I'm probably too stupid, but algoritms does not sit well with me. If you somehow could transform what you said into code, then i might be able to understand it :) – Hiam Apr 04 '12 at 18:01
  • This is an explanation for convolving via the frequency domain, not an explanation for why overlap-add is required. – Oliver Charlesworth Apr 04 '12 at 18:03
0

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.

hotpaw2
  • 70,107
  • 14
  • 90
  • 153