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...

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.

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.