# Inverse Fast Fourier with overlap

I had to work with sound(denoising algorithms), when I read about an algorithm it said that we do DTSTFT(Discrete-time short-time fourier transform) we will create an overlap between each "chunk" of data, for example if I have $$s=[1,2,3,4,5,6]$$ I divide it into $$s^{(1)}=[1,2,3,4]\\s^{(2)}=[3,4,5,6]$$ and then I use FFT on $s^{(1)}$ and $s^{(2)}$(this for $50\%$ overlap)

My problem is how can I do IFFT for this after I touched $S^{(1)}$ and $S^{(2)}$? Everywhere I looked said to do the overlap but had not say a thing about the Inverse

There are several ways.

Start with taking the iFFT of $S^{(1)}$ and $S^{(2)}$. Let's call the results $m^{(1)}$ and $m^{(2)}$, since they are modified. They are back in the time domain and you wish to recombine them into one signal again. Ideally, they would line up perfectly and you could just truncate one and keep the other. This won't happen, so the trick is to fade the latter into the former over the overlap region. At the beginning of the region the weighting of $m^{(1)}$ should be one and the weighting of $m^{(2)}$ should be zero. At the end of the region, the reverse should be true. The simplest solution is a linear transition, but that may not be the best.

For a 50% overlap, there is a nice property of a VonHann window in that the appropriate weighting is implicitely correct in the transition region and you can simply sum the two modified signals over the overlap region. For other overlap sizes the same function can still be used, but it needs to be resized appropriately. The window function can be applied in the time domain before you take the initial FFT, or after the iFFT is done. Of course, which you do greatly affects the bin values, so it depends on the nature of your "touching" on which way is better. The equivalent of a VonHann window can also be done in the frequency domain by calculating a new value for each bin by subtracting the average value of its neighbors and taking half that value. The equation would be $Y[k] = -.25 * X[k-1] + .5 * X[k] - .25 * X[k+1]$ where the $X$s are the original bin values. Doing this before or after your "touching" is the same as if you were windowing the signal before going into the frequency domain or after coming out.

The less touching you do, the more similar the two modified signals are going to be so the smoother the fading transition. For too much touching, the mismatch between the two modified signals may be too great and the results won't be so good. However, with a fading over the overlap region, the results are always going to be a smooth signal.

The VonHann window is good for spectrogram displays because it spreads the value of a sharp peak (near integer frequencies) to the neighboring bins and reduces the leakage of in between frequencies, so when you do a tone sweep through the frequency range, the display remains somewhat consistent and less frame size dependent. Chances are that this same property will make it desirable for you to do the window function before you do your touching.

Hope this helps,

Ced

=================================================

Followup:

The process works like this:

1) Divide your signal into overlapping chunks

2) For each chunk

A) Apply Window function

B) Do the FFT

C) Apply touches

D) Do the iFFT

E) Reverse Window function


3) Recombine chunks into a new signal

Generally speaking, when you recombine the signal you will want a weighting function that goes from 1 to 0 across your overlap region so you are fading out of one chunk as you are fading into the next chuck.

If you use an overlap of greater than 50%, you will have regions where more than two chunks exist for the same time domain and you'll have to figure out an appropriate recombining strategy. My understanding is that overlaps over 50% are in applications where the end result is the frequency domain and your interest is tracking frequency components.

You can use any window function you want, and any overlap amount. If you follow the steps above, if you don't do any "touching" in the frequency domain, you should get your original signal back. The advantage of the VonHann window using a 50% overlap is that the window function actually works as a weighting function so steps 2E and 3 are significantly simplified.

• Thanks for the answer. If I use Hamming window(before the FFT) with $75\%$ overlap, can I use the method you said in VonHann window? And what do you mean by "resized appropriately"? – Holo Feb 11 '18 at 6:44