Getting back to acyclic convolution, we may write it as
Since
is time limited to
(or
),
can be sampled at intervals of
without time aliasing. If
is time-limited to
, then
will be time limited to
. Therefore, we may sample
at intervals of
![]() |
(9.22) |
We conclude that practical FFT acyclic convolution may be carried out
using an FFT of any length
satisfying
![]() |
(9.23) |
where
is the length
DFT of the zero-padded
frame
, and
is the length
DFT of
,
also zero-padded out to length
, with
.
Note that the terms in the outer sum overlap when
even if
. In general, an LTI filtering by
increases
the amount of overlap among the frames.
This completes our derivation of FFT convolution between an
indefinitely long signal
and a reasonably short FIR filter
(short enough that its zero-padded DFT can be practically
computed using one FFT).
The fast-convolution processor we have derived is a special case of the Overlap-Add (OLA) method for short-time Fourier analysis, modification, and resynthesis. See [7,9] for more details.