Next  |  Prev  |  Up  |  Top  |  Index  |  JOS Index  |  JOS Pubs  |  JOS Home  |  Search


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 $ x(n)$ consists of $ N_x$ contiguous nonzero samples at times 0 to $ N_x-1$ , preceded and followed by zeros, and suppose $ h(n)$ is nonzero only over a block of $ N_h$ samples starting at time 0. Then the acyclic convolution of $ x$ with $ h$ reduces to

$\displaystyle (x\ast h)(n) \isdefs \sum_{m=-\infty}^\infty x(m)h(n-m) \eqsp \sum_{m=0}^n x(m)h(n-m)$ (9.15)

which is zero for $ n<0$ and $ n>(N_x+N_h-1)-1$ . Thus,
$\textstyle \parbox{0.8\textwidth}{\emph{the acyclic convolution of $N_x$\ samples with $N_h$\ samples produces at most $N_x+N_h-1$\ nonzero samples.}}$
The number $ N_x+N_h-1$ is easily checked for signals of length 1 since $ \delta\ast \delta = \delta$ , where $ \delta $ is 1 at time zero and 0 at all other times. Similarly,

$\displaystyle [\delta+\hbox{\sc Shift}_1(\delta)] \ast [\delta+\hbox{\sc Shift}_1(\delta)] \eqsp \delta + 2\hbox{\sc Shift}_1(\delta) + \hbox{\sc Shift}_2(\delta)$ (9.16)

and so on.

When $ N_x$ or $ N_h$ is infinity, the convolution result can be as small as 1. For example, consider $ x=[1,r,r^2,r^3,\ldots]$ , with $ \left\vert r\right\vert<1$ , and $ h=[1,-r,0,0,\ldots]$ . Then $ x\ast h = [1, 0, 0,
\ldots]$ . 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 $ N_x$ or $ N_h$ 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 $ N$ , where $ N$ is at least the sum of the operand lengths (minus one).



Subsections
Next  |  Prev  |  Up  |  Top  |  Index  |  JOS Index  |  JOS Pubs  |  JOS Home  |  Search

[How to cite this work]  [Order a printed hardcopy]  [Comment on this page via email]

``Spectral Audio Signal Processing'', by Julius O. Smith III, W3K Publishing, 2011, ISBN 978-0-9745607-3-1.
Copyright © 2016-07-18 by Julius O. Smith III
Center for Computer Research in Music and Acoustics (CCRMA),   Stanford University
CCRMA