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