0.12 Convolution algorithms

Fast convolution by the fft

One of the main applications of the FFT is to do convolution more efficiently than the direct calculation from the definition which is:

which, with a change of variables, can also be written as:

This is often used to filter a signal $x\left(n\right)$ with a filter whose impulse response is $h\left(n\right)$ . Each output value $y\left(n\right)$ requires $N$ multiplications and $N-1$ additions if $y\left(n\right)$ and $h\left(n\right)$ have $N$ terms. So, for $N$ output values, on the order of $N^2$ arithmetic operations are required.

Because the DFT converts convolution to multiplication:

can be calculated with the FFT and bring the order of arithmetic operations down to $Nlog\left(N\right)$ which can be significant for large $N$ .

This approach, which is called “fast convolutions", is a form of block processing since a whole block or segment of $x\left(n\right)$ must be available to calculate even one output value, $y\left(n\right)$ . So, a time delay of one block length is always required. Another problem is the filteringuse of convolution is usually non-cyclic and the convolution implemented with the DFT is cyclic. This is dealt with by appending zeros to $x\left(n\right)$ and $h\left(n\right)$ such that the output of the cyclic convolution gives one block of the output of the desired non-cyclic convolution.

For filtering and some other applications, one wants “on going" convolution where the filter response $h\left(n\right)$ may be finite in length or duration, but the input $x\left(n\right)$ is of arbitrary length. Two methods have traditionally used to break the input into blocks and use the FFT to convolve the blockso that the output that would have been calculated by directly implementing [link] or [link] can be constructed efficiently. These are called “overlap-add" and “over-lap save".

Fast convolution by overlap-add

In order to use the FFT to convolve (or filter) a long input sequence $x\left(n\right)$ with a finite length-M impulse response, $h\left(n\right)$ , we partition the input sequence in segments or blocks of length $L$ . Because convolution (or filtering) is linear, the output is a linear sum of the result of convolving the first block with $h\left(n\right)$ plus the result of convolving the second block with $h\left(n\right)$ , plus the rest. Each of these block convolutions can be calculated by using the FFT. The output is the inverse FFT of the product of the FFT of $x\left(n\right)$ and the FFT of $h\left(n\right)$ . Since the number of arithmetic operation to calculate the convolution directly is on the order of $M^2$ and, if done with the FFT, is on the order of $Mlog\left(M\right)$ , there can be a great savings by using the FFT for large $M$ .

The reason this procedure is not totally straightforward, is the length of the output of convolving a length-L block with a length-M filter is of length $L+M-1$ . This means the output blocks cannot simply be concatenated but must be overlapped and added, hence the name for this algorithm is “Overlap-Add".

The second issue that must be taken into account is the fact that the overlap-add steps need non-cyclic convolution and convolution by the FFT is cyclic. This is easily handled by appending $L-1$ zeros to the impulse response and $M-1$ zeros to each input block so that all FFTs are of length $M+L-1$ . This means there is no aliasing and the implemented cyclic convolution gives the same output as the desired non-cyclic convolution.