Convolving with Long Signals

We saw that we can perform efficient convolution of two finite-length sequences using a Fast Fourier Transform (FFT). 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.)

Thus, at every time
, the output
can be computed as a linear
combination of the *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 [7,9].

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 non-rectangular window function on each input block. A rectangular window length of samples may advance samples for each successive frame (hop size samples). In this case, the input blocks do not overlap, while the output blocks overlap by the FIR filter length (minus one sample). On the other hand, if nonlinear and/or time-varying spectral modifications to be performed, then there are good reasons to use a non-rectangular window function and a smaller hop size, as we will develop below.

- Overlap-Add Decomposition
- COLA Examples
- STFT of COLA Decomposition
- Acyclic Convolution
- Example of Overlap-Add Convolution
- Summary of Overlap-Add FFT Processing

[How to cite this work] [Order a printed hardcopy] [Comment on this page via email]

Copyright ©

Center for Computer Research in Music and Acoustics (CCRMA), Stanford University