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 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 [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.