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