Next  |  Prev  |  Up  |  Top  |  Index  |  JOS Index  |  JOS Pubs  |  JOS Home  |  Search

Cyclic FFT Convolution

Thanks to the convolution theorem, we have two alternate ways to perform cyclic convolution in practice:

  1. Direct calculation in the time domain using (8.13)
  2. Frequency-domain convolution:
    1. Fourier Transform both signals
    2. Perform term by term multiplication of the transformed signals
    3. Inverse transform the result to get back to the time domain
For short convolutions (less than a hundred samples or so), method 1 is usually faster. However, for longer convolutions, method 2 is ultimately faster. This is because the computational complexity of direct cyclic convolution of two $ N$ -point signals is $ {\cal O}(N^2)$ , while that of FFT convolution is $ {\cal O}(N \lg N)$ . More precisely, direct cyclic convolution requires $ N^2$ multiplies and $ N(N-1)$ additions, while the exact FFT numbers depend on the particular FFT algorithm used [80,66,224,277]. Some specific cases are compared in §8.1.4 below.

Next  |  Prev  |  Up  |  Top  |  Index  |  JOS Index  |  JOS Pubs  |  JOS Home  |  Search

[How to cite this work]  [Order a printed hardcopy]  [Comment on this page via email]

``Spectral Audio Signal Processing'', by Julius O. Smith III, W3K Publishing, 2011, ISBN 978-0-9745607-3-1.
Copyright © 2016-07-18 by Julius O. Smith III
Center for Computer Research in Music and Acoustics (CCRMA),   Stanford University