Convolution and windowing using a buffer - how do I do overlap add?

Question

I'm reading chunks of audio signal (1024 samples) using a buffer, applying a Hanning window, doing an FFT on it, then reading an Impulse Response, doing its FFT and then multiplying the two (convolution) and then taking that resulting signal back to the time domain using an IFFT. I'm zero padding the Impulse Response to match the length of the input signal chunk. However, I still get a noisy click sound after it reads every chunk, because of differences in amplitude I suspect.

At this stage I want to do an Overlap Add but am unclear on how to do it on a buffer. Convolving the input signal chunk with the Impulse Response results on a signal with the same number of samples (1024) so what am I overlapping when it gets to the next chunk?

• Should I be using a longer impulse response and zero pad the signal instead, and then add the rest of that signal after sample 1024 to the next window and so on? Or should I use a longer window on the input signal?

I am doing all this in Python using PyAudio.

Thank you very much for your help

Answer 1

normally i like to define windows to have even symmetry about $t=0$ or $n=0$, but this time i'll do it like MATLAB (except i know how to count from $0$).

Hann Window of width $B$ samples:

$$ w[n] \triangleq \begin{cases} \frac12 \left(1 - \cos\left(\frac{2 \pi}{B} (n+\frac12)\right) \right) \quad \text{for } 0 \le n < B \\ 0 \quad \text{for } n < 0 \text{ or } B \le n \\ \end{cases} $$

another way to write it is

$$ w[n] = \tfrac12 \left(1 - \cos\left(\tfrac{2 \pi}{B} (n+\tfrac12) \right) \right) \cdot \left(u[n] - u[n-B] \right) $$

where $u[n]$ is the discrete unit step function

$$ u[n] \triangleq \begin{cases} 1 \quad \text{for } n \ge 0 \\ 0 \quad \text{for } n < 0 \\ \end{cases} $$

all $B$ samples within the window width are non-zero. let's assume $B$ is even, so that $\frac{B}2$ is an integer. turns out that the Hann window is "complementary" which means the downslope of one Hann window adds to $1$ with the upslope of the window adjacent to its right if they are staggered by $\frac{B}2$ samples. in fact this is true:

$$ \sum\limits_{m=-\infty}^{\infty} w\left[n-m\tfrac{B}2 \right] = 1 $$

that means

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

where

$$ x_m[n] \triangleq x\left[n+m\tfrac{B}2 \right] w[n] $$

so we broke up the input into overlapping little "wavelets" (my term, not in the sense of Daubechies) or "grains", $x_m[n]$, each delayed, in the summation, by $\frac{B}2$ samples in relation to their preceding neighbor $x_{m-1}[n]$.

now we know that for the $m$-th delayed grain, $x_m\left[n-m\tfrac{B}2 \right] \ne 0$ only for $m\tfrac{B}2 \le n < m\tfrac{B}2 + B$

FIR convolution

we have an FIR filter with causal finite impulse response, $h[n]$, with length $L$. so $h[n]=0$ for $n<0$ or $L\le n$. the output of this FIR filter is

$$\begin{align} y[n] & = h[n] \ \circledast \ x[n] \\ & \triangleq \sum\limits_{i=-\infty}^{\infty} h[i] x[n-i] \\ & = \sum\limits_{i=0}^{L-1} h[i] x[n-i] \\ \end{align}$$

OLA convolution

one way to write this:

$$\begin{align} y[n] & = h[n] \ \circledast \ x[n] \\ & = h[n] \ \circledast \ \sum\limits_{m=-\infty}^{\infty} x_m[n-m\tfrac{B}2] \\ & = \sum\limits_{m=-\infty}^{\infty} h[n] \ \circledast \ x_m[n-m\tfrac{B}2] \\ & = \sum\limits_{m=-\infty}^{\infty} y_m[n-m\tfrac{B}2] \\ \end{align}$$

where

$$ \begin{align} y_m[n] & \triangleq h[n] \ \circledast \ x_m[n] \\ & = \sum\limits_{i=0}^{L-1} h[i] x_m[n-i] \\ \end{align} $$

another way to say it is

