Fast Convolution 1.4 2004/05/17 11:43:39 GMT-5 2004/06/21 11:59:00.562 GMT-5 Douglas L. Jones dl-jones@uiuc.edu Kyle Clarkson kclarks@rice.edu Harika Basana ilsai@rice.edu fast convolution FFT Efficient computation of convolution using FFTs.

Fast Circular Convolution Since, m 0 N 1 x m h n m N y n is equivalent to Y k X k H k y n can be computed as y n IDFT DFT x n DFT h n Cost Direct N 2 complex multiplies. N N 1 complex adds. Via FFTs 3 FFTs + N multipies. N 3 N 2 2 N complex multiplies. 3 N 2 N complex adds. If H k can be precomputed, cost is only 2 FFts + N multiplies.

Fast Linear Convolution DFT produces cicular convolution. For linear convolution, we must zero-pad sequences so that circular wrap-around always wraps over zeros.

To achieve linear convolution using fast circular convolution, we must use zero-padded DFTs of length N L M 1

Choose shortest convenient N (usually smallest power-of-two greater than or equal to L M 1 ) y n IDFT N DFT N x n DFT N h n There is some inefficiency when compared to circular convolution due to longer zero-padded DFTs. Still, O N 2 N savings over direct computation.

Running Convolution Suppose L , as in a real time filter application, or ≫ L M . There are efficient block methods for computing fast convolution.

Overlap-Save (OLS) Method Note that if a length-M filter h n is circularly convulved with a length-N segment of a signal x n ,

the first M 1 samples are wrapped around and thus is incorrect. However, for M 1 n N 1 ,the convolution is linear convolution, so these samples are correct. Thus N M 1 good outputs are produced for each length-N circular convolution. The Overlap-Save Method: Break long signal into successive blocks of N samples, each block overlapping the previous block by M 1 samples. Perform circular convolution of each block with filter h m . Discard first M 1 points in each output block, and concatenate the remaining points to create y n .

Computation cost for a length-N equals 2 n FFT per output sample is (assuming precomputed H k ) 2 FFTs and N multiplies 2 N 2 2 N N N M 1 N 2 N 1 N M 1 complex multiplies 2 N 2 N N M 1 2 N 2 N N M 1 complex adds Compare to M mults, M 1 adds per output point for direct method. For a given M , optimal N can be determined by finding N minimizing operation counts. Usualy, optimal N is 4 M Nopt 8 M .

Overlap-Add (OLA) Method Zero-pad length-L blocks by M 1 samples.

Add successive blocks, overlapped by M 1 samples, so that the tails sum to produce the complete linear convolution.

Computational Cost: Two length N L M 1 FFTs and M mults and M 1 adds per L output points; essentially the sames as OLS method.