Overlap-Add (OLA) STFT Processing

This chapter discusses use of the Short-Time Fourier Transform (STFT) to implement linear filtering in the frequency domain. Due to the speed of FFT convolution, the STFT provides the most efficient implementation engine for most FIR filters encountered in audio signal processing.

Recall from §6.1 the STFT:

where

We noted that if the window has the constant overlap-add property at hop-size ,

then the sum of the successive DTFTs over time equals the DTFT of the whole signal :

Consequently, the inverse-STFT is simply the inverse-DTFT of this sum:

We may now introduce spectral modifications by multiplying each spectral frame by some filter frequency response to get

Note that can be different for each frame, giving a certain class of time-varying filters. The filtered output signal spectrum is then

so that

where

This chapter discusses practical implementation of the above relations using the Fast Fourier Transform (FFT). In particular, we use the FFT to compute efficiently what may be regarded as a sampled DTFT. We will look at how sampling density must be increased along the unit circle when spectral modifications are to be performed, and we will discuss further the COLA condition on the analysis window and hop-size. In the end, our practical FFT-convolution engine will look as follows:

The sum over may be interpreted as adding separately filtered frames . Due to this filtering, the frames must overlap, even when the rectangular window is used. As a result, the overall system is often called an overlap-add FFT processor, or ``OLA processor'' for short. It is regarded as a sequence of FFTs which may be modified, inverse-transformed, and summed. This ``hopping transform'' view of the STFT is the Fourier dual of the ``filter-bank'' interpretation to be discussed in Chapter 9.

---

Subsections

• Convolution of Short Signals
  • Cyclic FFT Convolution
  • Acyclic FFT Convolution
    • Acyclic Convolution in Matlab or Octave
    • Pictorial View of Acyclic Convolution
  • Acyclic FFT Convolution in Matlab or Octave
  • FFT versus Direct Convolution
    • Audio FIR Filters
    • Example 1: Low-Pass Filtering by FFT Convolution
    • Example 2: Time Domain Aliasing
  
  
• Convolving with Long Signals
  • Overlap-Add Decomposition
  • COLA Examples
  • STFT of COLA Decomposition
  • Acyclic Convolution
  • Example of Overlap-Add Convolution
  • Overlap-Add FFT Processing Summary
  • The STFT as a Time-Frequency Distribution
    • Time-Frequency Parameters in the STFT
  
  
• Dual of Constant Overlap-Add
  • Poisson Summation Formula
  • Frequency-Domain COLA Constraints
    • Strong COLA
  • PSF Dual and Graphical Equalizers
  • PSF and Weighted Overlap Add
  • Example COLA Windows for WOLA
  
  
• Overlap-Save Method
• Time Varying OLA Modifications
  • Time-Varying STFT Modifications
  • Length L FIR Frame Filters
  
  
• Nonlinear Modifications
• Weighted Overlap Add
  • WOLA Processing Steps
    • Choice of WOLA Window
  
  
• Review of Zero Padding
• Exercises
• Lab Assignments

---

Order a Hardcopy of Spectral Audio Signal Processing

Previous: Matlab starter code
Next: Convolution of Short Signals

---

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.