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


Convolution of Short Signals

Figure: System diagram for filtering an input signal $ x(n)$ by filter $ h(n)$ to produce output $ y(n)$ as the convolution of $ x$ and $ h$ .
\includegraphics{eps/blackboxgen}

Figure 8.1 illustrates the conceptual operation of filtering an input signal $ x(n)$ by a filter with impulse-response $ h(n)$ to produce an output signal $ y(n)$ . By the convolution theorem for DTFTs2.3.5),

$\displaystyle (h*x) \;\longleftrightarrow\;H \cdot X$ (9.9)

or,

$\displaystyle \hbox{\sc DTFT}_\omega(h*x)\eqsp H(\omega)X(\omega)$ (9.10)

where $ h$ and $ x$ are arbitrary real or complex sequences, and $ H$ and $ X$ are the DTFTs of $ h$ and $ x$ , respectively. The convolution of $ x$ and $ h$ is defined by

$\displaystyle y(n) \eqsp (x*h)(n) \isdefs \sum_{m=-\infty}^{\infty} x(m)h(n-m).$ (9.11)

In practice, we always use the DFT (preferably an FFT) in place of the DTFT, in which case we may write

$\displaystyle \hbox{\sc DFT}_k(h*x)\eqsp H(\omega_k)X(\omega_k)$ (9.12)

where now $ h,x,H,X\in {\bf C}^N$ (length $ N$ complex sequences). It is important to remember that the specific form of convolution implied in the DFT case is cyclic (also called circular) convolution [263]:

$\displaystyle y(n) \eqsp (x*h)(n) \isdefs \sum_{m=0}^{N-1} x(m)h(n-m)_N \protect$ (9.13)

where $ (n-m)_N$ means ``$ (n-m)$ modulo $ N$ .''

Another way to look at convolution is as the inner product of $ x$ , and $ \hbox{\sc Shift}_n[\hbox{\sc Flip}(h)]$ , where $ \hbox{\sc Flip}_n(h)\isdeftext h(-n)=h(N-n)$ , i.e.,

$\displaystyle y(n) \eqsp \langle x, \hbox{\sc Shift}_n[\hbox{\sc Flip}(h)] \rangle. % \qquad\hbox{($h$ real)}
$ (9.14)

This form describes graphical convolution in which the output sample at time $ n$ is computed as an inner product of the impulse response after flipping it about time 0 and shifting time 0 to time $ n$ . See [263, p. 105] for an illustration of graphical convolution.



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]
[Lecture Video]  [Exercises]  [Examination]  
``Spectral Audio Signal Processing'', by Julius O. Smith III, W3K Publishing, 2011, ISBN 978-0-9745607-3-1.
Copyright © 2014-03-23 by Julius O. Smith III
Center for Computer Research in Music and Acoustics (CCRMA),   Stanford University
CCRMA