Convolving with Long Signals

We saw that we can perform efficient convolution of two finite-length sequences using the Fast Fourier Transform. There are some situations, however, in which it is impractical to use a single FFT for each convolution operand:

• One or both of the signals being convolved is very long.
• The filter must operate in real time. (We can't wait until the input signal ends before providing an output signal.)

Direct convolution does not have these problems. For example, given a causal finite-impulse resonse (FIR) of length , we need only store the past samples of the input signal to calculate the next output sample, since

Thus, at every time , the output can be computed as a linear combination of the current input sample and the current filter state .

To obtain the benefit of high-speed FFT convolution when the input signal is very long, we simply chop up the input signal into blocks, and perform convolution on each block separately. The output is then the sum of the separately filtered blocks. The blocks overlap because of the ``ringing'' of the filter. For a zero-phase filter, each block overlaps with both of its neighboring blocks. For causal filters, each block overlaps only with its neighbor to the right (the next block in time). The fact that signal blocks overlap and must be added together (instead of simply abutted) is the source of the name overlap-add method for FFT convolution of long sequences [8,10].

The idea of processing input blocks separately can be extended also to both operands of a convolution (both and in ). The details are a straightforward extension of the single-block-signal case discussed below.

When simple FFT convolution is being performed between a signal and FIR filter , there is no reason to use a window function on each input block. In these cases, we may consider that the input signal is processed under a rectangular window. If the window length is , it may advance samples for each successive frame (hop size = samples). In this case, the input blocks do not overlap. On the other hand, when spectral modifications are to be performed, or if the filter is changing each frame ( where is the frame number), then there are good reasons to use a non-rectangular window function and a smaller hop size, as we will develop below.

---

Subsections

• 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

---

Order a Hardcopy of Spectral Audio Signal Processing

Previous: Example 2: Time Domain Aliasing
Next: Overlap-Add Decomposition

---

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.