1 LINEAR TIME-INVARIANT SYSTEMS AND THEIR …

1 1 LINEAR TIME-INVARIANT SYSTEMSAND THEIR FREQUENCY RESPONSEP rofessor Andrew E. Yagle, EECS 206 Instructor, Fall 2005 Dept. of EECS, The University of Michigan, Ann Arbor, MI 48109-2122I. AbstractThe purpose of this document is to introduce EECS 206 students to LINEAR TIME-INVARIANT (LTI) systemsand THEIR frequency response. It also presents examples of designing a digital speedometer ( , differentiator)and a digital low-pass Table of contents by sections:1. Abstract (you re reading this now)2. LTI SYSTEMS and Other system Properties3. Impulse Response and its Computation4. Convolution and its Computation5. Frequency Response of LTI Systems6. Fourier Series Response of LTI Systems7. Application: Digital Speedometer8. Application: Digital Low-Pass FilterII. LTI SYSTEMS and Other system PropertiesSo just what is a LINEAR TIME-INVARIANT (LTI) system , and whyshould you care? SYSTEMS are used to perform signal processing. The effect of asystem on the spectrum of a signal can beanalyzed easily if and only if the system is LTI, as we will seein these ability todesigna filter to perform a specific signal processing task ( , filter out noise, differentiate,equalize frequency distortion) requires an ability toanalyzewhat a filter will do.

2 We will show how to analyzethe effect of a given LTI system on the spectrum of a signal. Then we will design LTI SYSTEMS for low-passfiltering and differentiation. With a few exceptions ( , median filtering), most filters are LTI SystemsAsystemis a device that accepts an input signalx[n], processes it somehow, and spits out an output signaly[n]. So a system is how a signal gets processed (hence, signal processing ). Some examples of SYSTEMS :y[n] = 3x[n] + 1;y[n] =x[n 2]2;y[n] 2y[n 1] + 3y[n 2] = 4x[n] + 5x[n 1]2 The last equation makes these important points: The outputy[n] at timencan depend on the present inputx[n], past inputsx[n 1], x[n 2]..andfuture inputsx[n+ 1], x[n+ 2].., and on known functions ofn; The outputy[n] can also depend on past values ofitself:y[n 1], y[n 2].. The system equation neednotbe an explicit formulay[n] =F(x[n], x[n 1].. , y[n], y[n 1]..), althoughit should be theoretically possible to write such a system is often designated using the diagramx[n] system y[n].

3 Note that this doesnotmeanthaty[no] dependsonlyonx[no]. Thecomplete output{y[n]}depends on thecomplete input{x[n]}.A system can be a mathematical model of a real-world device, derived using equations of biology, eco-nomics, or some other discipline. Some examples of such models: Biology:Population models in whichx[n] is some environmental factor andy[n] is the population of somespecies in generationn; Economics:Stock market models in whichx[n] is the federal reserve interest rate andy[n] is the daily DowJones close at the end of these are all discrete- time SYSTEMS . In continuous time , SYSTEMS can be used to model almost anyphysical phenomenon ( , circuits in EECS 215 or 314).However, in EECS 206 we willdesigndiscrete- time SYSTEMS to accomplish a specific task, , filter asampledcontinuous- time noisy signal. How are we able to do this?B. LINEAR SystemsAlinearsystem has the property that its response to the sum of two inputs is the sum of the responsesto each input separately:x1[n] LIN y1[n] andx2[n] LIN y2[n] implies (x1[n] +x2[n]) LIN (y1[n] +y2[n])This property is calledsuperposition.

4 By induction, this immediately extends to any number of also implies that scaling the inputx[n] by aconstantascales the output byaas well:x[n] LINEAR y[n] impliesax[n] LINEAR ay[n]This property is calledscaling. Although it is listed as a separate property, it follows from see this, let s use the notationx[n] y[n] as a shorthand to designate that input signal{x[n]}results inoutput signal{y[n]}. Leta=mn, wheremandnareintegers, be any rational number. Then we have:1. Letx[n]n z[n] where outputz[n] is something we wish to Use superposition onnidentical inputsx[n]n: Thennx[n]n=x[n] y[n] =nz[n].3. Soz[n] =y[n]nandx[n]n y[n]n,4. Use superposition onmidentical inputsx[n]n: Thenmx[n]n=ax[n] my[n]n=ay[n].3So the superposition property implies the scaling propertyfor any rational numbera. To extend thisresult to any realaactually requires some high-level mathematical analysis,but since any real number isarbitrarily close to a rational number, we can fudge the result in EECS can you tell whether a system is LINEAR ?

