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.2)
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 -point signals is , while that of FFT convolution is . More precisely, direct cyclic convolution requires multiplies and additions, while the exact FFT numbers depend on the particular FFT algorithm used [70,58,207]. Some specific cases are compared in §8.1.4 below.

---

Order a Hardcopy of Spectral Audio Signal Processing

Previous: Convolution of Short Signals
Next: Acyclic FFT Convolution

---

written by Julius Orion Smith III
Julius Smith's background is in electrical engineering (BS Rice 1975, PhD Stanford 1983). He is presently Professor of Music and Associate Professor (by courtesy) of Electrical Engineering at Stanford's Center for Computer Research in Music and Acoustics (CCRMA), teaching courses and pursuing research related to signal processing applied to music and audio systems. See http://ccrma.stanford.edu/~jos/ for details.