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


The number![]()



![]() |
(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).
Acyclic Convolution in Matlab
In Matlab or Octave, the conv function implements acyclic convolution:
octave:1> conv([1 2],[3 4]) ans = 3 10 8Note that it returns an output vector which is long enough to accommodate the entire result of the convolution, unlike the filter primitive, which always returns an output signal equal in length to the input signal:
octave:2> filter([1 2],1,[3 4]) ans = 3 10 octave:3> filter([1 2],1,[3 4 0]) ans = 3 10 8
Pictorial View of Acyclic Convolution
Figure 8.2 shows schematically the result of convolving
two zero-padded signals
and
. In this case, the signal
starts some time after
, say at
. Since
begins at
time 0
, the output starts promptly at time
, but it takes some
time to ``ramp up'' to full amplitude. (This is the transient
response of the FIR filter
.) If the length of
is
, then
the transient response is finished at time
. Next, when
the input signal goes to zero at time
, the output reaches
zero
samples later (after the filter ``decay time''), or time
. Thus, the total number of nonzero output samples is
.
If we don't add enough zeros, some of our convolution terms ``wrap around'' and add back upon others (due to modulo indexing). This can be called time-domain aliasing. Zero-padding in the time domain results in more samples (closer spacing) in the frequency domain, i.e., a higher `sampling rate' in the frequency domain. If we have a high enough spectral sampling rate, we can avoid time aliasing.
The motivation for implementing acyclic convolution using a
zero-padded cyclic convolution is that we can use a Cooley-Tukey Fast Fourier
Transform (FFT) to implement cyclic convolution when its length
is
a power of 2.
Next Section:
Acyclic FFT Convolution in Matlab
Previous Section:
Cyclic FFT Convolution