Overlap-Add FFT Processing Summary

Chapter Contents:

Search Spectral Audio Signal Processing

Would you like to be notified by email when Julius Orion Smith III publishes a new entry into his blog?

Overlap-Add FFT Processing Summary

Overlap-add FFT processors provide efficient implementations for FIR filters longer than 100 or so taps. Specifically, we ended up with:

$\displaystyle y = \sum_{m=-\infty}^\infty \hbox{\sc Shift}_{mR} \left( \hbox{\s... ... \hbox{\sc DFT}_N\left[\hbox{\sc Shift}_{-mR}(x)\cdot w \right]\right\}\right)$

where $\hbox{\sc Shift}()$ is acyclic in this context. Stated as a procedure, we have the following steps in an overlap-add FFT processor:

(1): Extract the th length frame of data at time .
(2): Shift it to the base time interval (or ).
(3): Optionally apply a length analysis window (causal or zero phase, as preferred). For simple LTI filtering, the rectangular window is fine.
(4): Zero-pad the windowed data out to the FFT size (a power of 2), such that $N\geq M+L-1$ , where is the FIR filter length.
(5): Take the -point FFT.
(6): Apply the filter frequency-response $H=\hbox{\sc FFT}_N(h)$ as a windowing operation in the frequency domain.
(7): Take the -point inverse FFT.
(8): Shift the origin of the -point result out to sample where it belongs.
(9): Sum into the output buffer containing the results from prior frames (OLA step).

The condition $N\geq M+L-1$ is necessary to avoid time aliasing, i.e., to implement acyclic convolution using the FFT; this condition is equivalent to a minimum sampling-rate requirement in the frequency domain.

A second condition is that the analysis window be COLA at the hop size used:

$\displaystyle \sum_m w(n-mR) = 1, \, \forall n\in{\bf Z}.$

Order a Hardcopy of Spectral Audio Signal Processing

Previous: Example of Overlap-Add Convolution
Next: The STFT as a Time-Frequency Distribution

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.

Sign in

Search Online Books

Free Online Books

Sponsor

Chapters

Spectral Audio Signal Processing
    Overlap-Add (OLA) STFT Processing
       Convolving with Long Signals
          Overlap-Add FFT Processing Summary