Overlap-save method of block convolution for fast convolution on audio streams.

Posted on Posted in Audio, Mathematics

Let $$\mathbf{h}$$ be a vector of size $$P$$ containing the impulse response you wish to convolve with, and let $$\mathbf{x}$$ contain an unknown number of float values which is the input audio stream.

Note that an FIR filter can be expressed as follows:
$$FIR(x[n],\mathbf{h})=y[n]=\sum_{j=0}^{P-1}({x[n+j] \cdot h[j]})$$

By chopping up $$x[n]$$ into sections of length $$L$$, we can apply the overlap-save algorithm to calculate the output of the filter.

Let:
$$x[n]=\sum_{r=0}^\infty x_r[n-rL]$$

where:
$$x_r[n]=x[n+r(L-P+1)-P+1] \qquad 0\leq n\leq L-1$$ and 0 otherwise.
We have each $$x_r$$ overlapping the previous one by $$P-1$$ points.

Next we convolve each $$x_r[n]$$ with $$h[n]$$ and discard $$0\leq n \leq P-2$$ of the output $$y[n]$$ where:

$$y[n]=x_r[n]*h[n]$$ (where $$*$$ refers to fourier convolution)

Discard $$0\leq n \leq P-2$$ of $$y[n]$$, ie $$P-1\leq n \leq L-1$$ are the valid outputs for $$y[n]$$.

This does not solve the problem of buffer management, you still have to work out how to manage the samples coming in if they come in blocks of size $$K$$ from an audio stream.

Leave a Reply

Your email address will not be published.