title: Understanding Overlap and Add for Filtering
body: <p>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:</p>
  
  <p><img src="https://i.stack.imgur.com/FmeoQ.png" alt="enter image description here"></p>
  
  <ul>
  <li>I take a chunk of length L from my input signal</li>
  <li>I pad the chunk with zeros to length L*2</li>
  <li>I transform that signal into frequency domain</li>
  <li>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)</li>
  <li>Then I transform the resulting signal back to time domain and add it to the output stream with an overlap of L</li>
  </ul>
  
  <p>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.</p>
  
  <p>Here is some more data from the tests I have been running:</p>
  
  <p>I created a signal, which consists of three cosine waves
  <img src="https://i.stack.imgur.com/lyeqr.png" alt="Input Signal"></p>
  
  <p>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)
  <img src="https://i.stack.imgur.com/QWueP.png" alt="Filter Time Domain"></p>
  
  <p>The output of the IFFT looks like this: It can be seen that low frequencies are attenuated more than frequency in the mid range.
  <img src="https://i.stack.imgur.com/wdgA4.png" alt="Output Signal"></p>
  
  <p>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)</p>
  
  <p>Output Signal overlap and add:
  <img src="https://i.stack.imgur.com/dKH5J.png" alt="Output Signal overlap and add"></p>
  
  <p>output signal overlap and save:
  <img src="https://i.stack.imgur.com/xwrVq.png" alt="output signal overlap and save"></p>
  
  <p>output signal using STFT with Hanning window:
  <img src="https://i.stack.imgur.com/jmIGU.png" alt="output signal using STFT with Hanning window"></p>
  
  <p>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?</p>
  
  <p>Here is my source</p>
  
  <pre><code>    // overlap and add
  
  // init Buffers
  for (UInt32 j = 0; j&lt;samples; j++){
      output[j] = 0.0;
  }
  
  
  // process multiple chunks of data
  for (UInt32 i = 0; i &lt; (float)div * 2; i++){
  
      for (UInt32 j = 0; j &lt; 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 &lt; 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 &lt; 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 &lt; chunklength; j++){
          // copy to output
          if ((int)((float)i * chunklength / 2 + j) &lt; samples){
              output[(int)((float)i * chunklength / 2 + j)] += outBuffer[j][0];
          }
  
      }
  
  }
  </code></pre>
  
  <p>After the suggestion below, I tried the following:</p>
  
  <p>IFFTed my Filter. This looks like this:
  <img src="https://i.stack.imgur.com/YU2U2.png" alt="enter image description here"></p>
  
  <p>set the second half to zero:
  <img src="https://i.stack.imgur.com/Rvmfd.png" alt="enter image description here"></p>
  
  <p>FFTed the signal and compared the magnitudes to the old filter (blue):
  <img src="https://i.stack.imgur.com/W7zJ5.png" alt="enter image description here"></p>
  
  <p>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...</p>