5 You have been exposed to enough LINEAR operatorsin Math 115 and 116 that your intuition will work, with one exception noted below (affine SYSTEMS ). But ifyour intuition isn t working, the following rule often works:If doubling the input doubles the output, then often the system is linearThis is not always true: the systemy[n] =y[n]2x[n]+x[n] has this property but is not LINEAR . But this ruleusually works. Note the rule is just the scaling property fora= implement this test, you can use either of two methods: Replace{x[n]}with{2x[n]}and{y[n]}with{2y [n]}, and see if you can reduce to the original equation; Or:Double the entire equation, and see if you can pull out{2x[n]}and{2y[n]}everywhere. Here{x[n]}meansx[n], x[n 1], x[n 2].. x[n+ 1], x[n+ 2]..Example:y[n] = 3x[n] is LINEAR since (2y[n]) = 3(2x[n]) reduces toy[n] = 3x[n].Example:y[n] = 3x[n] is LINEAR since doubling it yields 2y[n] = 6x[n] (2y[n]) = 3(2x[n]).Example:y[n] =x[n]2is not LINEAR since (2y[n]) = (2x[n])2does not reduce toy[n] =x[n] course, here it is easy to see that doubling the input quadruples the :y[n] 2y[n 1]+ny[n 2] = 3x[n]+4x[n 1] is LINEAR since doubling it yields 2y[n] 4y[n 1]+2ny[n 2] = 6x[n] + 8x[n 1] which becomes (2y[n]) 2(2y[n 1]) +n(2y[n 2]) = 3(2x[n]) + 4(2x[n 1]).

6 Note that you don t need an explicit formula fory[n] in terms of{x[n]}here. In fact, you can easily showthat superposition holds for this equation:y1[n] 2y1[n 1]+ny1[n 2] = 3x1[n]+4x1[n 1] andy2[n] 2y2[n 1]+ny2[n 2] = 3x2[n]+4x2[n 1]implies (y1[n]+y2[n]) 2(y1[n 1]+y2[n 1])+n(y1[n 2]+y2[n 2]) = 3(x1[n]+x2[n])+4(x1[n 1]+x2[n 1])Nonlinear SYSTEMS :y[n] = sin(x[n]);y[n] =|x[n]|;y[n] =x[n]x[n 1];y[n] =x[n] + 1 That last one is tricky it s graph is a straight line, but it isn t LINEAR (doublingx[n] does not doubley[n]).This is called anaffinesystem; affine means LINEAR +constant. C. TIME-INVARIANT SystemsAtime-invariant(TI) system has the property that delaying the input by anyconstant Ddelays the outputby the same amount:x[n] TIME-INVARIANT y[n] impliesx[n D] TIME-INVARIANT y[n D]A TIME-INVARIANT system thus has no internal clock it does not know that the input is can you tell whether a system is TIME-INVARIANT ?Here there is a simple rule that works:Ifnappearsonlyinside brackets (likex[n 1]), then the system is that, inside brackets, shifts are acceptable but scales are not:x[n 2] is OK butx[2n] andx[ n]are not (note time reversalx[ n] is a scaling).

7 Also, weird dependencies likex[n2] are not , not LINEAR :y[n] =x[n]2;y[n] =|x[n] +x[n 1]|;y[n] = sin(x[n]);y[n] =x[n]x[n 1]. LINEAR , not TI:y[n] =nx[n];y[n] =x[2n];y[n] = sin(n)x[n];y[n] ny[n 1] = 2x[n] + 3x[n 1].D. LINEAR TIME-INVARIANT (LTI) SystemsAn LTI system is one that is both LINEAR and TIME-INVARIANT (surprise). The LTI SYSTEMS that will be ofparticular interest in EECS 206 areAutoRegresive Moving-Average (ARMA) difference equations:y[n] +a1y[n 1] +a2y[n 2] +..+aNy[n N] AUTOREGRESSIVE(AR)=b0x[n] +b1x[n 1] +..+bMx[n M] MOVING AVERAGE(MA)This ARMA difference equation of order (N,M) is a discrete- time analogue of a differential autoregressionis a computation of a signaly[n] from itsNpast values{y[n 1], y[n 2].. y[n N]}.Regression analysis is an attempt to compute future values from past values, such as stock market moving averageis a weighted LINEAR combination of present valuex[n] andMpast values{x[n 1], x[n 2].. x[n M]}. It s called a moving average since the quantities being averaged move as time ARMA difference equation can be implemented recursively in timenby rewriting it asy[n] =b0x[n] +.

