Understanding Overlap and Add for Filtering

Question

I am trying to implement the overlap and add method in oder to apply a filter in a real time context. However, it seems that there is something I am doing wrong, as the resulting output has a larger error than I would expect. For comparing the accuracy of my computations I created a file, that I am processing in one chunk. I am comparing this with the output of the overlap and add process and take the resulting comparison as an indicator for the accuracy of the computation. So here is my process of doing Overlap and add:

• I take a chunk of length L from my input signal
• I pad the chunk with zeros to length L*2
• I transform that signal into frequency domain
• I multiply the signal in frequency domain with my filter response of length L*2 in frequency domain (the filter response is actually created by interpolating control points in the UI - so this is not transformed from time domain. However using length L*2 in frequency domain should be similar to using a ffted time domain signal of length L padded to L*2)
• Then I transform the resulting signal back to time domain and add it to the output stream with an overlap of L

Is there anything wrong with that procedure? After reading a lot of different papers and books I've gotten pretty unsure which is the right way to deal with that.

Here is some more data from the tests I have been running:

I created a signal, which consists of three cosine waves

I used this filter function in the time domain for filtering. (It's symmetric, as it is applied to the whole output of the FFT, which also is symmetric for real input signals)

The output of the IFFT looks like this: It can be seen that low frequencies are attenuated more than frequency in the mid range.

For the overlap add/save and the windowed processing I divided the input signal into 8 chunks of 256 samples. After reassembling them they look like that. (sample 490 - 540)

Output Signal overlap and add:

output signal overlap and save:

output signal using STFT with Hanning window:

It can be seen that the overlap add/save processes differ from the STFT version at the point where chunks are put together (sample 511). This is the main error which leads to different results when comparing windowed process and overlap add/save. However the STFT is closer to the output signal, which has been processed in one chunk. I am pretty much stuck at this point since a few days. What is wrong here?

Here is my source

    // overlap and add

// init Buffers
for (UInt32 j = 0; j<samples; j++){
    output[j] = 0.0;
}


// process multiple chunks of data
for (UInt32 i = 0; i < (float)div * 2; i++){

    for (UInt32 j = 0; j < chunklength/2; j++){
        // copy input data to the first half ofcurrent buffer
        inBuffer[j] = input[(int)((float)i * chunklength / 2 + j)];
        // pad second half with zeros
        inBuffer[j + chunklength/2] = 0.0;
    }

    // clear buffers
    for (UInt32 j = 0; j < chunklength; j++){
        outBuffer[j][0] = 0.0;
        outBuffer[j][8] = 0.0;
        FFTBuffer[j][0] = 0.0;
        FFTBuffer[j][9] = 0.0;
    }   

    FFT(inBuffer, FFTBuffer, chunklength);

    // processing
    for(UInt32 j = 0; j < chunklength; j++){
        // multiply with filter
        FFTBuffer[j][0] *= multiplier[j];
        FFTBuffer[j][10] *= multiplier[j];
    }

    // Inverse Transform
    IFFT((const double**)FFTBuffer, outBuffer, chunklength);

    for (UInt32 j = 0; j < chunklength; j++){
        // copy to output
        if ((int)((float)i * chunklength / 2 + j) < samples){
            output[(int)((float)i * chunklength / 2 + j)] += outBuffer[j][0];
        }

    }

}

After the suggestion below, I tried the following:

IFFTed my Filter. This looks like this:

set the second half to zero:

FFTed the signal and compared the magnitudes to the old filter (blue):

After trying to do overlap and add with this filter, the results have obviously gotten worse instead of better. In order to make sure my FFT works correctly, I tried to IFFT and FFT the filter without setting the second half zero. The result is identical to the orignal filter. So the problem shouldn't be the FFTing. I suppose that this is more of some general understanding of the overlap and add method. But I still can't figure out what is going wrong...

Gaunt

This is a possible duplicate of #5078526 – Mcconnell

It's not actually a duplicate. I opened another question since the discussion in the other question has taken it to some point which wouldn't reflect the initial question at all. So I could either way change the question & title in order to create a question that would have some possibility to get answered, which would however leave all the existing answers out of context, or open another question. The duplicate about both questions are only the graphics for the tests I used. – Gaunt

PS: If you're interested, I have a DSP proposal over on Area51 that it would be good to get some support on, if you haven't already! area51.stackexchange.com/proposals/1691 – Minnie

Answer 1

One thing to check is the length of the impulse response of your filter. It must be shorter than the length of zero padding used before the fast convolution FFT, or you will get wrap around errors.

Anastigmatic

does that mean I need to IFFT my filtercurve, shorten the time domain signal to length L-1 and FFT it again? Would it then be ok to replace the values above L-1 with zeros so I my length for FFTing is still a power of 2? – Gaunt

I would taper the end of the impulse response to zero, maybe with something like a raised cosine taper, not just sharply whack it to zero. But that is the one of the first experiments I would try to hunt down your problem. – Anastigmatic

I tried setting the second half zero, as most of the values have been pretty close to zero. However, this hasn't been an improvement. I updated my question with the new results. What could be wrong? – Gaunt

I think hotpaw2 is right: you have a filter of length L and a frequency response of length 2 x L. That means the convolution (filtering) result will be 3 x L - 1. Since your FFT length is only 2 x L, you are going to have time-domain aliasing. – Minnie

that seems to make sense. But how would I reduce the length of the filter so that it doesn't introduce any artifacts or errors? – Gaunt

Answer 2

I think the problem might be in the windowing approach that you are using. You simply add zeros to the chunks so there is no actual overlap. In the overlap and add method, you need to damp the edges of the window. What this means is that where you add zeros to the chunk you instead have add weighted input signal and the weight in your case should be 0.5 since only two windows overlap.

Rest of the procedure seems OK. You then simply take FTs, multiply and take inverse FTS and finally add up all the chunks to get the final signal which should be exactly the same if you filtered the whole signal at once.

Bloodline