FFT versus Direct Convolution

The following table compares the number of operations needed to perform the convolution of two length sequences for various values of :

In this example (adapted from [258]), the FFT (software) beats direct time-domain convolution at length 128 and higher. It takes approximately multiply/add operations to calculate the convolution summation directly, while it takes on the order of    log operations to use the FFT method. (Note, by the way, that can be calculated once in advance for time-invariant filtering operations.)

In digital audio, FIR filters are often hundreds of taps long. For such filters, the FFT method is much faster than direct convolution in the time domain.

---

Subsections

• Audio FIR Filters
• Example 1: Low-Pass Filtering by FFT Convolution
• Example 2: Time Domain Aliasing

---

Order a Hardcopy of Spectral Audio Signal Processing

Previous: Acyclic FFT Convolution in Matlab or Octave
Next: Audio FIR Filters

---

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.