$$\begin{align} y[n] & = h[n] \ \circledast \ x[n] \\ & = \sum\limits_{i=0}^{L-1} h[i] x[n-i] \\ & = \sum\limits_{i=0}^{L-1} h[i] \sum\limits_{m=-\infty}^{\infty} x_m[n-m\tfrac{B}2 - i] \\ & = \sum\limits_{m=-\infty}^{\infty} \sum\limits_{i=0}^{L-1} h[i] \ x_m[n-i - m\tfrac{B}2] \\ & = \sum\limits_{m=-\infty}^{\infty} y_m[n-m\tfrac{B}2] \\ \end{align}$$

$y_m[n]$ defined the same way as above.

the potentially non-zero length of the block of input samples $x_m[n]$ is $B$ samples, the length of the FIR is $L$ samples, and that makes the potentially non-zero length of the block of output samples $B+L-1$. you can see that

$$ y_m[n] = 0 \quad \text{for }n<0 \text{ or }n \ge B+L-1 $$

$y_m[n]$ could be non-zero for $0 \le n < B+L-1$.

unlike the overlapping input segments $x_m[n]$, the length of the output grains $y_m[n]$ need not be the block length $B$, but can be (and are) longer. so instead of 50% overlap (which is $\frac{B-\tfrac12 B}{B} = \frac12$ or an overlap of $B - \tfrac12 B$ samples) like you might have with the Hann-windowed input, your overlap with the output blocks will be $B+L-1 - \tfrac12 B$ samples.

FFT convolution

the convolution of each block

$$ y_m[n] = \sum\limits_{i=0}^{L-1} h[i] x_m[n-i] $$

can be done with an FFT as long as the FFT size $N$ is at least the length of the output block.

$$ N \ge B+L-1 $$

in this case

$$\begin{align} X_m[k] & = \mathcal{DFT} \left\{ x_m[n] \right\} \\ & = \sum\limits_{n=0}^{N-1} x_m[n] \ e^{-j 2 \pi \frac{nk}{N}} \\ \end{align}$$

$$ Y_m[k] = H[k] \cdot X_m[k] \quad \text{for } 0 \le k < N $$

where

$$\begin{align} H[k] & = \mathcal{DFT} \left\{ h[n] \right\} \\ & = \sum\limits_{n=0}^{N-1} h[n] \ e^{-j 2 \pi \frac{nk}{N}} \\ \end{align}$$

$$\begin{align} Y_m[k] & = \mathcal{DFT} \left\{ y_m[n] \right\} \\ & = \sum\limits_{n=0}^{N-1} y_m[n] \ e^{-j 2 \pi \frac{nk}{N}} \\ \end{align}$$

you need only compute $H[k]$ once for use with all of the blocks. and you get the time-domain samples for each output block with the inverse FFT.

$$ \begin{align} y_m[n] & = \mathcal{IDFT} \left\{ Y_m[k] \right\} \\ & = \frac1N \sum\limits_{k=0}^{N-1} Y_m[k] \ e^{+j 2 \pi \frac{nk}{N}} \\ \end{align} $$

Answer 2

An input chunk of length N convolved with an impulse response of length M will result in an output of length N+M-1 before overlap-add is implemented. Also to prevent circular convolution taking place you need to make sure that the FFT size you use for both is the same size as the output chunk N+M-1.

1) Choose an input segment size N so that N + M - 1 = a power of 2

2) Take input chunk of length N and zero pad so that it is length N + M-1

3) Take impulse response of length M and zero pad so that it length N + M-1 also.

4) Compute DFT of both signals with FFT-size of N+M-1

5) Multiply both signals in frequency domain and IFFT the result

Now remember that the IFFT output is of length N+M-1, hence why methods like overlap-add and overlap-save are used. You need to sum the first M-1 samples from an output chunk with the last M-1 samples from the previous.

Reference: http://www.analog.com/media/en/technical-documentation/dsp-book/dsp_book_Ch18.pdf

P.S I only learned this recently so apologise if i haven't explained anything very well, I have attached a PDF from the DSP guide about FFT convolution which goes into more depth.

Answer 3

it doesnt matter if it's a buffer or not, you still have to have samples of lengths required by the overlap-add.

Reconstitute the buffers into samples of the necessary length, a delay will be necessary as long as the samples required by an overlap-add code function. After than you just need normal overlap add code.

Answer 4

This has an implementation of the convolution using overlap-add method in python, maybe this will be useful.