### 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).

#### 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