Thanks to the convolution theorem, we have two alternate ways to
perform cyclic convolution in practice:
- Direct calculation in the time domain using (8.13)
- Frequency-domain convolution:
- Fourier Transform both signals
- Perform term by term multiplication of the transformed signals
- 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$](http://www.dsprelated.com/josimages_new/sasp2/img61.png)
-point signals is
![$ {\cal O}(N^2)$](http://www.dsprelated.com/josimages_new/sasp2/img1328.png)
, while that of FFT convolution is
![$ {\cal O}(N \lg N)$](http://www.dsprelated.com/josimages_new/sasp2/img1329.png)
. More
precisely, direct cyclic convolution requires
![$ N^2$](http://www.dsprelated.com/josimages_new/sasp2/img1330.png)
multiplies and
![$ N(N-1)$](http://www.dsprelated.com/josimages_new/sasp2/img1331.png)
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 Section: Acyclic FFT ConvolutionPrevious Section: Loudness Spectrogram Examples