Linear Convolution in DSP and Hann window

Question

My understanding is that when dealing with discrete finite sequences, convolution done thru FFT is circular. To obtain linear convolution, one would pad the input with zeros up some appropriate length. Then take FFT of two padded sequences, element-by-element multiplication, then IFFT.

For very long signal, to do Linear convolution, one might use the Overlap-Add (OLA) method, which breaks the long signal into segments of equal length, then do the linear convolution as above and sum all the overlapping section together to get the final output.

My question is that isn't that when one breaks a long signal into parts and to use FFT on it later, one should apply a Hann window to minimize Gibbs phenomena due to discontinuities that might occur at two end points ?? So far all the documents about OLA that I come across has not shown use of Hann window in conjuction with OLA. I wonder if it's somehow not needed or all the OLA document just want to illustrate one idea clearly, so as not to confuse reader with addition of Hann window. I understand that if we use both OLA and Hann, it will be more complicated. Please enlighten. Thank you.

Answer 1

This is an insightful question, one that I remember pondering in the 1980s when I first learned of the Overlap-Add (OLA) and Overlap-Save (OLS, sometimes called Overlap-Scrap) methods of "fast convolution".

It turns out that for strict LTI filtering, that you need not window with a Hann, but you could if you wanted to, and for a general frequency-domain modification algorithm, you may want to window with Hann anyway.

Let $w[n]$ be your window and have non-zero length $L-1$ which is less than the length of the FFT, $N$. If it's Hann, the symmetrical definition (with $L$ even) is:

$$ w[n] = \begin{cases} \tfrac12 \cos\left(\tfrac{2\pi}{L}n \right) + \tfrac12 \qquad & \text{if } |n| < \tfrac{L}{2} \\ \\ 0 \qquad & \text{if } |n| \ge \tfrac{L}{2} \\ \end{cases} $$

You can see that

$$ \sum\limits_{m=-\infty}^{\infty} w[n-m\tfrac{L}{2}] = 1 \qquad \forall n \in \mathbb{Z} \tag{1}$$

then

$$\begin{align} x[n] &= x[n] \sum\limits_{m=-\infty}^{\infty} w[n-m\tfrac{L}{2}] \\ \\ &= \sum\limits_{m=-\infty}^{\infty} x[n] w[n-m\tfrac{L}{2}] \\ \\ &= \sum\limits_{m=-\infty}^{\infty} x_m[n-m\tfrac{L}{2}]\\ \end{align}$$

where $$ x_m[n] \triangleq x[n+m\tfrac{L}{2}] w[n] $$ is a "grain" of $x[n]$ slid over to be centered at $n=0$.

You can see you can take each segment or grain, $x_m[n-m\tfrac{L}{2}]$, slide it over to 0 to be $x_m[n]$, pass that through your filter (however it's done, with an FFT or not) to get $y_m[n]$ (which is not normally as short as $L-1$, but must be no longer than the FFT size, $N$), which you slide back to $y_m[n-m\tfrac{L}{2}]$ and add up each term to get $y[n]$:

$$ y[n] = \sum\limits_{m=-\infty}^{\infty} y_m[n-m\tfrac{L}{2}] $$

But this works whether the segments overlap or not as long as Eq. $(1)$ is valid. You can make this work with a rectangular window.

But, for a rectangular window, the hop length (which was $\tfrac{L}{2}$ for the overlapping Hann) will be the same as the non-zero window length for a rectangular window (which was $L-1$ for the Hann). So overlap-add will be more efficient with a rectangular window. But you might want to do other frequency-domain things (like a phase vocoder) so I might recommend using the Hann window anyway for OLA. There is something elegant about it.

Answer 2

I had to deal with this issue a few years ago while coding a channel vocoder for an audio editor.

From a practical point of view, I ended up separating the FFT processing part from the overlap-add part into two different layers.

The OLA processor layer would simply take a signal as input, chop it into smaller pieces and send them to the FFT processing layer. No windowing was applied at this stage to any of the parts so the FFT processing layer could choose the most appropriate windowing function for its needs (if any). On return, the OLA processor would re-assemble back the already processed parts.

For this particular channel vocoder, the FFT layer would apply a Hann window before anything else, then move the signal to FFT space, do the vocoder thing and then IFFT. The last step was to apply a Hann window again and return the processed part to the OLA.

This way I could easily implement a different filter/effect just by writing a different FFT processing layer and possibly using a different window function.