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 [261]), 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

---

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

Order a Hardcopy of Spectral Audio Signal Processing

---

About the Author: 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.

Hai Smith,

I have one small doubt in frequency domain based filtering method.

Whether the performance point of view, will this overlap save method produces identical results ( bit by bit matching) as that of time domain convolution. Obviously not but more or less both methods produces same results. There might be some kind of dB level differences when processing real time signals.

Please provide your views in this regard.

Regards,
Sreenivas.