Why should all the poles be inside the unit circle for a discrete-time digital system to be stable? And why must we care about regions of convergence (ROC)? With only a small investment in time, it is possible to gain a very clear understanding of exactly what is going on — it is not complicated if learnt step at a time, and there are not many steps.
Step 1: Formal Laurent Series
Despite the fancy name, Step 1 is straightforward. Digital systems operate on sequences of numbers: a sequence of numbers goes into a system and a sequence of numbers comes out. For example, if denotes an input sequence then an example of a discrete-time system is .
How can a specific input sequence be written down, and how can the output sequence be computed?
The direct approach is to specify each individual , for example, for , , , and for . Direct substitution then determines the output: , and so forth.
The system has a number of nice properties, two of which are linearity and time invariance. This is often expressed in textbooks by saying the system is LTI, where the L in LTI stands for Linear and the TI stands for Time Invariant. When first learning about discrete-time digital systems, usually attention is restricted to linear time-invariant systems, and indeed, it is for such systems that the Z-transform proves most useful.
Any LTI system has the property that the output is the convolution of the input with the impulse response. For example, the impulse response of is found by injecting the input and for . This impulse as input produces the output , and for . It is common to denote the impulse response using the letter , that is, , and for .
By the definition of convolution, the convolution of a sequence with a sequence is . If , and for then and this is equal to ; we have verified in this particular case that the output of the original system is indeed given by convolving the input with the impulse response.
Let’s be honest: writing , and for is tedious! An alternative is to use a formal Laurent series to represent a sequence. Here, “formal” means that we do not try to evaluate this series! A Laurent series just means instead of limiting ourselves to polynomials in a dummy variable , we allow negative powers of , and we allow an infinite number of non-zero terms. (The variable has nothing to do with time; it will be replaced in Step 3 by where it will be referred to as the Z-transform. To emphasise, is just a dummy variable, a placeholder.)
Precisely, the sequence , and for can be encoded as ; isn’t that much more convenient to write? In general, an arbitrary sequence can be encoded as the formal series . The sole purpose of the term is as a placeholder for placing the coefficient . In other words, if we are given the formal series then we immediately know that that is our secret code for the sequence that consists of all zeros except for the -5th term which is 2, the 0th term which is 3 and the 7th term which is 1.
Being able to associate letters with encoded sequences is convenient, hence people will write to mean , , and for . Do not try to evaluate for some value of though – that would make no sense at this stage. (Mathematically, we are dealing with a commutative ring that involves an indeterminant . If you are super-curious, see Formal Laurent series.)
Now, there is an added benefit! If the input to our system is and the impulse response is then there is a “simple” way to determine the output: just multiply these two series together! The multiplication rule for formal Laurent series is equivalent to the convolution rule for two sequences. You can check that (corresponding to etc) really is the output of our system if the input were for , , , and for .
- A formal Laurent series provides a convenient encoding of a discrete-time sequence.
- Convolution of sequences corresponds to multiplication of formal Laurent series.
- Do not think of formal Laurent series as functions of a variable. (They are elements of a commutative ring.) Just treat the variable as a placeholder.
- In particular, there is no need (and it makes no sense) to talk about ROC (regions of convergence) if we restrict ourselves to formal Laurent series.
Step 2: Analytic Functions
This is where the fun begins. We were told not to treat a formal Laurent series as a function, but it is very tempting to do so… so let’s do just that! 🙂 The price we pay though is that we do need to start worrying about ROC (regions of convergence) for otherwise we could end up with incorrect answers.
To motivate further our desire to break the rules, consider the LTI system . Such a system has “memory” or an “internal state” because the current output depends on a previous output and hence the system must somehow remember previous values of the output. We can assume that in the distant past the system has been “reset to zero” and hence the output will be zero up until the first time the input is non-zero. The impulse response is determined by setting to 1 and observing the output: , , and in general for . Encoding this using a formal Laurent series gives the alternative representation .
There is a more “efficient” representation of based on the Taylor series expansion . Indeed, if we were to break the rules and treat as a function, we might be tempted to write instead of . It turns out that, with some care, it is mathematically legitimate to do this. (Furthermore, Step 3 will explain why it is beneficial to go to this extra trouble.)
We know we can encode a sequence using a formal Laurent series, and we can reverse this operation to recover the sequence from the formal Laurent series. In Step 2 then, we just have to consider when we can encode a formal Laurent series as some type (what type?) of function, meaning in particular that it is possible to determine uniquely the formal Laurent series given the function.
Power series (and Laurent series) are studied in complex analysis: recall that every power series has a (possibly zero) radius of convergence, and within that radius of convergence, a power series can be evaluated. Furthermore, within the radius of convergence, a power series (with real or complex coefficients) defines a complex analytic function. The basic idea is that a formal Laurent series might (depending on how quickly the coefficients die out to zero) represent an analytic function on a part of the complex plane.
If the formal Laurent series only contains non-negative powers of then it is a power series and from complex analysis we know that there exists an , the radius of convergence (which is possibly zero or possibly infinite), such that the sum converges if and the sum diverges if . In particular, is an analytic function on the open disk .
If the formal Laurent series only contains non-positive powers, that is, , then we can consider it to be a power series in and apply the above result. Since , there exists a (possibly zero or possibly infinite) such that is an analytic function on . [From above, the condition would be which is equivalent to hence defining verifies the claim.]
In the general case, a formal Laurent series decomposes as . Both sums must converge if it is to define an analytic function, hence in the general case, a formal Laurent series defines an analytic function on a domain of the form .
The encoding of a sequence as an analytic function is therefore straightforward in principle: given a formal Laurent series , determine the constants and , and provided the region is non-empty, we can use the analytic function to encode the sequence . We must specify the ROC together with whenever we wish to define a sequence in this way; without knowing the ROC, we do not know the domain of definition of , that is, we would not know for what values of does describe the sequence we want. It is possible for a function to describe different sequences depending on the ROC! An example of this is now given.
If then we have seen that . But wait! This is not entirely true. If then certainly .Yet if then . The function for does not describe the series . It looks like a perfectly good function though, so what series does it describe?
The region is unbounded. (In fact, it is an open disc centred at the point at infinity.) This motivates us to replace by so that the domain becomes and we can attempt looking for a power series in . Precisely, . Therefore, the single function actually encodes two different series depending on whether we treat it as a function on or a function on .
Readers remembering their complex analysis will not find this bizarre because a holomorphic (i.e., complex differentiable) function generally requires more than one power series to represent it. A power series about a point is only valid up until a pole is encountered, after which another point must be chosen and a power series around that point used to continue the description of the function. When we change points, the coefficients of the power series will generally change. In the above example, the first series is a power series around the origin while the second series is a power series around the point at infinity and therefore naturally has different coefficients. (Thankfully there are only these two possibilities to worry about: a power series about a different point would look like and is not of the form we described in Step 1. Only when or does the power series match up with the formal Laurent series in Step 1.)
While it might seem that introducing analytic functions is an unnecessary complication, it actually makes certain calculations simpler! Such a phenomenon happened in Step 1: we discovered convolution of sequences became multiplication of Laurent series (and usually multiplication is more convenient than convolution). In Step 3 we will see how the impulse response of can be written down immediately.
Step 3: The Z-transform
Define and . Clearly, the constraint implies a relationship between and , but how can we determine this relationship?
Note that is actually an infinite number of constraints, one for each . The first step is to think of these as a single constraint on the whole sequences and . We can do this either intuitively or rigorously, arriving at the same answer either way.
Intuitively, think of a table (my lack of WordPress skills prevents me from illustrating this nicely). The top row looks like . The next row looks like . The last row looks like . Stack these three rows on top of each other so they line up properly: the purpose of the table is to line everything up correctly! Then another way of expressing is by saying that the first row of the table is equal to the second row of the table plus the third row of the table, where rows are to be added elementwise.
Rigorously, what has just happened is that we are treating a sequence as a vector in an infinite-dimensional vector space: just like is a vector in , we can think of as a vector in . Each of the three rows of the table described above is simply a vector.
To be able to write the table compactly in vector form, we need some way of going from the vector to the shifted-one-place-to-the-right version of it, namely . In linear algebra, we know that a matrix can be used to map one vector to another vector provided the operation is linear, and in fact, shifting a vector is indeed a linear operation. In abstract terms, there exists a linear operator that shifts a sequence one place to the right: .
Letting and denote the vectors and respectively, we can rigorously write our system as . This is precisely the same as what we did when we said the first row of the table is equal to the second row of the table plus the third row of the table.
Our natural instinct is to collect like terms: if denotes the identity operator (think of a matrix with ones on the diagonal), so that , then is equivalent to , that is, . This equation tells us the output as a function of the input — but how useful is it? (Does the inverse exist, and even if it does, how can we evaluate it?)
While in some cases the expression might actually be useful, often it is easier to use series rather than vectors to represent sequences: we will see that the linear operator is equivalent to multiplication by , which is very convenient to work with!
Precisely, since and represent exactly the same sequence, it should be clear that the equation is equivalent to the equation . Indeed, returning to the table, corresponds to the first row, corresponds to the last row, and corresponds to the second row.
Now, from Step 2, we know that we can think of and as analytic functions (provided we are careful about the ROC). Therefore, we feel entitled to continue manipulating to obtain . Since by definition the impulse response satisfies , we seem to have immediately found the impulse response of the original system; at the very least, it agrees with the longer calculation performed at the start of Step 2.
Remark: Actually, the only way to justify rigorously that the above manipulation is valid is to check the answer we have found really is the correct answer. Indeed, to be allowed to perform the manipulations we must assume the existence of a domain on which both and are analytic. If we assume is “nice” then, under that assumption, prove that is “nice”, that does not mean is nice. It is like saying “if it is raining then we can show it really is raining, therefore it must be raining right now!”. A rigorous justification would look something like the following. First we must make some assumption about the input sequence for otherwise we have no idea what ROC to use. If we are interested in inputs that are uniformly bounded and which are zero up until time 0 then we can safely assume that is analytic on . Since is non-zero whenever , we know is analytic on . Therefore will be analytic on . This means that can be expanded as a power series in a neighbourhood of the origin, and the coefficients of that power series are what we believe the output of the system will be. To check this really is the output of the system, it suffices to show for . This is straightforward: as required, where every manipulation can be seen to be valid for (there are no divisions by zero or other bad things occurring).
The remark above shows it is (straightforward but) tedious to verify rigorously that we are allowed to perform the manipulations we want. It is much simpler to go the other way and define a system directly in terms of and its ROC. Then, provided the ROC of overlaps with the ROC of , the output is given by on the overlap, which can be correctly expanded as a Laurent series with regard to the ROC, and the output sequence read off.
All that remains is to introduce the Z-transform and explain why engineers treat as a “time shift operator”.
The Z-transform is simply doing the same as what we have been doing, but using instead of . Why rather than ? Just convention (and perhaps a bit of convenience too, e.g., it leads to stable systems being those with all poles inside the unit circle, rather than outside). In fact, sometimes is used instead of , hence you should always check what conventions an author or lecturer has decided to adopt.
The rule that engineers are taught is that when you “take the Z-transform” of then you replace by , by and by . The reason this rule works was justified at great length above: recall that as an intermediate mental step we can think of the input and output as vectors, and this led to thinking of them instead as series, because multiplication by will then shift the sequence one place to the right. Thus, is asserting that the sequence is equal to the sequence plus a half times the sequence shifted to the right by one place, which is equivalent to the original description .
Step 4: Poles and Zeros
A straightforward but nonetheless rich class of LTI systems can be written in the form . Importantly, this class is “closed” in that if you connect two such systems together (the output of one connects to the input of the other) then the resulting system can again be written in the same way (but generally with larger values of ). Another important feature of this class of systems is that they can be readily implemented in hardware.
Applying the Z-transform to such a system shows that the impulse response in the Z-domain is a rational function. Note that the product of two rational functions is again a rational function, demonstrating that this class of systems is closed under composition, as stated above. Most of the time, it suffices to work with rational impulse responses.
If is rational (and in reduced form — no common factors) then the zeros of are the solutions of the polynomial equation while the poles are the solutions of the polynomial equation . [More generally, if is analytic, then the zeros are the solutions of and the poles are the solutions of .] Note that a pole of is a zero of its inverse: if we invert a system, poles become zeros and zeros become poles.
Poles are important because poles are what determine the regions of convergence and hence they determine when our manipulations in Step 3 are valid. This manifests itself in poles having a physical meaning: as we will see, the closer a pole gets to the unit circle, the less stable a system becomes.
Real-world systems are causal: the output cannot depend on future input. The impulse response of a causal system is zero for . Therefore, the formal Laurent series (Step 1) representation of has no negative powers of . Its region of convergence will therefore be of the form for some . (If then the system would blow up!) Since , the ROC of a causal transfer function will therefore be of the form for some . If is rational then it has only a finite number of poles, and it suffices to choose to be the largest of the magnitudes of the poles.
Let’s look at an unstable system: . This system is clearly unstable because its impulse response is readily seen to be . We put in a bounded signal ( and for ) yet obtain an unbounded output ( for ). Taking the Z-transform gives , so that . For , this gives us the correct series representation .
If we put a signal that starts at time zero (i.e., for ) into a causal system we will get an output even if the system is unstable. This is because the input will have a ROC of the form and has a ROC of the form , so will have a ROC .
If we put a signal that started at time into our system, then there might be no solution! (Intuitively, it means the system will have to have blown up before reaching time 0.) For example, with ROC represents the signal for and for . We cannot form the product because there is no value of for which both and are valid: one’s ROC is while the other’s is .
There are many different definitions of a sequence being bounded. Three examples are: 1) there exists an such that, for all , ; 2) ; and 3) . Out of these three, the easiest to detect whether is bounded given only is the second one: if the ROC of includes then, by definition (see a complex analysis textbook), is absolutely convergent for , meaning , hence because implies for all . This type of boundedness is called “bounded in “. For the reverse direction, recall that the radius of convergence is such that a power series in will converge for all and diverge for all . Therefore, if the boundary of the largest possible ROC of does not contain the unit circle then must be unbounded in . (The boundary case is inconclusive: the power series has a ROC yet is bounded. On the other hand, has a ROC and is unbounded.)
A sequence is bounded in if the largest possible ROC of includes the unit circle . A sequence is unbounded in if the closure of the largest possible ROC does not include the unit circle.
If the ROC of the transfer function includes the unit circle, then an -bounded input will produce an -bounded output. Indeed, the ROC of both and will include the unit circle, therefore, the ROC of will include the unit circle and will be -bounded.
If all the poles of a causal are within the unit circle then the ROC will include the unit circle, hence a bounded input will produce a bounded output. Engineers therefore call a system stable if all the poles of are inside the unit circle.
Note that it follows from earlier remarks that if has a pole outside the unit circle then the impulse response will be unbounded. If has a pole on the unit circle then the impulse response will resonant at the corresponding frequency indefinitely. For example, if where then for . This does not die away because for all . By writing we get and therefore we think of this as a resonance at frequency . Furthermore, if where , then and we see that there is a damped resonance at frequency . As the pole gets closer to the unit circle (that is, ) the impulse response takes longer to die out. Engineers care about pole placement!
- Although often engineers can get away with just following recipes, it is safer in the long run and easier to remember the recipes if you have spent a bit more time to learn the underlying rationale for when and why the rules work.
- Linear algebra and complex analysis are considered core subjects of an undergraduate mathematics degree because they have such broad applicability: here we saw them play integral roles in discrete-time signal processing.
- This is because the “mathematical behaviour” of Laurent series matches the “physical behaviour” of discrete-time linear time-invariant systems.
- There is a close relationship between the Z-transform and the Fourier transform: just make the substitution . This is only allowed if the ROC contains the unit circle. The concept of a pole does not explicitly appear in the Fourier domain because, rather than permit to be anywhere in the complex plane, the substitution means we are only looking at the behaviour of on the unit circle.
- When it comes to system design, understanding where the poles and zeros are can be more productive than trying to understand the whole frequency spectrum.