2

Are there any good (if possible scientific) resources available (web or books) about overlap processing. I am not that interested in the effects of using overlap processing and windows when analyzing a signal, since the requirements are different. It is more about the following Real Time situation: (I am currently dealing with audio signals)

  • Dividing a signal into smaller parts.
  • Creating overlap windows.
  • FFTing the windowed chunks.
  • Do processing in the frequency domain.
  • IFFT the results.
  • put the chunks together to a continuous stream.

I am especially interested in the influence of the window used on the resulting error as well as the effect of the overlap length. However I couldn't find any good resources that deal with the subject in detail. Any suggestions?

Edit:

After some discussions if using a window function is appropriate, I found a decent handout explaining the overlap and add/save method. http://www.ece.tamu.edu/~deepa/ecen448/handouts/08c/10_Overlap_Save_Add_handouts.pdf

However, after doing some tests, I noticed that the windowed version would perform more accurate in most cases than the overlap & add/save method. Could anybody confirm this? I don't want to jump to any conclusions regarding computation time though....

Edit2:

Here are some graphs from my tests:

I created a signal, which consists of three cosine waves enter image description here

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) enter image description here

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

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) enter image description here enter image description here enter image description here

It can be seen that the overlap add/save processes differ from the windowed version at the point where chunks are put together (sample 511). This is the error which leads to different results when comparing windowed process and overlap add/save. The windowed process is closer to the one processed in one big junk.

However, I have no idea why they are there or if they shouldn't be there at all.

st-h
  • 2,444
  • 6
  • 37
  • 60
  • does this help https://ccrma.stanford.edu/~jos/sasp/Inverse_Transforming_STFT_Bin.html ? – TimCodes.NET Feb 22 '11 at 12:27
  • that's an interesting page, however they focus more on dividing the signal in the frequency domain in smaller bands and dealing with that. It's more about creating filter bands than processing a continuous time domain signal in the frequency domain (which is what I am looking for). – st-h Feb 22 '11 at 12:38
  • Udo Zoelzer is somebody working in this field. "Googling" him might help. – AudioDroid Feb 22 '11 at 12:59
  • **Fast convolution** is another way of relating to what you are looking for. – AudioDroid Feb 22 '11 at 15:44
  • I've written a couple of examples of overlap-save processing in http://stackoverflow.com/questions/2929401/dsp-filtering-in-the-frequency-domain-via-fft and http://stackoverflow.com/questions/3775912/fourier-space-filtering. In my experience, the best way to understand what's happening is to graph the intermediate results of each block in the time domain. – mtrw Feb 22 '11 at 18:35
  • after much googling I found this great handout about overlap-add and overlap-save: http://www.ece.tamu.edu/~deepa/ecen448/handouts/08c/10_Overlap_Save_Add_handouts.pdf – st-h Feb 22 '11 at 20:52
  • So I am adding another question here, hoping someone is still listening: By reading mtrw's links over and over again, I came to the conclusion, that for overlap and add/save - I need to ifft the time domain filter, make it continous within the block, fft it again and then multiply it with the fft of the time domain signal. And finally ifft the result. Does this make any sense at all or did I misunderstand mtrw's answer? – st-h Feb 25 '11 at 00:47

3 Answers3

3

This is fairly well-known area of signal processing, and generally speaking if you are doing processing along the lines of FFT -> spectral processing -> IFFT you need to use the "overlap and add" approach. Cross-correlation of two inputs is a classic example, done much more easily in the spectral domain than the time domain.

Here's a short paper I found right away via Google (I just searched for "fft overlap and add"): http://www.coe.montana.edu/ee/rmaher/ee477/ee477_fftlab_sp07.pdf

I would recommend you invest in a good Signal Processing book, such as the classic Rabiner & Gold "Theory and application of digital signal processing" (Prentice-Hall ISBN 0-13-914101-4). That should cover the concept of overlap-and-add processing.

AAT
  • 3,286
  • 1
  • 22
  • 26
  • Thanks, yes, that is the thing I am interested in. However, everything I found so far covers the topic to a degree similar to the paper you mentioned. Haven't found anything that goes more into detail. E.g. What are the effects of different windows and overlap? What is sufficient for which application? What's the explanation behind the effects that happen? Will order the book you mentioned - already thought about it today. – st-h Feb 22 '11 at 16:22
  • 1
    +1 for the Rabiner and Gold reference, it has the best overlap-save explanation I've ever seen. – mtrw Feb 22 '11 at 18:30
1

When using an FFT for overlap-add or overlap-save fast convolution filtering, normally you don't want to use a windowing function. The circular windowing artifacts cancel out when combining successive FFT frames in canonical overlap add/save filtering.

ADDED:

If you do use a non-rectangular window, you might want to make sure that all the overlapped frames of windows sum to DC, otherwise your resulting filtered signal will have amplitude scalloping. Rectangular windows and raised-cosine (von Hann) windows will sum to DC if the overlap amount is an exact submultiple of the window width (except, of course, at the very start and end of the overlap sequence).

