Sign in

username:

password:



Not a member?

Search Online Books



Search tips

Free Online Books

Sponsor

Industry's highest performing at the lowest power DSPs now as low as $5.00*
Start development today!
*volume pricing for 10ku

Chapters

See Also

Embedded SystemsFPGAElectronics

Introduction to Digital Filters
    Time Domain Digital Filter Representations
       Convolution Representation

Chapter Contents:

Search Introduction to Digital Filters

  

Book Index | Global Index

Would you like to be notified by email when Julius Orion Smith III publishes a new entry into his blog?

  

Convolution Representation

We will now derive the convolution representation for LTI filters in its full generality. The first step is to express an arbitrary signal $ x(\cdot)$ as a linear combination of shifted impulses, i.e.,

$\displaystyle x(n)=\sum_{i=0}^n x(i)\delta(n-i) \isdef (x\ast \delta)(n), \quad n\in{\bf Z} \protect$ (6.4)

where ``$ \ast $'' denotes the convolution operator. (See [84]6.4 for an elementary introduction to convolution.)

If the above equation is not obvious, here is how it is built up intuitively. Imagine $ \delta(\cdot)$ as a 1 in the midst of an infinite string of 0s. Now think of $ \delta(\cdot -i)$ as the same pattern shifted over to the right by $ i$ samples. Next multiply $ \delta(\cdot -i)$ by $ x(\cdot)$, which plucks out the sample $ x(i)$ and surrounds it on both sides by 0's. An example collection of waveforms $ x(i)\delta(\cdot -i)$ for the case $ x(i) = i, i = -2, -1, 0, 1, 2$ is shown in Fig.5.4a. Now, sum over all $ i$, bringing together the samples of $ x$, to obtain $ x(\cdot)$. Figure 5.4b shows the result of this addition for the sequences in Fig.5.4a. Thus, any signal $ x(\cdot)$ may be expressed as a weighted sum of shifted impulses.

Equation (5.4) expresses a signal as a linear combination (or weighted sum) of impulses. That is, each sample may be viewed as an impulse at some amplitude and time. As we have already seen, each impulse (sample) arriving at the filter's input will cause the filter to produce an impulse response. If another impulse arrives at the filter's input before the first impulse response has died away, then the impulse response for both impulses will superimpose (add together sample by sample). More generally, since the input is a linear combination of impulses, the output is the same linear combination of impulse responses. This is a direct consequence of the superposition principle which holds for any LTI filter.

Figure 5.4: Any signal may be considered to be a sum of impulses. (a) Family of impulses at various amplitudes and time shifts. (b) Addition of impulses in (a), giving part of a ramp signal $ x(i)=i$.
\begin{figure}\input fig/kfig2p11.pstex_t \end{figure}

We repeat this in more precise terms. First linearity is used and then time-invariance is invoked. Using the form of the general linear filter in Eq.$ \,$(4.2), and the definition of linearity, Eq.$ \,$(4.3) and Eq.$ \,$(4.5), we can express the output of any linear (and possibly time-varying) filter by

\begin{eqnarray*} y(n) &=& {\cal L}_n\{x(\cdot)\}\\ &=& {\cal L}_n\{(x \ast \... ...ght\}\\ &\isdef & \sum_{i=-\infty}^\infty x(i) h(n,i) \protect \end{eqnarray*}

where we have written $ h(n, i) \isdef {\cal L}_n\{\delta(\cdot - i)\}$ to denote the filter response at time $ n$ to an impulse which occurred at time $ i$. If we are to be completely rigorous mathematically, certain ``smoothness'' restrictions must be placed on the linear operator $ {\cal L}$ in order that it may be distributed inside the infinite summation [37]. However, practically useful filters of the form of Eq.$ \,$(5.1) satisfy these restrictions. If in addition to being linear, the filter is time-invariant, then $ h(n, i) = h(n - i)$, which allows us to write

$\displaystyle y(n) =\sum_{i=-\infty}^\infty x(i) h(n - i) \isdef (x\ast h)(n), \; n \in {\bf Z} \protect.$ (6.5)

This states that the filter output $ y$ is the convolution of the input $ x$ with the filter impulse response $ h$.

The infinite sum in Eq.$ \,$(5.5) can be replaced by more typical practical limits. By choosing time 0 as the beginning of the signal, we may define $ x(n)$ to be 0 for $ n < 0$ so that the lower summation limit of $ -\infty$ can be replaced by 0. Also, if the filter is causal, we have $ h(n) = 0$ for $ n < 0$, so the upper summation limit can be written as $ n$ instead of $ \infty$. Thus, the convolution representation of a linear, time-invariant, causal digital filter is given by

$\displaystyle \zbox {y(n) = \sum_{i=0}^n x(i) h(n - i) = (x \ast h)(n),\; n=0,1,2,\ldots,} $

for causal input signals (i.e., $ x(n)=0$ for $ n < 0$).

Since the above equation is a convolution, and since convolution is commutative (i.e., $ (x \ast h)(n) = (h \ast x)(n)$ [84]), we can rewrite it as

$\displaystyle \zbox {y(n) = \sum_{i=0}^n h(i) x(n - i) = (h \ast x)(n), \; n\ge0} $

or

$\displaystyle y(n) = h(0) x(n) + h(1) x(n-1) + h(2) x(n-2) + \cdots + h(n) x(0). $

This latter form looks more like the general difference equation presented in Eq.$ \,$(5.1). In this form one can see that $ h(i)$ may be identified with the $ b_i$ coefficients in Eq.$ \,$(5.1). It is also evident that the filter operates by summing weighted echoes of the input signal together. At time $ n$, the weight of the echo from $ i$ samples ago [$ x(n - i)$] is $ h(i)$.


Subsections
Previous: Implications of Linear-Time-Invariance
Next: Convolution Representation Summary

Order a Hardcopy of Introduction to Digital Filters

About the Author: Julius Orion Smith III
Julius Smith's background is in electrical engineering (BS Rice 1975, PhD Stanford 1983). He is presently Professor of Music and Associate Professor (by courtesy) of Electrical Engineering at Stanford's Center for Computer Research in Music and Acoustics (CCRMA), teaching courses and pursuing research related to signal processing applied to music and audio systems. See http://ccrma.stanford.edu/~jos/ for details.


Comments

No comments yet for this page


Add a Comment
You need to login before you can post a comment (best way to prevent spam). ( Not a member? )