<< Chapter < Page Chapter >> Page >
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 logbase --> N complex multiplies.
    • 3 N 2 logbase --> 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 alwayswraps 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 logbase --> 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 logbase --> N N N M 1 N 2 logbase --> N 1 N M 1 complex multiplies 2 N 2 logbase --> N N M 1 2 N 2 logbase --> 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 N opt 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.

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Digital signal processing: a user's guide. OpenStax CNX. Aug 29, 2006 Download for free at http://cnx.org/content/col10372/1.2
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Digital signal processing: a user's guide' conversation and receive update notifications?

Ask