Acyclic FFT Convolution

If we add enough trailing zeros to the signals being convolved, we can
obtain *acyclic* convolution embedded within a cyclic
convolution. How many zeros do we need to add? Suppose the signal
consists of
contiguous nonzero samples at times **0**
to
, preceded and followed by zeros, and suppose
is nonzero
only over a block of
samples starting at time 0. Then the
acyclic convolution of
with
reduces to

(9.15) |

which is zero for and . Thus,

The number is easily checked for signals of length 1 since , where is 1 at time zero and 0 at all other times. Similarly,

(9.16) |

and so on.

When
or
is infinity, the convolution result can be as
small as 1. For example, consider
, with
, and
. Then
. This is an example of what is called *deconvolution*.
In the frequency domain, deconvolution always involves a pole-zero
cancellation. Therefore, it is only possible when
or
is
infinite. In practice, deconvolution can sometimes be accomplished
approximately, particularly within narrow frequency bands
[119].

We thus conclude that, to embed acyclic convolution within a cyclic
convolution (as provided by an FFT), we need to *zero-pad* both
operands out to length
, where
is at least the sum of the
operand lengths (minus one).

[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