6.01, Fall Semester, 2007—Lecture Notes 1MASSACHVSETTS INSTITVTE OF TECHNOLOGYDepartment of Electrical Engineering and Computer Science6.01—Introduction to EECS IFall Semester, 2007Lecture NotesDifference Equations and Z TransformsZee secret is in zee transforms.Difference Equations with InputSo far, we’ve used difference equations to model the behavior of systems whose values at some timedepend only on their own values at some previous time points. But it is also important to considersystems that depend on an input value, as well.Let’s get the idea by considering a very simple example to start.Example 1 Let’s think about a simple first-order system with a constant input. We can think, forinstance, of a bank account, like Zelda’s or Oswald’s, into which a constant payment c is depositedeach year.We would model that system using the difference equationy(n) = αy(n − 1) + c .Because of the input, c, it is called a non-homogenous difference equation. Because it is so simple,we can see what’s going on just by expanding it out:y(n) = αy(n − 1) + c= α(αy(n − 2) + c) + c= α(α(αy(n − 3) + c) + c) + c. . .= αny(0) + cnXi=0αi= αny(0) + c1 − αn+11 − α.That last step is the standard formula for the sum of a geometric series.What will happen to this bank acc ount as n goes to infinity? It’s clear that if |α| > 1 then thefirst term will go to positive or negative infinity, and we needn’t bother thinking about the secondterm. However, if |α| < 1, then as n goes to infinity, the whole expression goes to c/(1 − α).So, for example, if Uncle Oswald lived forever, with a $100/year being deposited into his account,which as you may recall, had a 5% management fee, the steady state value of the account would be100/(1 − 0.95) = 2000.6.01, Fall Semester, 2007—Lecture Notes 2More generally, a linear difference equation with input can be described in the formKXk=0aky(n + k) =LXl=0blx(n + l) . (1)We can think about it as a process by which a sequence x(n) is transformed into a new sequencey(n). If x(n) = 0 for all n, then this is one of our old familiar homogeneous (without input)difference equations from last time, but written slightly differently. To convert back into that form,we’d have to sayy(n) = −KXk=1aK−1aky(n − k) .For the study of the behavior of more complex systems, we’ll find it algebraically easier to writedifference equations in the form of equation 1.For diffe rence equations with inputs, natural frequencies play an important role, and can be usedto compute solutions. The general solution to a linear difference equation has two parts, one ofwhich depends only on the initial conditions, and one of which depends on the input. The detailsof how to derive a complete closed-form solution are cool, but more detail than we want to getinto in this course. We are going to continue to concentrate on the qualitative behavior of systemsdescribed by difference equations, in particular understanding whether or not a given system willbe stable in the sense made precise by the definition below.Definition 1 A system is bounded-input bounded-output (BIBO) stable if x(n) being bounded forall n necessarily implies that y(n) will also be bounded for all n.For linear difference equations, If the natural frequencies (roots of the characteristic polynomial)λiassociated with the difference equation are all such that |λi| < 1, then the associated system isBIBO-stable. So, our first step in understanding the behavior of a system, with or without input,is to determine the magnitude of the syste m’s natural frequencies. In the format of equation 1, thenatural frequencies are the roots of the characteristic polynomialKXk=0akλk= 0 .Abstraction and modularityWe’ve introduced two kinds of objects in our informal discussion above: sequences and transforma-tions on sequences. As we build complex control or signal-processing s ystem s, or wish to analyzeAunt Zelda’s secret financial empire of linked companies, investments, and bank accounts, we needto develop a system of modularity and abstraction so we can put small pieces together into a clearlyunderstood and analyzable system.We will restrict our attention to a limited but powerful class of sequences, thoses which are solutionsto difference equations with input sequences which are bounded. We can start by defining a setof primitive ope rations on sequences, ones which guarantee that there is a difference equation thatrelates the given input, usually denoted as x(n), to the final output, usually denoted y(n). Theseprimative operations are:6.01, Fall Semester, 2007—Lecture Notes 3• Addition: y(n) = x1(n) + x2(n)• Scaling: y(n) = kx(n)• Shifting back: y(n) = x(n − 1)• Shifting forward: y(n) = x(n + 1)Note that the general difference equation in ( 1) can be generated by a combination of scaling,shifting, and adding. Regardless of whether we are referring to one of the primative operations, orto a general difference equation, we think of a system as taking an input sequence and producingan output sequence.When representing more complicated systems, two primary methods of combination for systems arequite helpful:• Cascade: Using the output sequence of one syste m as the the input to another system,• Parallel sum: Summing the sequences generated by two different systems, to generate an outputIn the next sections, we’ll be able to define this all much more formally.The imp ortant thing here is that when we combine systems, we get another system, and thatsystem has the property that the relationship between the input sequence and the output sequenceis describable by a linear difference equation.Z TransformsIn the Coyote and Roadrunner example from the last lab, we had to play with two coupled lineardifference equations. We made it all work out, but it was a lot of algebra. We could think of thatas a cascade of two systems, with the output of one (the coyote population) being treated as inputto the other (the roadrunner population) and vice versa. As we want to build ever more complexsystems, the algebra will get even more complicated, and not be any fun.Remember how we made multiplication of complex numbers a lot easier by changing to the complexexponential representation? It turns out that we can make operations on sequences a lot easierrepresent by changing the sequence representation, using something called the z transform (alsoknown as generating functions in much of the computer science
View Full Document
Unlocking...