hotpaw2
  • 70,107
  • 14
  • 90
  • 153
  • I just tried that out one more time. Used a chunk of my input signal, added zeros, FFTed it, applied filtering, IFFTed it, added it to the processed signal. The results: added crackles. I don't see this working using overlapp-add without a non rectangular window. However, using a Hann window, for example, everything works as it should. Still in need for in depth explanations though. – st-h Feb 22 '11 at 17:05
  • +1 - I agree that you never want to use a windowing function when doing overlap-save (or overlap-add) processing. You're using the FFT to implement convolution quickly, and using padding to work around the circular convolution that is inherent in using the FFT. Windows are useful for frequency analysis, i.e., looking at the spectral results. In filtering, you don't care about the particular spectral values. – mtrw Feb 22 '11 at 18:33
  • Please explain. Articles like this one, AAT just posted here, recommend using a window function for doing STFT: http://www.coe.montana.edu/ee/rmaher/ee477/ee477_fftlab_sp07.pdf I am pretty confused now, as I couldn't achieve good results without a windowing function. – st-h Feb 22 '11 at 18:48
  • @codeySmurf - Your description of what your want to do makes me think you're trying to filter a time domain signal. You don't need STFTs to do this. Filtering needs either time domain convolution, or overlap-save processing. Neither uses a windowing function. If you wish to examine the frequency content, using FTs, power spectra, STFTs, whatever, you will probably need a windowing function. Data processed in this manner is not appropriate as an input to a filtering process. – mtrw Feb 22 '11 at 19:34
  • well, I start with an input signal in the time domain and a frequency response, which is in the frequency domain. So I'm taking the part of the input signal that is currently available (it's a real time application), transforming it into the frequency domain, multiplying it with the frequency response and transferring it back to the time domain. So, basically it is Filtering. I am still reading your detailed answer for the other question you posted above, but having troubles understanding the last step at the moment. Obviously, the problem is similar though. – st-h Feb 22 '11 at 20:00
  • @codey - the processing technique described in the paper is...well, I wouldn't do things that way. For what you're doing, you need to make sure all the blocks are padded appropriately, but should otherwise be pretty straightforward. You should, just for reference, inverse transform your filter and do regular convolution too. The results should be identical down to numerical error. – mtrw Feb 22 '11 at 20:04
  • Thanks. So, I will take N numbers of input samples and the frequency response of N samples and pad both with 0s to N*2 samples? (or might it be shorter?) Then I'll fft the input signal, multiply both and transfer them back to a signal of N*2 samples in time domain. Then I add N samples to the last samples of the previous iteration and extend the signal with N samples. Is this what you are talking about? What is the downside of the process described in the paper? – st-h Feb 22 '11 at 20:21
  • Windowing distorts the result of an FFT to make it easier to analyze. This distortion is lossy. It throws away "ugly artifacts" that actually contain information about that chunk of the signal. When filtering, you don't want this information loss. If you want to both analyze and filter, use 2 forward FFTs, a windowed FFT for analysis, and another FFT with no window function to do fast convolution filtering. – hotpaw2 Feb 22 '11 at 21:16
  • After finding one of the best handouts ever: http://www.ece.tamu.edu/~deepa/ecen448/handouts/08c/10_Overlap_Save_Add_handouts.pdf I tried to do some tests. However, I noticed that the windowed version would perform more accurate in most cases than the overlap&add/save. Could anybody confirm this? Don't want to jump to any conclusions regarding computation time. – st-h Feb 23 '11 at 01:51
  • 1
    @codeySmurf : What exactly do you mean more accurate? The gold test is to compare with direct linear convolution with the full impulse response of your filter. Are you just zeroing FFT bins? If so that's a bad/broken filter causing your problem. – hotpaw2 Feb 23 '11 at 02:07
  • I test by creating various signals, which are processed in one chunk. Then I'll process these signal by dividing them in multiple chunks, process each of them using the discussed methods and put them together. After that I calculate the difference between the resulting signals. The result has been that the windowed version usually was closer to the signal that has been processed in one chunk. – st-h Feb 23 '11 at 09:58
1

I have been playing with this attempting to answer the question for myself as to why one would use a window. My only references to a synthesis window are this: https://ccrma.stanford.edu/~jos/sasp/Inverse_FFT_Synthesis.html

http://recherche.ircam.fr/anasyn/roebel/amt_audiosignale/VL2.pdf

http://www.dspdimension.com/tutorials/

Stephan Bernsee has some good overview information. His smbpitchshift code uses a synthesis window -- He uses the raised cosine on the input block, then applies it again on the output block, but this I believe is necessary because the pitch shifting algorithm is not a linear filtering operation, so it is certain there may be discontinuous artifacts on the window boundaries, thus a synthesis window is used to create a smooth transition between frames.

I think the reason there is not much information specifically addressing windowing for frequency domain real-time convolution is because it doesn't have a practical application unless you also need to do some analysis (ie, and adaptive filter of some sort), then the topics related to spectral spreading is again of interest.

I have plotted outputs from a filtered signal using both a raised cosine window as well as overlap-add method, and the end result is an identical IR, and identical signals. It comes as no surprise since the same operations performed in the time domain yield the same results.

On the other hand, if I implement a broken filter kernel, a smooth windowing function can help mask artifacts. This in a sense windows the broken IR so there is a more cohesive transition between frames. It would still be better to have an IR that is limited to length nfft/2 in the time domain. If you need to obtain a filter response with an IR longer than nfft/2, then you should consider either using a larger FFT size (if latency is not a problem) or use a partitioned convolution scheme:

http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=0CB4QFjAA&url=http%3A%2F%2Fpcfarina.eng.unipr.it%2FPublic%2FPapers%2F164-Mohonk2001.PDF&ei=qtH0TorDEoKziQKAloHEDg&usg=AFQjCNGDmz79DiuG1kmPXifbWJ7M-gr9rQ&sig2=CMopEcGc1VArZ3gipWTr_w

or

http://www.music.miami.edu/programs/mue/Research/jvandekieft/jvchapter2.htm

I hope that is helpful to somebody reading this

I hope those links help, even though it doesn't directly address windowing as used in real-time Frequency domain filtering.

RJB
  • 366
  • 3
  • 8