# Convolution filter details¶

## Implementation Details¶

The convolution filter efficiently computes the convolution of two signals. The efficiency is achieved by employing the FFT and the circular convolution theorem. The algorithm is a variant of the overlap-add method. It works on a fixed block size \(B\) for arbitrarily long input signals. Thus, the convolution of a streaming input signal with a long FIR filter \(h[n]\) (where the length of \(h[n]\) may exceed the block size \(B\)) is computed with a fixed complexity \(O(B \log B)\).

More formally, the convolution filter computes \(y[n] = (x * h)[n]\) by partitioning the input \(x\) and filter \(h\) into blocks and applies the overlap-add method. Let \(x[n]\) be an input signal of arbitrary length. Often, \(x[n]\) is a streaming input with unknown length. Let \(h[n]\) be an FIR filter with \(M\) taps. The convolution filter works on a fixed block size \(B=2^b\).

First, the input and filter are windowed and shifted to the origin to give the \(k\)-th block input \(x_k[n] = x[n + kB] , n=\{0,1,\ldots,B-1\},\forall k\in\mathbb{Z}\) and \(j\)-th block filter \(h_j[n] = h[n + jB] ,n=\{0,1,\ldots,B-1\},j=\{0,1,\ldots,\lfloor M/B \rfloor\}\). The convolution \(y_{k,j}[n] = (x_k * h_j)[n]\) is efficiently computed with length \(2B\) FFTs as

The overlap-add method sums the "overlap" from the previous block with the current block. To complete the \(k\)-th block, the contribution of all blocks of the filter are summed together to give

The final convolution is then the sum of the shifted blocks

Note that \(y_k[n]\) is of length \(2B\) so its second half overlaps and adds into the first half of the \(y_{k+1}[n]\) block.

## Maximum efficiency criterion¶

To avoid excess computation or maximize throughput, the convolution filter should be given input samples in multiples of the block size \(B\). Otherwise, the FFT of a block is computed twice as many times as would be necessary and hence throughput is reduced.