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

Pictorial View of Acyclic Convolution

Figure 8.2: Schematic depiction of the acyclic convolution of two signals.
\includegraphics[width=\textwidth ]{eps/convwaves}

Figure 8.2 shows schematically the result of convolving two zero-padded signals $ x$ and $ h$ . In this case, the signal $ x(n)$ starts some time after $ n=0$ , say at $ n=n_x$ . Since $ h(n)$ begins at time 0 , the output starts promptly at time $ n_x$ , but it takes some time to ``ramp up'' to full amplitude. (This is the transient response of the FIR filter $ h$ .) If the length of $ h$ is $ N_h$ , then the transient response is finished at time $ n=n_x+N_h-1$ . Next, when the input signal goes to zero at time $ n_x+N_x$ , the output reaches zero $ N_h-1$ samples later (after the filter ``decay time''), or time $ n_x+N_x+N_h-1$ . Thus, the total number of nonzero output samples is $ N_x+N_h-1$ .

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 $ N$ is a power of 2.


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