8 +bMx[n M] a1y[n 1] .. aNy[n N]In Matlab, usey=filter([b0 b1..bM],[1 a1..aN],X].AMoving Average(MA) difference equation of orderMhas just the MA part:y[n] =b0x[n] +b1x[n 1] +..+bMx[n M]We will focus on MA SYSTEMS (described by MA difference equations) in these notes. For ARMA SYSTEMS ,we need the z-transform (covered in the next set of notes).The following problem shows how useful the concept of LTI following two input-output pairs:{1,3} LTI {1,5,6}and{2,7} LTI {2,11,14}Computethe response to{6,7}.Solution:Using linearity,{2,7}-2{1,3}={0,1} LTI {2,11,14}-2{1,5,6}={0,1,2}Using time -invariance, we can advance the output in time by 1to get{0,1,0} LTI {1,2}Using superposition on the responses to [n] and [n 1], we have{6,7}=6{0,1,0}+7{0,1} LTI 6{1,2}+7{0,1,2}={6,19,14}.5 This example suggests that once we know the response to{0,1,0}= [n], we can find the response to anyinput. This is indeed the case, as we show Impulse Response and its ComputationTheimpulse responseh[n] of an LTI system is just the response to an impulse: [n] LTI h[n].)

9 The significance ofh[n] is that we can compute the response toanyinput once we know the response toimpulse. We will derive an explicit formula in the next section. This section will focus on computingh[n].MA system :We can just read offh[n] from its coefficients. Settingx[n] = [n] andy[n] =h[n],y[n] =b0x[n]+b1x[n 1]+..+bMx[n M] h[n] =b0 [n]+b1 [n 1]+..+bM [n M] ={b0, b1.. bM}Example:Fory[n] = 2x[n] +x[n 2] + 4x[n 3], we haveh[n] ={2,0,1,4}. Don t forget the zero!1st-order AR system :This is the one AR system we can analyze without the z-transform (see the nextset of notes for that). We wish to compute the impulse responseh[n] fory[n] ay[n 1] =bx[n].Settingx[n] = [n] andy[n] =h[n] andn= 0,1,2..yieldsn= 0 h[0] ah[ 1] =b [0] =b h[0] =bn= 1 h[1] ah[0] =b [1] = 0 h[1] =ban= 2 h[2] ah[1] =b [2] = 0 h[2] =ba2n= 3 h[3] ah[2] =b [3] = 0 h[3] =ba3An induction argument confirmsh[n] =banu[n]. Using LTI, the response tobk [n k] isbkan ku[n k].y[n] ay[n 1] =b0x[n]+..+bMx[n M] h[n] =b0anu[n]+b1an 1u[n 1]+.

10 +bMan Mu[n M]ARMA difference equations with AR-part orderN 2 will have to wait for the z-transform, in the nextset of notes. But see again how powerful the concept of LTI canbe?IV. Convolution and its ComputationA. Derivation of ConvolutionFor LTI SYSTEMS , we now show how to compute the response toanyinput from the impulse responseh[n]:1. [n] LTI h[n] (Definition of impulse response)2. [n i] LTI h[n i] ( time -invariance works for any constanti) [i] [n i] LTI x[i]h[n i] (Scaling property of LINEAR works for any constantx[i])4. i= x[i] [n i] LTI i= x[i]h[n i] (Superposition property of LINEAR )When you have no idea what to make of a summation, like the one here, try writing it out explicitly. Andif it goes from to , write out the terms for positive and negative indices separately. Here, this gives i= x[i] [n i] =x[0] [n] +x[1] [n 1] +x[2] [n 2] +..+x[ 1] [n+ 1] +x[ 2] [n+ 2] +..={.. x[ 2], x[ 1], x[0], x[1], x[2]..}=x[n].6So i= x[i] [n i] =x[n]! And the response of the LTI system to any inputx[n] isx[n] LTI y[n] = i= x[i]h[n i] =h[n] x[n]This is called theconvolutionof the two signals{h[n]}and{x[n]}, because it is so convoluted (scrambled).