Learning Objectives

- Learn methods to do convolution by FFT more efficiently.

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

\[y(n)=\sum h(m)x(n-m)\]

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

\[y(n)=\sum x(m)h(n-m)\]

This is often used to filter a signal x(n)x(n)" role="presentation" style="position:relative;" tabindex="0">\(x(n)\) with a filter whose impulse response is x(n)x(n)" role="presentation" style="position:relative;" tabindex="0">\(h(n)\)h(n)h(n)" role="presentation" style="position:relative;" tabindex="0">. Each output value x(n)x(n)" role="presentation" style="position:relative;" tabindex="0">\(y(n)\)y(n)y(n)" role="presentation" style="position:relative;" tabindex="0"> requires \(N\) multiplications and N-1N-1" role="presentation" style="position:relative;" tabindex="0">\(N-1\) additions if x(n)x(n)" role="presentation" style="position:relative;" tabindex="0">\(y(n)\) and x(n)x(n)" role="presentation" style="position:relative;" tabindex="0">\(h(n)\) have \(N\) terms. So, for \(N\) output values, on the order of N2N2" role="presentation" style="position:relative;" tabindex="0">\(N^2\) arithmetic operations are required.

Because the DFT converts convolution to multiplication:

\[\text{DFT}y(n)=\text{DFT}\left \{ h(n)\text{DFT}x(n)\right \}\]

can be calculated with the FFT and bring the order of arithmetic operations down to Nlog(N)Nlog(N)" role="presentation" style="position:relative;" tabindex="0">\(N\log (N)\) which can be significant for large \(N\).

NN" role="presentation" style="position:relative;" tabindex="0">This approach, which is called “fast convolutions", is a form of block processing since a whole block or segment of x(n)x(n)" role="presentation" style="position:relative;" tabindex="0">\(x(n)\) must be available to calculate even one output value, x(n)x(n)" role="presentation" style="position:relative;" tabindex="0">\(y(n)\). So, a time delay of one block length is always required. Another problem is the filtering use of convolution is usually non-cyclic and the convolution implemented with the DFT is cyclic. This is dealt with by appending zeros to x(n)x(n)" role="presentation" style="position:relative;" tabindex="0">\(x(n)\) and x(n)x(n)" role="presentation" style="position:relative;" tabindex="0">\(h(n)\) 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 x(n)x(n)" role="presentation" style="position:relative;" tabindex="0">\(h(n)\) may be finite in length or duration, but the input x(n)x(n)" role="presentation" style="position:relative;" tabindex="0">\(x(n)\) is of arbitrary length. Two methods have traditionally used to break the input into blocks and use the FFT to convolve the block so that the output that would have been calculated by directly implementing the above equations, can be constructed efficiently. These are called “overlap-add" and “over-lap save".

## h(n)h(n)" role="presentation" style="position:relative;" tabindex="0">Contributor