Chapter 3

Analyzing Discrete-Time Systems in the Time Domain

Chapter Objectives

• Develop the notion of a discrete-time system.
• Learn simplifying assumptions made in the analysis of discrete-time systems. Discuss the concepts of linearity and time invariance, and their significance.
• Explore the use of difference equations for representing discrete-time systems.
• Develop methods for solving difference equations to compute the output signal of a system in response to a specified input signal.
• Learn to represent a difference equation in the form of a block diagram that can be used as the basis for simulating or realizing a system.
• Discuss the significance of the impulse response as an alternative description form for linear and time-invariant systems.
• Learn how to compute the output signal for a linear and time-invariant system using convolution. Understand the graphical interpretation of the steps involved in carrying out the convolution operation.
• Learn the concepts of causality and stability as they relate to physically realizable and usable systems.

3.1 Introduction

The definition of a discrete-time system is similar to that of its continuous-time counterpart:

Signal-system interaction involving a single-input single-output discrete-time system is illustrated in Fig. 3.1.

The input-output relationship of a discrete-time system may be expressed in the form

$$\begin{array}{ccc}y\left[n\right]=\text{Sys}\left\{x\left[n\right]\right\}& & \left(3.1\right)\end{array}$$

where Sys{...} represents the transformation that defines the system in the time domain. A very simple example is a system that simply multiplies its input signal by a constant gain factor K

$$\begin{array}{ccc}y\left[n\right]=Kx\left[n\right]& & \left(3.2\right)\end{array}$$

or a system that delays its input signal by m samples

$$\begin{array}{ccc}y\left[n\right]=x\left[n-m\right]& & \left(3.3\right)\end{array}$$

or one that produces an output signal proportional to the square of the input signal

$$\begin{array}{ccc}y\left[n\right]=K{\left[x\left[n\right]\right]}^2& & \left(3.4\right)\end{array}$$

A system with higher complexity can be defined using a difference equation that establishes the relationship between input and output signals.

Two commonly used simplifying assumptions used in studying mathematical models of systems, namely linearity and time invariance, will be the subject of Section 3.2. Section 3.3 deals with the issue of deriving a difference equation model for a discrete-time system, and Section 3.4 discusses the characteristics of constant-coefficient linear difference equations. Solution methods for constant-coefficient linear difference equations are presented in Section 3.5. Block diagrams for realizing discrete-time systems are introduced in Section 3.6. In Section 3.7 we discuss the significance of the impulse response for discrete-time systems, and its use in the context of the convolution operator for determining the output signal. Concepts of causality and stability of systems are discussed in Sections 3.8 and 3.9 respectively.

3.2 Linearity and Time Invariance

In our discussion of continuous-time systems in Chapter 2 we have relied heavily on the simplifying assumptions of linearity and time invariance. We have seen that these two assumptions allow a robust set of analysis methods to be developed. The same is true for the analysis of discrete-time systems.

3.2.1 Linearity in discrete-time systems

Linearity property will be very important as we analyze and design discrete-time systems. Conditions for linearity of a discrete-time system are:

Eqns. (3.5) and (3.6), referred to as the additivity rule and the homogeneity rule respectively, must be satisfied for any two discrete-time signals x1[n] and x2[n] as well as any arbitrary constant α1. These two criteria can be combined into one equation known as the superposition principle.

Verbally expressed, Eqn. (3.7) implies that the response of the system to a weighted sum of any two input signals is equal to the same weighted sum of the individual responses of the system to each of the two input signals. Fig. 3.2 illustrates this concept.

A generalization of the principle of superposition for the weighted sum of N discrete-time signals is expressed as

$$\begin{array}{ccc}\text{Sys}\left\{{\displaystyle \sum _{i=1}^N}{\alpha }_i{x}_i\left[n\right]\right\}={\displaystyle \sum _{i=1}^N}{\alpha }_i\text{ Sys}\left\{x_i\left[n\right]\right\}& & \left(3.8\right)\end{array}$$

The response of a linear system to a weighted sum of N arbitrary signals is equal to the same weighted sum of individual responses of the system to each of the N signals. Let yi[n] be the response to the input term xi[n] alone, that is yi[n] = Sys {xi[n]} for i = 1,...,N.

Superposition principle implies that

$$\begin{array}{ccc}y\left[n\right]=\text{Sys}\left\{{\displaystyle \sum _{i=1}^N}{\alpha }_i{x}_i\left[n\right]\right\}={\displaystyle \sum _{i=1}^N}{\alpha }_i{y}_i\left[n\right]& & \left(3.9\right)\end{array}$$

This is illustrated in Fig. 3.3.

Example 3.1: Testing linearity in discrete-time systems

For each of the discrete-time systems described below, determine whether the system is linear or not:

1. y[n] = 3x[n] + 2x[n − 1]
2. y[n] = 3x [n] + 2x [n + 1] x[n − 1]
3. y[n] = a−n x[n]

Solution:

1. In order to test the linearity of the system we will think of its responses to the two discrete-time signals x1[n] and x2[n] as

   $$y_1\left[n\right]=\text{Sys}\left\{x_1\left[n\right]\right\}=3x_1\left[n\right]+2x_1\left[n-1\right]$$

   and

   $$y_2\left[n\right]=\text{Sys}\left\{x_2\left[n\right]\right\}=3x_2\left[n\right]+2x_2\left[n-1\right]$$

   The response of the system to the linear combination signal x[n] = α1x1[n] + α2x2[n] is computed as

   $$\begin{array}{ll}y\left[n\right]\hfill & =\text{Sys}\{{\alpha }_1{x}_1[n]+{\alpha }_2{x}_2[n]\}\hfill \\ \hfill & =3({\alpha }_1{x}_1[n]+{\alpha }_2{x}_2[n])+2({\alpha }_1{x}_1[n-1]+{\alpha }_2{x}_2[n-1])\hfill \\ \hfill & ={\alpha }_1(3x_1[n]+2x_1[n-1])+{\alpha }_2(3x_2[n]+2x_2[n-1])\hfill \\ \hfill & ={\alpha }_1 y_1[n]+{\alpha }_2 y_2[n]\hfill \end{array}$$

   Superposition principle holds, and therefore the system in question is linear.

2. Again using the test signals x1[n] and x2[n] we have

   $$y_{1}n=\text{Sys}\left\{x_1\left[n\right]\right\}=3x_1\left[n\right]+2x_1\left[n+1\right]x_1\left[n-1\right]$$

   and

   $$y_{2}n=\text{Sys}\left\{x_2\left[n\right]\right\}=3x_2\left[n\right]+2x_2\left[n+1\right]x_2\left[n-1\right]$$

   Use of the linear combination signal x[n] = α1x1[n] + α2x2[n] as input to the system yields the output signal

   $$\begin{array}{ll}y[n]\hfill & =\text{Sys}\{{\alpha }_1{x}_1[n]+{\alpha }_2{x}_2[n]\}\hfill \\ \hfill & =3({\alpha }_1{x}_1[n]+{\alpha }_2{x}_2[n])\hfill \\ \hfill & +2({\alpha }_1{x}_1[n+1]+{\alpha }_2{x}_2[n+1])({\alpha }_1{x}_1[n-1]+{\alpha }_2{x}_2[n-1])\hfill \end{array}$$

   In this case the superposition principle does not hold true. The system in part (b) is therefore not linear.

3. The responses of the system to the two test signals are

   $$y_1\left[n\right]=\text{Sys}\left\{x_1\left[n\right]\right\}=a^{-n}{x}_1\left[n\right]$$

   and

   $$y_2\left[n\right]=\text{Sys}\left\{x_2\left[n\right]\right\}=a^{-n}{x}_2\left[n\right]$$

   and the response to the linear combination signal x[n] = α1x1[n] + α2x2[n] is

   $$\begin{array}{ll}y[n]\hfill & =\text{Sys}\{{\alpha }_1{x}_1[n]+{\alpha }_2{x}_2[n]\}\hfill \\ \hfill & =a^{-n}({\alpha }_1{x}_1[n]+{\alpha }_2{x}_2[n])\hfill \\ \hfill & ={\alpha }_1 a^{-n}{x}_1[n]+{\alpha }_2 a^{-n}{x}_2[n]\hfill \\ \hfill & ={\alpha }_1 y_1[n]+{\alpha }_2{y}_2[n]\hfill \end{array}$$

   The system is linear.

3.2.2 Time invariance in discrete-time systems

The definition of the time invariant property for a discrete-time system is similar to that of a continuous-time system. Let a discrete-time system be described with the input-output relationship y[n] = Sys{x[n]}. For the system to be considered time-invariant,the only effect of time-shifting the input signal should be to cause an equal amount of time shift in the output signal.

This relationship is depicted in Fig. 3.4.

Alternatively, the time-invariant nature of a system can be characterized by the equivalence of the two configurations shown in Fig. 3.5.

Example 3.2: Testing time invariance in discrete-time systems

For each of the discrete-time systems described below, determine whether the system is time-invariant or not:

1. y[n] = y[n − 1] + 3x[n]
2. y[n] = x[n]y[n − 1]
3. y[n] = nx [n − 1]

Solution:

1. We will test the time-invariance property of the system by time-shifting both the input and the output signals by the same number of samples, and see if the input–output relationship still holds. Replacing the index n by n − k in the arguments of all input and output terms we obtain

   $$\text{Sys}\left\{x\left[n-k\right]\right\}=y\left[n-k-1\right]+3x\left[n-k\right]=y\left[n-k\right]$$

   The input–output relationship holds, therefore the system is time-invariant.

2. Proceeding in a similar fashion we have

   $$\text{Sys}\left\{x\left[n-k\right]\right\}=x\left[n-k\right]y\left[n-k-1\right]=y\left[n-k\right]$$

   This system is time-invariant as well.

3. Replacing the index n by n − k in the arguments of all input and output terms yields

   $$\text{Sys}\left\{x\left[n-k\right]\right\}=nx\left[n-k-1\right]\ne y\left[n-k\right]$$

   This system is clearly not time-invariant since the input–output relationship no longer holds after input and output signals are time-shifted.

   Should we have included the factor n in the time shifting operation when we wrote the response of the system to a time-shifted input signal? In other words, should we have written the response as

   $$\text{Sys}\left\{x\left[n-k\right]\right\}\stackrel{?}{=}\left(n-x\right)x\left[n-k-1\right]$$

   The answer is no. The factor n that multiplies the input signal is part of the system definition and not part of either the input or the output signal. Therefore we cannot include it in the process of time-shifting input and output signals.

3.2.3 DTLTI systems

Discrete-time systems that are both linear and time-invariant will play an important role in the rest of this textbook. We will develop time- and frequency-domain analysis and design techniques for working with such systems. To simplify the terminology, we will use the acronym DTLTI to refer to discrete-time linear and time-invariant systems.

3.3 Difference Equations for Discrete-Time Systems

In Section 2.3 we have discussed methods of representing continuous-time systems with differential equations. Using a similar approach, discrete-time systems can be modeled with difference equations involving current, past, or future samples of input and output signals. We will begin our study of discrete-time system models based on difference equations with a few examples. Each example will start with a verbal description of a system and lead to a system model in the form of a difference equation. Some of the examples will lead to systems that will be of fundamental importance in the rest of this text while other examples lead to nonlinear or time-varying systems that we will not consider further. In the sections that follow we will focus our attention on difference equations for DTLTI systems, and develop solution techniques for them using an approach that parallels our study of differential equations for CTLTI systems.

Example 3.3: Moving-average filter

A length-N moving average filter is a simple system that produces an output equal to the arithmetic average of the most recent N samples of the input signal. Let the discrete-time output signal be y[n]. If the current sample index is 100, the current output sample y[100] would be equal to the arithmetic average of the current input sample x[100] and (N − 1) previous input samples. Mathematically we have

$$\begin{array}{ll}y[100]\hfill & =\frac{x[100]+x[99]+...+x[100-(N-1)]}{N}\hfill \\ \hfill & =\frac{1}{N}{\displaystyle \sum }_{k=0}^{N-1}x[100-k]\hfill \end{array}$$

The general expression for the length-N moving average filter is obtained by expressing the n-th sample of the output signal in terms of the relevant samples of the input signal as

$$\begin{array}{ccc}\begin{array}{ll}y[n]\hfill & =\frac{x[n]+x[n-1]+...+x[n-(N-1)]}{N}\hfill \\ \hfill & =\frac{1}{N}{\displaystyle \sum }_{k=0}^{N-1}x[n-k]\hfill \end{array}& & (3.11)\end{array}$$

Eqn. (3.11) is a difference equation describing the input-output relationship of the moving average filter as a discrete-time system. The operation of the length-N moving average filter is best explained using the analogy of a window, as illustrated in Fig. 3.6.

Suppose that we are observing the input signal through a window that is wide enough to hold N samples of the input signal at any given time. Let the window be stationary, and let the input signal x[n] move to the left one sample at a time, similar to a film strip. The current sample of the input signal is always the rightmost sample visible through the window. The current output sample is the arithmetic average of the input samples visible through the window.

Moving average filters are used in practical applications to smooth the variations in a signal. One example is in analyzing the changes in a financial index such as the Dow Jones Industrial Average. An investor might use a moving average filter on a signal that contains the values of the index for each day. A 50-day or a 100-day moving average window may be used for producing an output signal that disregards the day-to-day fluctuations of the input signal and focuses on the slowly varying trends instead. The degree of smoothing is dependent on N, the size of the window. In general, a 100-day moving average is smoother than a 50-day moving average.

Let x[n] be the signal that holds the daily closing values of the index for the calendar year 2003. The 50-day moving averages are computed by

$$y_1\left[n\right]=\frac{1}{50}{\displaystyle \sum _{k=0}^{49}}x\left[n-k\right]$$

and 100-day moving averages are computed by

$$y_2\left[n\right]=\frac{1}{100}{\displaystyle \sum _{k=0}^{99}}x\left[n-k\right]$$

Fig. 3.7 shows the daily values of the index for the calendar year 2003 as a discrete-time signal as well as the outputs produced by 50-day and 100-day moving average filters. Note that, in the computation of the output signal samples y1[0],...,y1[48] as well as the output signal samples y2[0],...,y2[98], the averaging window had to be supplied with values from 2002 data for the index. For example, to compute the 50-day moving average on January 1 of 2003, previous 49 samples of the data from December and part of November of 2002 had to be used.

We will develop better insight for the type of smoothing achieved by moving average filters when we discuss frequency domain analysis methods for discrete-time systems.

Example 3.4: Length-2 moving-average filter

A length-2 moving average filter produces an output by averaging the current input sample and the previous input sample. This action translates to a difference equation in the form

$$\begin{array}{ccc}y\left[n\right]=\frac{1}{2}x\left[n\right]+\frac{1}{2}x\left[n-1\right]& & \left(3.12\right)\end{array}$$

and is illustrated in Fig. 3.8. The window through which we look at the input signal accommodates two samples at any given time, and the current input sample is close to the right edge of the window. As in the previous example, we will assume that the window is stationary, and the system structure shown is also stationary. We will imagine the input signal moving to the left one sample at a time like a film strip. The output signal in the lower part of the figure also acts like a film strip and moves to the left one sample at a time, in sync with the input signal. If we wanted to write the input-output relationship of the length-2 moving average filter for several values of the index n,we would have

$$\begin{array}{ll}n=0:\hfill & y[0]=\frac{1}{2}x[0]+\frac{1}{2}x[n-1]\hfill \\ n=1:\hfill & y[1]=\frac{1}{2}x[1]+\frac{1}{2}x[0]\hfill \\ n=2:\hfill & y[2]=\frac{1}{2}x[2]+\frac{1}{2}x[1]\hfill \end{array}$$

and so on.

Example 3.5: Length-4 moving average filter

A length-4 moving average filter produces an output by averaging the current input sample and the previous three input samples. This action translates to a difference equation in the form

$$\begin{array}{ccc}y\left[n\right]=\frac{1}{4}x\left[n\right]+\frac{1}{4}x\left[n-1\right]+\frac{1}{4}x\left[n-2\right]+\frac{1}{4}x\left[n-3\right]& & \left(3.13\right)\end{array}$$

and is illustrated in Fig. 3.9.

For a few values of the index we can write the following set of equations:

$$\begin{array}{ll}n=0:\hfill & y[0]=\frac{1}{4}x[0]+\frac{1}{4}x[-1]+\frac{1}{4}x[-2]+\frac{1}{4}x[-3]\hfill \\ n=1:\hfill & y[1]=\frac{1}{4}x[1]+\frac{1}{4}x[0]+\frac{1}{4}x[-1]+\frac{1}{4}x[-2]\hfill \\ n=2:\hfill & y[2]=\frac{1}{4}x[2]+\frac{1}{4}x[1]+\frac{1}{4}x[0]+\frac{1}{4}x[-1]\hfill \end{array}$$

Example 3.6: Exponential smoother

Another method of smoothing a discrete-time signal is through the use of an exponential smoother which employs a difference equation with feedback. The current output sample is computed as a mix of the current input sample and the previous output sample through the equation

$$\begin{array}{ccc}y\left[n\right]=\left(1-\alpha \right)y\left[n-1\right]+\alpha x\left[n\right]& & \left(3.14\right)\end{array}$$

The parameter α is a constant in the range 0 < α < 1, and it controls the degree of smoothing. According to Eqn. (3.14), the current output sample y[n] has two contributors, namely the current input sample x[n] and the previous output sample y[n − 1]. The contribution of the current input sample is proportional to α, and the contribution of the previous output sample is proportional to 1 − α. Smaller values of α lead to smaller contributions from each input sample, and therefore a smoother output signal. Writing the difference equation given by Eqn. (3.14) for several values of the sample index n we obtain

$$\begin{array}{cc}n=0:\hfill & y\left[0\right]=\left(1-\alpha \right)y\left[-1\right]+\alpha x\left[0\right]\hfill \\ n=1:\hfill & y\left[1\right]=\left(1-\alpha \right)y\left[0\right]+\alpha x\left[1\right]\hfill \\ n=2:\hfill & y\left[2\right]=\left(1-\alpha \right)y\left[1\right]+\alpha x\left[2\right]\hfill \end{array}$$

and so on. Since the difference equation in Eqn. (3.14) is linear with constant coefficients, the exponential smoother would be an example of a DTLTI system provided that it is initially relaxed which, in this case, implies that y[−1] = 0. Fig. 3.10 illustrates the application of the linear exponential smoother to the 2003 Dow Jones Industrial Average data for α = 0.1 and α = 0.2.

Example 3.7: Loan payments

A practical everyday use of a difference equation can be found in banking: borrowing money for the purchase of a house or a car. The scenario is familiar to all of us. We borrow the amount that we need to purchase that dream house or dream car, and then pay back a fixed amount for each of a number of periods, often measured in terms of months. At the end of each month the bank will compute our new balance by taking the balance of the previous month, increasing it by the monthly interest rate, and subtracting the payment we made for that month. Let y[n] represent the amount we owe at the end of the n-th month, and let x[n] represent the payment we make in month n. If c is the monthly interest rate expressed as a fraction (for example, 0.01 for a 1 percent monthly interest rate), then the loan balance may be modeled as the output signal of a system with the following difference equation as shown in Fig. 3.11:

$$\begin{array}{ccc}y\left[n\right]=\left(1+c\right)y\left[n-1\right]-x\left[n\right]& & \left(3.15\right)\end{array}$$

Expressing the input-output relationship of the system through a difference equation allows us to analyze it in a number of ways. Let A represent the initial amount borrowed in month n = 0, and let the monthly payment be equal to B for months n = 1, 2,.... One method of finding y[n] would be to solve the difference equation in Eqn. (3.15) with the input signal

$$\begin{array}{ccc}x\left[n\right]=Bu\left[n-1\right]& & \left(3.16\right)\end{array}$$

and the initial condition y[0] = A. Alternatively we can treat the borrowed amount as a negative payment in month 0, and solve the difference equation with the input signal

$$\begin{array}{ccc}x\left[n\right]=-A\delta \left[n\right]+Bu\left[n-1\right]& & \left(3.17\right)\end{array}$$

and the initial condition y[−1] = 0.

In later parts of this text, as we develop the tools we need for analysis of systems, we will revisit this example. After we learn the techniques for solving linear constant-coefficient difference equations, we will be able to find the output of this system in response to an input given by Eqn. (3.17).

Example 3.8: A nonlinear dynamics example

An interesting example of the use of difference equations is seen in chaos theory and its applications to nonlinear dynamic systems. Let the output y[n] of the system represent the population of a particular kind of species in a particular environment, for example, a certain type of plant in the rain forest. The value y[n] is normalized to be in the range 0 < y[n] < 1 with the value 1 corresponding to the maximum capacity for the species which may depend on the availability of resources such as food, water, direct sunlight, etc. In the logistic growth model, the population growth rate is assumed to be proportional to the remaining capacity 1 − y[n], and population change from one generation to the next is given by

$$\begin{array}{ccc}y\left[n\right]=r\left(1-y\left[n-1\right]\right)+y\left[n-1\right]& & \left(3.18\right)\end{array}$$

where r is a constant. This is an example of a nonlinear system that does not have an input signal. Instead, it produces an output signal based on its initial state.

Software resources:

ex_3_8.m

Example 3.9: Newton-Raphson method for finding a root of a function

In numerical analysis, one of the simplest methods for finding the real roots of a well-behaved function is the Newton-Raphson technique. Consider a function u = f (w)shown in Fig. 3.12. Our goal is to find the value of w for which u = f (w) = 0

Starting with an initial guess w = w0 for the solution, we draw the line that is tangent to the function at that point, as shown in Fig. 3.12. The value w = w1 where the tangent line intersects the real axis is our next, improved, guess for the root. The slope of the tangent line is f′(w0), and it passes through the point (w0, f (w0)). Therefore, the equation of the tangent line is

$$\begin{array}{ccc}u-f\left(w_0\right)=f^{\prime }\left(w_0\right)\left(w-w_0\right)& & \left(3.19\right)\end{array}$$

At the point where the tangent line intersects the horizontal axis we have u = 0 and w = w1. Substituting these values into Eqn. (3.19) we have

$$\begin{array}{ccc}-f\left(w_0\right)=f^{\prime }\left(w_0\right)\left(w_1-w_0\right)& & \left(3.20\right)\end{array}$$

and solving for w1 results in

$$\begin{array}{ccc}{w}_1=w_0-\frac{f\left(w_0\right)}{f^{\prime }\left(w_0\right)}& & \left(3.21\right)\end{array}$$

Thus, from an initial guess w0 for the solution, we find a better guess w1 through the use of Eqn. (3.21). Repeating this process, an even closer guess can be found as

$$\begin{array}{ccc}{w}_2=w_1-\frac{f\left(w_1\right)}{f^{\prime }\left(w_1\right)}& & \left(3.22\right)\end{array}$$

and so on. The technique can be modeled as a discrete-time system. Let the output signal y[n] represent successive guesses for the root, that is, y[n] = wn. The next successive guess can be obtained from the previous one through the difference equation

$$\begin{array}{ccc}y\left[n\right]=y\left[n-1\right]-\frac{f\left(y\left[n-1\right]\right)}{f^{\prime }\left(y\left[n-1\right]\right)}& & \left(3.23\right)\end{array}$$

As an example of converting this procedure to a discrete-time system, let the function be

$$u=f\left(w\right)=w^2-A$$

where A is any positive real number. We can write

$$\begin{array}{ccccc}{f}^{\prime }\left(w\right)=2w,& \text{and}& \frac{f\left(w\right)}{f^{\prime }\left(w\right)}=\frac{w}{2}-\frac{A}{2w}& & \left(3.24\right)\end{array}$$

The difference equation in Eqn. (3.23) becomes

$$\begin{array}{ccc}\begin{array}{ll}y[n]\hfill & =y[n-1]-\frac{y[n-]}{2}+\frac{A}{2y[n-1]}\hfill \\ \hfill & =\frac{1}{2}\left(y[n-1]+\frac{A}{y[n-1]}\right)\hfill \end{array}& & (3.25)\end{array}$$

Obviously Eqn. (3.25) represents a nonlinear difference equation. Let us use this system to iteratively find the square root of 10 which we know is $\sqrt{10}=3.162278$. The function the root of which we are seeking is f (w) = w 2 − 10. Starting with an initial guess of y[0] = 1 we have

$$y\left[1\right]=\frac{1}{2}\left(y\left[0\right]+\frac{10}{y\left[0\right]}\right)=\frac{1}{2}\left(1+\frac{10}{1}\right)=5.5$$

The next iteration produces

$$y\left[2\right]=\frac{1}{2}\left(y\left[1\right]+\frac{10}{y\left[1\right]}\right)=\frac{1}{2}\left(5.5+\frac{10}{5.5}\right)=3.659091$$

Continuing in this fashion we obtain y[3] = 3.196005, y[4] = 3.162456, and y[5] = 3.162278 which is accurate as the square root of 10 up to the sixth decimal digit.

Software resources:

ex_3_9.m

3.4 Constant-Coefficient Linear Difference Equations

DTLTI systems can be modeled with constant-coefficient linear difference equations. A linear difference equation is one in which current, past and perhaps even future samples of the input and the output signals can appear as linear terms. Furthermore, a constant coefficient linear difference equation is one in which the linear terms involving input and output signals appear with coefficients that are constant, independent of time or any other variable.

The moving-average filters we have explored in Examples 3.3, 3.4 and 3.5 were described by constant-coefficient linear difference equations:

$$\begin{array}{ll}\text{Length-}2:\hfill & y\left[n\right]=\frac{1}{2}x\left[n\right]+\frac{1}{2}x\left[n-1\right]\hfill \\ \text{Length-}4:\hfill & y\left[n\right]=\frac{1}{4}x\left[n\right]+\frac{1}{4}x\left[n-1\right]+\frac{1}{4}x\left[n-2\right]+\frac{1}{4}x\left[n-3\right]\hfill \\ \text{Length-}10:\hfill & y\left[n\right]=\frac{1}{10}{\displaystyle \sum _{k=0}^9}x\left[n-k\right]\hfill \end{array}$$

A common characteristic of these three difference equations is that past or future samples of the output signal do not appear on the right side of any of them. In each of the three difference equations the output y[n] is computed as a function of current and past samples of the input signal. In contrast, reconsider the difference equation for the exponential smoother

$$y\left[n\right]=\left(1-\alpha \right)y\left[n-1\right]+\alpha x\left[n\right]$$

or the difference equation for the system that computes the current balance of a loan

$$y\left[n\right]=\left(1+c\right)y\left[n-1\right]-x\left[n\right]$$

Both of these systems also have constant-coefficient linear difference equations (we assume that parameters α and c are constants). What sets the last two systems apart from the three moving average filters above is that they also have feedback in the form of past samples of the output appearing on the right side of the difference equation. The value of y[n] depends on the past output sample y[n − 1].

Examples 3.8 and 3.9, namely the logistic growth model and the Newton-Raphson algorithm for finding a square root, utilized the difference equations

$$y\left[n\right]=r\left(1-y\left[n-1\right]\right)y\left[n-1\right]$$

and

$$y\left[n\right]=\frac{1}{2}\left(y\left[n-1\right]+\frac{A}{y\left[n-1\right]}\right)$$

Both of these difference equations are nonlinear since they contain nonlinear terms of y[n−1].

A general constant-coefficient linear difference equation representing a DTLTI system is in the form

$$\begin{array}{ccc}\begin{array}{l}{a}_{0}y\left[n\right]+a_{1}y\left[n-1\right]+...+a_{N-1}y\left[n-N+1\right]+a_{N}y\left[n-N\right]=\\ b_{0}b\left[n\right]+b_{1}x\left[n-1\right]...+b_{M-1}x\left[n-M+1\right]+b_{M}x\left[n-M\right]\end{array}& & \left(3.26\right)\end{array}$$

or in closed summation form as shown below.

The order of the difference equation (and therefore the order of the system it represents) is the larger of N and M. For example, the length-2 moving average filter discussed in Example 3.4 is a first-order system. Similarly, the orders of the length-4 and the length-10 moving average filters of Examples 3.5 and 3.3 are 3 and 9 respectively.

A note of clarification is in order here: The general form we have used in Eqns. (3.26) and (3.27) includes current and past samples of x[n] and y[n] but no future samples. This is for practical purposes only. The inclusion of future samples in a difference equation for the computation of the current output would not affect the linearity and the time invariance of the system represented by that difference equation, as long as the future samples also appear as linear terms and with constant coefficients. For example, the difference equation

$$\begin{array}{ccc}y\left[n\right]=y\left[n-1\right]+x\left[n+2\right]-3x\left[n+1\right]+2x\left[n\right]& & \left(3.28\right)\end{array}$$

is still a constant-coefficient linear difference equation, and it may still correspond to a DTLTI system. We just have an additional challenge in computing the output signal through the use of this difference equation: We need to know future values of the input signal. For example, computation of y[45] requires the knowledge of x[46] and x[47] in addition to other terms. We will explore this further when we discuss the causality property later in this chapter.

Example 3.10: Checking linearity and time-invariance of a difference equation

Determine whether the first-order constant-coefficient linear difference equation in the form

$$a_{0}y\left[n\right]+a_{1}y\left[n-1\right]=b_{0}x\left[n\right]$$

represents a DTLTI system.

Solution: Our approach will be similar to that employed in Example 2.7 of Chapter 2 for a continuous-time system. Assume that two input signals x1[n] and x2[n] produce the corresponding output signals y1[n] and y2[n] respectively. Each of the signal pairs x1[n] ↔ y1[n] and x2[n] ↔ y2[n] must satisfy the difference equation, so we have

$$\begin{array}{ccc}{a}_0{y}_1\left[n\right]+a_1{y}_1\left[n-1\right]=b_0{x}_1\left[n\right]& & \left(3.29\right)\end{array}$$

and

$$\begin{array}{ccc}{a}_0{y}_2\left[n\right]+a_1{y}_2\left[n-1\right]=b_0{x}_2\left[n\right]& & \left(3.30\right)\end{array}$$

Let a new input signal be constructed as a linear combination of x1[n] and x2[n] as

$$\begin{array}{ccc}{x}_3\left[n\right]+{\alpha }_1{x}_1\left[n\right]+{\alpha }_2{x}_2\left[n\right]& & \left(3.31\right)\end{array}$$

For the system described by the difference equation to be linear, its response to the input signal x3[n] must be

$$\begin{array}{ccc}{y}_3\left[n\right]+{\alpha }_1{y}_1\left[n\right]+{\alpha }_2{x}_2\left[n\right]& & \left(3.32\right)\end{array}$$

and the input-output signal pair x3[n] ↔ y3[n] must also satisfy the difference equation. Substituting y3[n] into the left side of the difference equation yields

$$\begin{array}{ccc}{a}_0{y}_3\left[n\right]+{\alpha }_1{y}_3\left[n-1\right]=a_0\left({\alpha }_1{y}_1\left[n\right]+{\alpha }_2{y}_2\left[n\right]\right)+a_1\left({\alpha }_1{y}_1\left[n-1\right]+{\alpha }_2{y}_2\left[n-1\right]\right)& & \left(3.33\right)\end{array}$$

By rearranging the terms on the right side of Eqn. (3.33) we get

$$\begin{array}{ccc}{a}_0{y}_3[n]+{\alpha }_1{y}_3[n-1]={\alpha }_0(a_0 y_1[n]+a_1 y_1[n-1])+{\alpha }_2(a_0 y_2[n]+(a_1 y_2[n-1])& & (3.34)\end{array}$$

Substituting Eqns. (3.29) and (3.30) into Eqn. (3.34) leads to

$$\begin{array}{ccc}\begin{array}{ll}{a}_0{y}_3[n]+a_1{y}_3[n-1]\hfill & ={\alpha }_1 (b_0{x}_1[n])+{\alpha }_2 (b_0{x}_2[n])\hfill \\ \hfill & =b_0 ({\alpha }_1{x}_1[n]+{\alpha }_2{x}_2[n])\hfill \\ \hfill & =b_0{x}_3[n]\hfill \end{array}& & \left(3.35\right)\end{array}$$

proving that the input-output signal pair x3[n] ↔ y3[n] satisfies the difference equation.

Before we can claim that the difference equation in question represents a linear system, we need to check the initial value of y[n]. We know from previous discussion that a difference equation like the one given by Eqn. (3.29) can be solved iteratively starting at a specified value of the index n = n0 provided that the value of the output sample at index n = n0 − 1 is known. For example, let n0 = 0, and let y[n0 − 1] = y[−1] = A. Starting with the specified value of y[−1] we can determine y[0] as

$$y\left[0\right]=\left(\frac{a_1}{a_0}\right)A+b_0{x}_0$$

Having determined the value of y[0] we can find y[1] as

$$\begin{array}{ll}y[1]\hfill & =(-\frac{a_1}{a_0})y[0]+b_0{x}_1\hfill \\ \hfill & =(-\frac{a_1}{a_0})[(-\frac{a_1}{a_0})A+b_0{x}_0]+b_0{x}_1\hfill \end{array}$$

and continue in this fashion. Clearly the result obtained is dependent on the initial value y[−1] = A. Since the y1[n], y2[n] and y3[n] used in the development above are all solutions of the difference equation for input signals x1[n], x2[n] and x3[n] respectively, they must each satisfy the specified initial condition, that is,

$$\begin{array}{ccc}{y}_1\left[-1\right]=A,& y_2\left[-1\right]=A,& y_3\left[-1\right]=A\end{array}$$

In addition, the linearity condition in Eqn. (3.32) must be satisfied for all values of the index n including n = − 1:

$$y_3\left[-1\right]={\alpha }_1{y}_1\left[-1\right]+{\alpha }_2{y}_2\left[-1\right]$$

Thus we are compelled to conclude that the system represented by Eqn. (3.29) is linear only if y[−1] = 0. In the general case, we need y[n0− 1] = 0 if the solution is to start at index n = n0.

Our next task is to check the time-invariance property of the system described by the difference equation. If we replace the index n with n − m, Eqn. (3.29) becomes

$$\begin{array}{ccc}{a}_{0}y\left[n-m\right]+a_{1}y\left[n-m-1\right]=b_{0}x\left[n-m\right]& & \left(3.36\right)\end{array}$$

Delaying the input signal x[n] by m samples causes the output signal y[n] to be delayed by the same amount. The system is time-invariant.

In Example 3.10 we have verified that the first-order constant-coefficient linear difference equation corresponds to a DTLTI system provided that its initial state is zero. We are now ready to generalize that result to the constant-coefficient linear difference equation of any order. Let the two input signals x1[n] and x2[n] produce the output signals y1[n] and y2[n] respectively. The input-output signal pairs x1[n] ↔ y1[n] and x2[n] ↔ y2[n] satisfy the difference equation, so we can write

$$\begin{array}{ccc}{\displaystyle \sum _{k=0}^N}{a}_k{y}_1\left[n-k\right]={\displaystyle \sum _{k=0}^M}{b}_k{x}_1\left[n-k\right]& & \left(3.37\right)\end{array}$$

and

$$\begin{array}{ccc}{\displaystyle \sum _{k=0}^N}{a}_k{y}_2\left[n-k\right]={\displaystyle \sum _{k=0}^M}{b}_k{x}_2\left[n-k\right]& & \left(3.38\right)\end{array}$$

To test linearity of the system we will construct a new input signal as a linear combination of x1[n] and x2[n]:

$$\begin{array}{ccc}{x}_3\left[n\right]={\alpha }_1{x}_1\left[n\right]+{\alpha }_2{x}_2\left[n\right]& & \left(3.39\right)\end{array}$$

If the system described by the difference equation is linear, its response to the input signal x3[n] must be

$$\begin{array}{ccc}{y}_3\left[n\right]={\alpha }_1{y}_1\left[n\right]+{\alpha }_2{y}_2\left[n\right]& & \left(3.40\right)\end{array}$$

We will test the input-output signal pair x3[n] ↔ y3[n] through the difference equation. Substituting y3[n] into the left side of the difference equation yields

$$\begin{array}{ccc}{\displaystyle \sum _{k=0}^N}{a}_k{y}_3\left[n-k\right]={\displaystyle \sum _{k=0}^N}{a}_k\left({\alpha }_1{y}_1\left[n-k\right]+{\alpha }_2{y}_2\left[n-k\right]\right)& & \left(3.41\right)\end{array}$$

Rearranging the terms on the right side of Eqn. (3.41) and separating them into two separate summations yields

$$\begin{array}{ccc}{\displaystyle \sum _{k=0}^N}{a}_k{y}_3\left[n-k\right]={\alpha }_1{\displaystyle \sum _{k=0}^N}{a}_k{y}_1\left[n-k\right]+{\alpha }_2{\displaystyle \sum _{k=0}^N}{a}_k{y}_2\left[n-k\right]& & \left(3.42\right)\end{array}$$

The two summations on the right side of Eqn. (3.42) can be substituted with their equivalents from Eqns. (3.37) and (3.38), resulting in

$$\begin{array}{ccc}{\displaystyle \sum _{k=0}^N}{a}_k{y}_3\left[n-k\right]={\alpha }_1{\displaystyle \sum _{k=0}^N}{b}_k{x}_1\left[n-k\right]+{\alpha }_2{\displaystyle \sum _{k=0}^N}{b}_k{x}_2\left[n-k\right]& & \left(3.43\right)\end{array}$$

Finally, we will combine the two summations on the right side of Eqn. (3.43) back into one summation to obtain

$$\begin{array}{ccc}\begin{array}{c}{\displaystyle \sum _{k=0}^N}{a}_k{y}_3\left[n-k\right]={\displaystyle \sum _{k=0}^N}{b}_k\left({\alpha }_1{x}_1\left[n-k\right]+{\alpha }_2{x}_2\left[n-k\right]\right)\\ ={\displaystyle \sum _{k=0}^N}{b}_k{x}_3\left[n-k\right]\end{array}& & \left(3.44\right)\end{array}$$

We conclude that the input-output signal pair x3[n] ↔ y3[n] also satisfies the difference equation. The restriction discussed in Example 3.10 regarding the initial conditions will be applicable here as well. If we are interested in finding a unique solution for n ≥ n0, then the initial values

$$\begin{array}{ccc}y\left[n_0-1\right],& y\left[n_0-2\right],...,& y\left[n_0-N\right]\end{array}$$

are needed. The linearity condition given by Eqn. (3.40) must be satisfied for all values of n including index values n = n0 − 1, n0 − 2,..., n0 − N. Consequently, the system that corresponds to the difference equation in Eqn. (3.27) is linear only if all the initial conditions are zero, that is,

$$y\left[n_0-k\right]=0$$

for k = 1,...,N. Next we need to check for time invariance. Replacing the index n with n − m in Eqn. (3.27) we get

$$\begin{array}{ccc}{\displaystyle \sum _{k=0}^N}{a}_{k}y\left[n-m-k\right]={\displaystyle \sum _{k=0}^M}{b}_{k}x\left[n-m-k\right]& & \left(3.45\right)\end{array}$$

indicating that the input-output signal pair x[n − m] ↔ y[n − m] also satisfies the difference equation. Thus, the constant-coefficient linear difference equation is time-invariant.

3.5 Solving Difference Equations

The output signal of a discrete-time system in response to a specified input signal can be determined by solving the corresponding difference equation. In some of the examples of Section 3.3 we have already experimented with one method of solving a difference equation, namely the iterative method. Consider again the difference equation for the exponential smoother of Example 3.6. By writing the difference equation for each value of the index n we were able to obtain the output signal y[n] one sample at a time. Given the initial value y[−1] of the output signal, its value for n = 0 is found by

$$y\left[0\right]=\left(1-\alpha \right)y\left[-1\right]+\alpha x\left[n\right]$$

Setting n = 1 we obtain

$$y\left[1\right]=\left(1-\alpha \right)y\left[0\right]+\alpha x\left[1\right]$$

Repeating for n = 2 leads to

$$y\left[2\right]=\left(1-\alpha \right)y\left[1\right]+\alpha x\left[2\right]$$

and we can continue in this fashion indefinitely. The function ss_expsmoo(..) developed in MATLAB Exercise 3.3 is an implementation of the iterative solution of this difference equation.

The iterative solution method is not limited to DTLTI systems; it can also be used for solving the difference equations of nonlinear and/or time-varying systems. Consider, for example, the nonlinear difference equation for the logistic growth model of Example 3.8. For a specified parameter value r and initial value y[−1], the output at n = 0 is

$$y\left[0\right]=r\left(1-y\left[-1\right]\right)y\left[-1\right]$$

Next, y[1] is computed from y[0] as

$$y\left[1\right]=r\left(1-y\left[0\right]\right)y\left[0\right]$$

and so on. Fig. 3.13 shows the first 50 samples of the solution obtained in this fashion for r = 3.1 and y[−1] = 0.3.

Iterative solution of a difference equation can be also used as the basis of implementing a discrete-time system on real-time signal processing hardware. One shortcoming of this approach, however, is the lack of a complete analytical solution. Each time we iterate through the difference equation we obtain one more sample of the output signal, but we do not get an expression or a formula for computing the output for an arbitrary value of the index n. If we need to know y[1527], we must iteratively compute samples y[0] through y[1526] first.

In the rest of this section we will concentrate our efforts on developing an analytical method for solving constant-coefficient linear difference equations. Analytical solution of nonlinear and/or time-varying difference equations is generally difficult or impossible, and will not be considered further in this text.

The solution method we are about to present exhibits a lot of similarities to the method developed for solving constant-coefficient ordinary differential equations in Section 2.5. We will recognize two separate components of the output signal y[n] in the form

$$\begin{array}{ccc}y\left[n\right]=y_h\left[n\right]+y_p\left[n\right]& & \left(3.46\right)\end{array}$$

The term yh[n] is the solution of the homogeneous difference equation found by setting x[n] = 0 in Eqn. (3.27) for all values of n:

$$\begin{array}{ccc}{\displaystyle \sum _{k=0}^N}{a}_{k}y\left[n-k\right]=0& & \left(3.47\right)\end{array}$$

Thus, yh[n] is the signal at the output of the system when no input signal is applied to it. As in the continuous-time case, we will refer to yh[n] as the homogeneous solution of the difference equation or, equivalently, as the natural response of the system to which it corresponds. It depends on the structure of the system which is expressed through the set of coefficients ai for i = 0,...,N. Furthermore, it depends on the initial state of the system that is expressed through the output samples y[n0 − 1],y[n0 − 2],...,y[n0 − N]. (Recall that n0 is the beginning index for the solution; usually we will use n0 = 0.) When we discuss the stability property of DTLTI systems in Section 3.9 we will discover that, for a stable system, yh[n] approaches zero for large positive and negative values of the index n.

The second term yp[n] in Eqn. (3.46) is the part of the solution that is due to the input signal x[n] applied to the system. It is referred to as the particular solution of the difference equation. It depends on both the input signal x[n] and the internal structure of the system. It is independent of the initial state of the system. The combination of the homogeneous solution and the particular solution is referred to as the forced solution or the forced response.

3.5.1 Finding the natural response of a discrete-time system

We will begin the discussion of the solution method for solving the homogeneous equation by revisiting the linear exponential smoother first encountered in Example 3.6.

Example 3.11: Natural response of exponential smoother

Determine the natural response of the exponential smoother defined in Example 3.6 if y[−1] = 2.

Solution: The difference equation for the exponential smoother was given in Eqn. (3.6). The homogeneous difference equation is found by setting x[n] = 0:

$$\begin{array}{ccc}y\left[n\right]=\left(1-\alpha \right)y\left[n-1\right]& & \left(3.48\right)\end{array}$$

The natural response yh[n] yet to be determined must satisfy the homogeneous difference equation. We need to start with an educated guess for the type of signal yh[n] must be, and then adjust any relevant parameters. Therefore, looking at Eqn. (3.48), we ask the question: “What type of discrete-time signal remains proportional to itself when delayed by one sample?” A possible answer is a signal in the form

$$\begin{array}{ccc}{y}_h\left[n\right]=c{z}^n& & \left(3.49\right)\end{array}$$

where z is a yet undetermined constant. Delaying y[n] of Eqn. (3.49) by one sample we get

$$\begin{array}{ccc}{y}_h\left[n-1\right]=c{z}^{n-1}=z^{-1}c{z}^n=z^{-1}y\left[n\right]& & \left(3.50\right)\end{array}$$

Substituting Eqns. (3.49) and (3.50) into the homogeneous difference equation yields

$$c{z}^n=\left(1-\alpha \right)z^{-1}c{z}^n$$

or, equivalently

$$c{z}^n=\left[1-\left(1-\alpha \right)z^{-1}\right]=0$$

which requires one of the following conditions to be true for all values of n:

1. c zn = 0
2. [1 − (1 − α) z−1 = 0

We cannot use the former condition since it leads to the trivial solution y[n] = czn = 0, and is obviously not very useful. Furthermore, the initial condition y[−1] = 2 cannot be satisfied using this solution. Therefore we must choose the latter condition and set z = (1 − α) to obtain

$$\begin{array}{cc}{y}_h\left[n\right]=c{\left(1-\alpha \right)}^n,& \text{for }n\ge 0\end{array}$$

The constant c is determined based on the desired initial state of the system. We want y[−1] = 2, so we impose it as a condition on the solution found in Eqn. (3.51):

$$y_h\left[-1\right]=c{\left(1-\alpha \right)}^{-1}=2$$

This yields c = 2(1 − α) and

$$y_h\left[n\right]=2\left(1-\alpha \right){\left(1-\alpha \right)}^n=2{\left(1-\alpha \right)}^{n+1}$$

The natural response found is shown in Fig. 3.14 for α =1 and α = 0.2.

Software resources:

ex_3_11.m

Let us now consider the solution of the general homogeneous difference equation in the form

$$\begin{array}{ccc}{\displaystyle \sum _{k=0}^N}{a}_{k}y\left[n-k\right]=0& & \left(3.51\right)\end{array}$$

Let us start with the same initial guess that we used in Example 3.11:

$$\begin{array}{ccc}{y}_h\left[n\right]=c{z}^n& & \left(3.52\right)\end{array}$$

Shifted versions of the prescribed homogeneous solution are

$$\begin{array}{c}{y}_h\left[n-1\right]=c{z}^{n-1}=z^{-1}c{z}^n\\ y_h\left[n-2\right]=c{z}^{n-2}=z^{-2}c{z}^n\\ y_h\left[n-3\right]=c{z}^{n-3}=z^{-3}c{z}^n\end{array}$$

which can be expressed in the general form

$$\begin{array}{ccc}{y}_h\left[n-k\right]=c{z}^{n-k}=z^{-k}c{z}^n& & \left(3.53\right)\end{array}$$

Which value (or values) of z can be used in the homogeneous solution? We will find the answer by substituting Eqn. (3.53) into Eqn. (3.51):

$$\begin{array}{ccc}{\displaystyle \sum _{k=0}^N}{a}_k{z}^{-k}c{z}^n=0& & \left(3.54\right)\end{array}$$

The term czn is independent of the summation index k, and can be factored out to yield

$$c{z}^n\begin{array}{ccc}{\displaystyle \sum _{k=0}^N}{a}_k{z}^{-k}=0& & \left(3.55\right)\end{array}$$

There are two ways to satisfy Eqn. (3.55):

1. cz n = 0

   This leads to the trivial solution y[n] = 0 for the homogeneous equation, and is therefore not very interesting. Also, we have no means of satisfying any initial conditions with this solution other than y[−i] = 0 for i = 1,..., N.

2. ${\displaystyle \sum _{k=0}^N}{a}_k{z}^{-k}=0$

   This is called the characteristic equation of the system. Values of z that are the solutions of the characteristic equation can be used in exponential functions as solutions of the homogeneous difference equation.

The characteristic equation for a DTLTI system is found by starting with the homogeneous difference equation and replacing delayed versions of the output signal with the corresponding negative powers of the complex variable z.

The characteristic equation can be written in open form as

$$\begin{array}{ccc}{a}_0+a_1{z}^{-1}+...+a_{N-1}{z}^{-N+1}+a_N{z}^{-N}=0& & \left(3.58\right)\end{array}$$

If we want to work with non-negative powers of z, we could simply multiply both sides of the characteristic equation by zP to obtain

$$\begin{array}{ccc}{a}_0{z}^N+a_1{z}^{N-1}+...+a_{N-1}{z}^1+a_N=0& & \left(3.59\right)\end{array}$$

The polynomial on the left side of the equal sign in Eqn. (3.59) is the characteristic polynomial of the DTLTI system. Let the roots of the characteristic polynomial be z1, z2,...,zN so that Eqn. (3.59) can be written as

$$\begin{array}{ccc}{a}_0\left(a-z_1\right)\left(a-z_2\right)...\left(a-z_N\right)=0& & \left(3.60\right)\end{array}$$

Any of the roots of the characteristic polynomial can be used in a signal in the form

$$\begin{array}{cccc}{y}_i\left[n\right]=c_i{z}_i^n,& i=1,...,N& & \left(3.61\right)\end{array}$$

which satisfies the homogeneous difference equation:

$$\begin{array}{cccc}{\displaystyle \sum _{k=0}^N}{a}_k{y}_i\left[n-k\right]=0& \text{for }i=1,...,N& & \left(3.62\right)\end{array}$$

Furthermore, any linear combination of all valid terms in the form of Eqn. (3.61) satisfies the homogeneous difference equation as well, so we can write

$$\begin{array}{ccc}{y}_h\left[n\right]=c_1{z}_1^n+c_2{z}_2^n+...+c_N{z}_N^n={\displaystyle \sum _{k=1}^N}{c}_k{z}_k^n& & \left(3.63\right)\end{array}$$

The coefficients c1, c2,...,cN are determined from the initial conditions. The exponential terms $z_i^n$ in the homogeneous solution given by Eqn. (3.63) are the modes of the system. In later parts of this text we will see that the modes of a DTLTI system correspond to the poles of the system function and the eigenvalues of the state matrix.

Example 3.12: Natural response of second-order system

A second-order system is described by the difference equation

$$y\left[n\right]-\frac{5}{6}y\left[n-1\right]+\frac{1}{6}y\left[n-2\right]=0$$

Determine the natural response of this system for n ≥ 0 subject to initial conditions

$$\begin{array}{cc}y\left[n-1\right]=19,& \text{and }y\left[-2\right]=53\end{array}$$

Solution: The characteristic equation is

$$z^2-\frac{5}{6}z+\frac{1}{6}=0$$

with roots z1 = 1/2 and z2 = 1/3. Therefore the homogeneous solution of the difference equation is

$$y_h\left[n\right]=c_1{\left(\frac{1}{2}\right)}^n+c_2{\left(\frac{1}{3}\right)}^n$$

for n ≥ 0. The coefficients c1 and c2 need to be determined from the initial conditions. We have

$$\begin{array}{ccc}\begin{array}{ll}{y}_h[-1]\hfill & =c_1 {\left(\frac{1}{2}\right)}^{-1}+c_2 {\left(\frac{1}{3}\right)}^{-1}\hfill \\ \hfill & =2 c_1+3 c_2=19\hfill \end{array}& & (3.64)\end{array}$$

and

$$\begin{array}{ccc}\begin{array}{ll}{y}_h[-2]\hfill & =c_1 {\left(\frac{1}{2}\right)}^{-2}+c_2 {\left(\frac{1}{3}\right)}^{-2}\hfill \\ \hfill & =4 c_1+9 c_2=53\hfill \end{array}& & (3.65)\end{array}$$

Solving Eqns. (3.64) and (3.65) yields c1 = 2 and c2 = 5. The natural response of the system is

$$y_h\left[n\right]=2{\left(\frac{1}{2}\right)}^{n}u\left[n\right]+5{\left(\frac{1}{3}\right)}^{n}u\left[n\right]$$

Software resources:

ex_3_12.m

In Example 3.12 the characteristic equation obtained from the homogeneous difference equation had two distinct roots that were both real-valued, allowing the homogeneous solution to be written in the standard form of Eqn. (3.63). There are other possibilities as well. Similar to the discussion of the homogeneous differential equation in Section 2.5.3 we will consider three possible scenarios:

Case 1: All roots are distinct and real-valued.

This leads to the homogeneous solution

$$\begin{array}{ccc}y\left[n\right]={\displaystyle \sum _{k=1}^N}{c}_k{z}_k^n& & \left(3.66\right)\end{array}$$

for n ≥ n0 as we have seen in Example 3.12. The value of the real root zk determines the type of contribution made to the homogeneous solution by the term $c_k{z}_k^n$. If |zk| < 1 then $z_k^n$ decays exponentially over time. Conversely, |zk| > 1 leads toa term $z_k^n$ that grows exponentially. A negative value for zk causes the corresponding term in the homogeneous solution to have alternating positive and negative sample amplitudes. Possible forms of the contribution $z_k^n$ are shown in Fig. 3.15.

Case 2: Characteristic polynomial has complex-valued roots.

Since the difference equation and its characteristic polynomial have only real-valued coefficients, any complex roots of the characteristic polynomial must appear in conjugate pairs. Therefore, if

$$z_{1a}=r_1{e}^{j{\Omega }_1}$$

is a complex root, then its conjugate

$$z_{1b}=z_{1a}^{*}=r_1{e}^{-j{\Omega }_1}$$

must also be a root. Let the part of the homogeneous solution that is due to these two roots be

$$\begin{array}{ccc}\begin{array}{ll}{y}_{h1}[n]\hfill & =c_{1a}{z}_{1a}^n+c_{1b}{z}_{1b}^n\hfill \\ \hfill & =c_{1a}{r}_1^n{e}^{j{\Omega }_{1}n}+c_{1b}{r}_1^n{e}^{-j{\Omega }_{1}n}\hfill \end{array}& & (3.67)\end{array}$$

The coefficients c1a and c1b are yet to be determined from the initial conditions. Since the coefficients of the difference equation are real-valued, the solution yh[n] must also be real. Furthermore, yh1 [n], the part of the solution that is due to the complex conjugate pair of roots we are considering must also be real. This implies that the coefficients c1a and c1b must form a complex conjugate pair. We will write the two coefficients in polar complex form as

$$\begin{array}{cccc}{c}_{1a}=\left|c_1\right|e^{j{\theta }_1},& \text{and }{c}_{1b}=\left|c_1\right|e^{-j{\theta }_1}& & \left(3.68\right)\end{array}$$

Substituting Eqn. (3.68) into Eqn. (3.67) we obtain

$$\begin{array}{ccc}\begin{array}{ll}{y}_{h1}[n]\hfill & =\left|c_1\right|r_1^n{e}^{j({\Omega }_{1}n+{\theta }_1)}+\left|c_1\right|r_1^n{e}^{-j({\Omega }_{1}n+{\theta }_1)}\hfill \\ \hfill & =2\left|c_1\right|r_1^{n}cos({\Omega }_{1}n+{\theta }_1)\hfill \end{array}& & (3.69)\end{array}$$

The contribution of a complex conjugate pair of roots to the solution is in the form of a cosine signal multiplied by an exponential signal. The oscillation frequency of the discrete-time cosine signal is determined by Ω1. The magnitude of the complex conjugate roots,r1, impacts the amplitude behavior. If r1 < 1, then the amplitude of the cosine signal decays exponentially over time. If r1 > 1 on the other hand, the amplitude of the cosine signal grows exponentially over time. These two possibilities are illustrated in Fig. 3.16.

With the use of the the appropriate trigonometric identity1 Eqn. (3.69) can also be written in the alternative form

$$\begin{array}{ccc}\begin{array}{ll}{y}_{h1}[n]\hfill & =2\left|c_1\right|cos({\theta }_1)r_1^{n}cos({\Omega }_{1}n)-2\left|c_1\right|sin({\theta }_1)r_1^{n}sin({\Omega }_{1}n)\hfill \\ \hfill & =d_1{r}_1^{n}cos({\Omega }_{1}n)+d_2{r}_1^{n}cos({\Omega }_{1}n)\hfill \end{array}& & (3.70)\end{array}$$

Case 3: Characteristic polynomial has some multiple roots.

Consider again the factored version of the characteristic equation first given by Eqn. (3.60):

$$a_0\left(z-z_1\right)\left(z-z_2\right)...\left(z-z_{1N}\right)=0$$

What if the first two roots are equal, that is, z2 = z1? If we were to ignore the fact that the two roots are equal, we would have a natural response in the form

$$\begin{array}{ccc}\begin{array}{ll}{y}_h[n]\hfill & =c_1{z}_1^n+c_2{z}_2^n+\text{other terms}\hfill \\ \hfill & =c_1{z}_1^n+c_2{z}_1^n+\text{other terms}\hfill \\ \hfill & =(c_1+c_2)z_1^n+\text{other terms}\hfill \\ \hfill & ={\tilde{c}}_1{z}_1^n+\text{other terms}\hfill \end{array}& & (3.71)\end{array}$$

The equality of two roots leads to loss of one of the coefficients that we will need in order to satisfy the initial conditions. In order to gain back the coefficient we have lost, we need an additional term for the two roots at z = z1, and it can be obtained by considering a solution in the form

$$\begin{array}{ccc}{y}_h\left[n\right]=c_{11}{z}_1^n+c_{12}{z}_1^n+\text{other terms}& & \left(3.72\right)\end{array}$$

In general, a root of multiplicity r requires r terms in the homogeneous solution. If the characteristic polynomial has a factor (z − z1)r, the resulting homogeneous solution is

$$\begin{array}{ccc}{y}_h\left[n\right]=c_{11}{z}_1^n+c_{12}{z}_1^n+...+c_{1r}{n}^{1-1}{z}_1^n+\text{other terms}& & \left(3.73\right)\end{array}$$

Example 3.13: Natural response of second-order system revisited

Determine the natural response of each of the second-order systems described by the difference equations below:

1. y[n] − 1.4y[n − 1] + 0.85y[n − 2] = 0

   with initial conditions y[−1] = 5 and y[−2] = 7.

2. y[n] − 1.6y[n − 1] + 0.64y[n − 2] = 0

   with initial conditions y[−1] = 2 and y[−2] = − 3.

Solution:

1. The characteristic equation is

   $$z^2-1.4z+0.85=0$$

   which can be solved to yield

   $$z_{1,2}=0.7\pm j0.6$$

   Thus, the roots of the characteristic polynomial form a complex conjugate pair. They can be written in polar complex form as

   $$z_{1,2}=0.922e^{\pm j0.7086}$$

   which leads us to a homogeneous solution in the form

   $$y_h\left[n\right]=d_1{\left(0.922\right)}^{n}cos\left(0.7086n\right)+d_2{\left(0.922\right)}^{n}sin\left(0.7086n\right)$$

   for n ≥ 0. The coefficients d1 and d2 need to be determined from the initial conditions. Evaluating yh[n] for n = −1 and n = − 2 we have

   $$\begin{array}{ccc}\begin{array}{ll}{y}_h[-1]\hfill & =d_1 {(0.922)}^{-1}cos(-0.7086)+d_2 {(0.922)}^{-1}sin(-0.7086)\hfill \\ \hfill & =0.6923 d_1-0.5385 d_2=5\hfill \end{array}& & (3.74)\end{array}$$

   and

   $$\begin{array}{ccc}\begin{array}{ll}{y}_h[-2]\hfill & =d_1 {(0.922)}^{-2}cos(-0.4173)+d_2 {(0.922)}^{-2}sin(-1.4173)\hfill \\ \hfill & =0.1893 d_1-0.7456 d_2=7\hfill \end{array}& & (3.75)\end{array}$$

   Solving Eqns. (3.74) and (3.75) yields d1 = 1.05 and d2 = −5.8583. The natural response of the system is

   $$y_h\left[n\right]=1.05{\left(0.922\right)}^{n}cos\left(0.7086n\right)u\left[n\right]-5.8583{\left(0.922\right)}^{n}sin\left(0.7086n\right)u\left[n\right]$$

   and is graphed in Fig. 3.17.

   Figure 3.17

   

   Natural response of the system in Example 3.13 part (a).

2. For this system the characteristic equation is

   $$z^2-1.6z+0.64=0$$

   The roots of the characteristic polynomial are z1 = z2 = 0.8. Therefore we must look for a homogeneous solution in the form of Eqn. (3.72):

   $$y_h\left[n\right]=c_1{\left(0.8\right)}^n+c_{2}n{\left(0.8\right)}^n$$

   for n ≥ 0. Imposing the initial conditions at n = −1 and n = −2 we obtain

   $$\begin{array}{ccc}\begin{array}{ll}{y}_h[-1]\hfill & =c_1 {(0.8)}^{-1}+c_2 (-1){(0.8)}^{-1}\hfill \\ \hfill & =1.25 c_1-1.25 c_2=2\hfill \end{array}& & (3.76)\end{array}$$

   and

   $$\begin{array}{ccc}\begin{array}{ll}{y}_h[-2]\hfill & =c_1 {(0.8)}^{-2}+c_2 (-2){(0.8)}^{-2}\hfill \\ \hfill & =1.5625 c_1-3.125 c_2=-3\hfill \end{array}& & (3.77)\end{array}$$

   Eqns. (3.76) and (3.77) can be solved to obtain the coefficient values c1 = 5.12 and c2 = 3.52. The natural response is

   $$y_h\left[n\right]=5.12{\left(0.8\right)}^n+3.52n{\left(0.8\right)}^n$$

   and is graphed in Fig. 3.18.

   Figure 3.18

   

   Natural response of the system in Example 3.13 part (b).

Software resources:

ex_3_13a.m

ex_3_13b.m

3.5.2 Finding the forced response of a discrete-time system

In the preceding section we focused our efforts on determining the homogeneous solution of the constant-coefficient linear difference equation or, equivalently, the natural response yh[n] of the system when no external input signal exists. As stated in Eqn. (3.46), the complete solution is the sum of the homogeneous solution with the particular solution that corresponds to the input signal applied to the system. The procedure for finding a particular solution for a difference equation is similar to that employed for a differential equation. We start with an educated guess about the form of the particular solution we seek, and then adjust the values of its parameters so that the difference equation is satisfied. The form of the particular solution picked should include the input signal x[n] as well as the delayed input signals xn − k] that differ in form. For example, if the input signal is x[n] = K cos (Ω0n), then we assume a particular solution in the form

$$\begin{array}{ccc}{y}_p\left[n\right]=k_{1}cos\left({\Omega }_{0}n\right)+k_{2}sin\left({\Omega }_{0}n\right)& & \left(3.78\right)\end{array}$$

Both cosine and sine terms are needed since x[n − 1] is in the form

$$\begin{array}{ll}x[n-1]\hfill & =Kcos({\Omega }_0[n-1])\hfill \\ \hfill & =Kcos({\Omega }_0) cos({\Omega }_{0}n)+Ksin({\Omega }_0) sin({\Omega }_{0}n)\hfill \end{array}$$

Other delays of x[n] do not produce any terms that differ from these. If the input signal is in the form x[n] = n m then the delays of x[n] would contain the terms nm− 1, nm−2,...,n1, n0, and the particular solution is in the form

$$\begin{array}{ccc}{y}_p\left[n\right]=k_m{n}^m+k_{m-1}{n}^{m-1}+...+k_{1}n+k_0& & \left(3.79\right)\end{array}$$

Table 3.1 lists some of the common types of input signals and the forms of particular solutions to be used for them.

The unknown coefficients ki of the particular solution are determined from the difference equation by assuming all initial conditions are zero (recall that the particular solution does not depend on the initial conditions of the difference equation, or the initial state of the system). Initial conditions of the difference equation are imposed in the subsequent step for determining the unknown coefficients of the homogeneous solution, not the coefficients of the particular solution. The procedure for determining the complete forced solution of the difference equation is summarized below:

Example 3.14: Forced response of exponential smoother for unit-step input

Find the forced response of the exponential smoother of Example 3.6 when the input signal is a unit-step function, and y[−1] = 2.5.

Solution: In Example 3.11 the homogeneous solution of the difference equation for the exponential smoother was determined to be in the form

$$y_h\left[n\right]=c{\left(1-\alpha \right)}^n$$

For a unit-step input, the particular solution is in the form

$$y_p\left[n\right]=k_1$$

The particular solution must satisfy the difference equation. Substituting yp[n] into the difference equation we get

$$k_1=\left(1-\alpha \right)k_1+\alpha$$

and consequently k1 = 1. The forced solution is the combination of homogeneous and particular solutions:

$$\begin{array}{cc}y[n]& =y_h[n]+y_p[n]\\ & =c {(1-\alpha )}^n+1\end{array}$$

The constant c needs to be adjusted to satisfy the specified initial condition y[−1] = 2.5.

$$y\left[-1\right]=c{\left(1-\alpha \right)}^{-1}+1=2.5$$

results in c = 1.5 (1 − α), and the forced response of the system is

$$\begin{array}{ll}{y}_h[n]\hfill & =1.5(1-\alpha ) {(1-\alpha )}^n+1\hfill \\ \hfill & =1.5{(1-\alpha )}^{n+1}+1,\text{ for }n\ge 0\hfill \end{array}$$

This signal is shown in Fig. 3.19 for α = 0.1.

Software resources:

ex_3_14.m

Example 3.15: Forced response of exponential smoother for sinusoidal input

Find the forced response of the exponential smoother of Example 3.6 when the input signal is a sinusoidal function in the form

$$x\left[n\right]=Acos\left(\Omega n\right)$$

Use parameter values A = 20, Ω = 0.2π, and α = 0.1. The initial value of the output signal is y[−1] = 2.5.

Solution: Recall that the difference equation of the exponential smoother is

$$y\left[n\right]=\left(1-\alpha \right)y\left[n-1\right]+\alpha x\left[n\right]$$

The homogeneous solution is in the form

$$y_h\left[n\right]=c{\left(1-\alpha \right)}^n$$

For a sinusoidal input signal, the form of the appropriate particular solution is obtained from Table 3.1 as

$$\begin{array}{ccc}{y}_p\left[n\right]=k_{1}cos\left(\Omega n\right)+k_{2}sin\left(\Omega n\right)& & \left(3.80\right)\end{array}$$

The particular solution must satisfy the difference equation of the exponential smoother. Therefore we need

$$\begin{array}{ccc}{y}_p\left[n\right]-\left(1-\alpha \right)y_p\left[n-1\right]=\alpha x\left[n\right]& & \left(3.81\right)\end{array}$$

The term yp[n − 1] is needed in Eqn. (3.81). Time-shifting both sides of Eqn. (3.80)

$$\begin{array}{ccc}{y}_p\left[n-1\right]=k_{1}cos\left(\Omega \left[n-1\right]\right)+k_{2}sin\left(\Omega \left[n-1\right]\right)& & \left(3.82\right)\end{array}$$

Using the appropriate trigonometric identities 2 Eqn. (3.82) can be written as

$$\begin{array}{ccc}{y}_p\left[n-1\right]=\left[k_{1}cos(\Omega )-k_{2}sin(\Omega )\right]cos\left(\Omega n\right)+\left[k_{1}sin(\Omega )+k_{2}cos(\Omega )\right]sin\left(\Omega n\right)& & \left(3.83\right)\end{array}$$

Let us define

$$\beta =1-\alpha$$

to simplify the notation. Substituting Eqns. (3.80) and (3.83) along with the input signal x[n] into the difference equation in Eqn. (3.81) we obtain

$$\begin{array}{lll}\begin{array}{l}[k_1-\beta k_{1}cos(\Omega )+\beta k_{2}sin(\Omega )]cos(\Omega n)\hfill \\ +[k_2-\beta k_{1}sin(\Omega )-\beta k_{2}cos(\Omega )]sin(\Omega )\hfill \\ =\alpha Acos(\Omega n)\hfill \end{array}\hfill & \hfill & (3.84)\hfill \end{array}$$

Since Eqn. (3.84) must be satisfied for all values of the index n, coefficients of cos(Ωn)and sin (Ωn) on both sides of the equal sign must individually be set equal to each other. This leads to the two equations

$$\begin{array}{ccc}{k}_1\left[1-\beta cos(\Omega )\right]+k_2\beta sin(\Omega )=A& & \left(3.85\right)\end{array}$$

and

$$\begin{array}{ccc}-k_1\beta sin(\Omega )+k_2\left[1-\beta cos(\Omega )\right]=0& & \left(3.86\right)\end{array}$$

Eqns. (3.85) and (3.86) can be solved for the unknown coefficients k1 and k2 to yield

$$\begin{array}{lllll}{k}_1=\frac{\alpha A\left[1-\beta cos(\Omega )\right]}{1-2\beta cos(\Omega )+{\beta }^2}\hfill & \text{and}\hfill & k_2=\frac{\alpha A\beta sin(\Omega )}{1-2\beta cos(\Omega )+{\beta }^2}\hfill & \hfill & \left(3.87\right)\hfill \end{array}$$

Now the forced solution of the system can be written by combining the homogeneous and particular solutions as

$$\begin{array}{ccc}\begin{array}{c}y\left[n\right]=y_h\left[n\right]+y_p\left[n\right]\\ =c{\beta }^n+\frac{\alpha A\left[1-\beta cos(\Omega )\right]}{1-2\beta cos(\Omega )+{\beta }^2}cos\left(\Omega n\right)+\frac{\alpha A\beta sin(\Omega )}{1-2\beta cos(\Omega )+{\beta }^2}sin\left(\Omega n\right)\end{array}& & \left(3.88\right)\end{array}$$

Using the specified parameter values of A = 20, Ω = 0.2π, α = 0.1 and β = 0.9, the coefficients k1 and k2 are evaluated to be

$$\begin{array}{ccc}{k}_1=1.5371& \text{and}& k_2=2.9907\end{array}$$

and the forced response of the system is

$$y\left[n\right]=c{\left(0.9\right)}^n+1.5371cos\left(0.2\pi n\right)+2.9907sin\left(0.2\pi n\right)$$

We need to impose the initial condition y[−1] = 2.5 to determine the remaining unknown coefficient c. For n = − 1 the output signal is

$$\begin{array}{ll}y[-1]\hfill & =c{(0.9)}^{-1}+1.5371cos(-0.2\pi )+2.9907 sin(0.2\pi )\hfill \\ \hfill & =1.111c-0.5144=2.5\hfill \end{array}$$

Solving for the coefficient c yields to c = 2.7129. The forced response can now be written in complete form:

$$\begin{array}{ccc}y\left[n\right]=2,7129{\left(0.9\right)}^n+1.5371cos\left(0.2\pi n\right)+2.9907\text{ sin}\left(0.2\pi n\right)& & \left(3.89\right)\end{array}$$

for n ≥ 0. The forced response consists of two components. The first term in Eqn. (3.89) is the transient response

$$\begin{array}{ccc}{y}_t\left[n\right]=2,7129{\left(0.9\right)}^n& & \left(3.90\right)\end{array}$$

which is due to the initial state of the system. It disappears over time. The remaining terms in Eqn. (3.89) represent the steady-state response of the system:

$$\begin{array}{ccc}{y}_{ss}\left[n\right]=1.5371cos\left(0.2\pi n\right)+2.9907\text{ sin}\left(0.2\pi n\right)& & \left(3.91\right)\end{array}$$

Signals y[n], yt[n] and yss[n] are shown in Fig. 3.20.

Software resources:

ex_3_15.m

3.6 Block Diagram Representation of Discrete-Time Systems

A discrete-time system can also be represented with a block diagram, and multiple solutions exist that are functionally equivalent. In this section we will discuss just one particular technique for obtaining a block diagram, and the discussion of other techniques will be deferred until Chapter 8.

Block diagrams are useful for discrete-time systems not only because they provide additional insight into the operation of a system, but also because they allow implementation of the system on a digital computer. We often use the block diagram as the first step in developing the computer code for implementing a discrete-time system. An example of this is given in MATLAB Exercise 3.5.

Three types of operators are utilized in the constant-coefficient linear difference equation of Eqn. (3.27): multiplication of a signal by a constant gain factor, addition of two signals, and time shift of a signal. Consequently, the fundamental building blocks for use in block diagrams of discrete-time systems are constant-gain amplifier, signal adder and one-sample delay element as shown in Fig. 3.21.

We will begin the discussion with a simple third-order difference equation expressed as

$$\begin{array}{ccc}y\left[n\right]+a_{1}y\left[n-1\right]+a_{2}y\left[n-2\right]+a_{3}y\left[n-3\right]=b_{0}x\left[n-1\right]+b_{1}x\left[n-1\right]+b_{2}x\left[n-2\right]& & \left(3.92\right)\end{array}$$

This is a constant-coefficient linear difference equation in the standard form of Eqn. (3.27) with parameter values N = 3 and M = 2. Additionally, the coefficient of the term y[n] is chosen to be a0 = 1. This is not very restricting since, for the case of a0 = 1, we can always divide both sides of the difference equation by a0 to satisfy this condition. It can be shown that the following two difference equations that utilize an intermediate signal w (t) are equivalent to Eqn. (3.92):

$$\begin{array}{ccc}w\left[n\right]+a_{1}w\left[n-1\right]+a_{2}w\left[n-2\right]+a_{3}w\left[n-3\right]=x\left[n\right]& & \left(3.93\right)\end{array}$$

$$\begin{array}{ccc}y\left[n\right]=b_{0}w\left[n\right]+b_{1}w\left[n-1\right]+b_{2}w\left[n-2\right]& & \left(3.94\right)\end{array}$$

The proof is straightforward. The terms on the right side of Eqn. (3.92) can be written using Eqn. (3.93) and its time-shifted versions. The following can be written:

$$\begin{array}{ccc}{b}_{0}x\left[n\right]=b_0\left(w\left[n\right]+a_{1}w\left[n-1\right]+a_{2}w\left[n-2\right]+a_{3}w\left[n-3\right]\right)& & \left(3.95\right)\end{array}$$

$$\begin{array}{ccc}{b}_{1}x\left[n-1\right]=b_1\left(w\left[n-1\right]+a_{1}w\left[n-3\right]+a_{2}w\left[n-3\right]+a_{3}w\left[n-4\right]\right)& & \left(3.96\right)\end{array}$$

$$\begin{array}{ccc}{b}_{2}x\left[n-2\right]=b_2\left(w\left[n-2\right]+a_{1}w\left[n-3\right]+a_{2}w\left[n-4\right]+a_{3}w\left[n-5\right]\right)& & \left(3.97\right)\end{array}$$

We are now in a position to construct the right side of Eqn. (3.92) using Eqns. (3.95) through (3.97):

$$\begin{array}{ccc}\begin{array}{ll}{b}_{0}x\left[n\right]+\hfill & b_{1}x\left[n-1\right]+b_{2}x\left[n-2\right]=\hfill \\ \hfill & b_0\left(w\left[n\right]+a_{1}w\left[n-1\right]+a_{2}w\left[n-2\right]+a_{3}w\left[n-3\right]\right)\hfill \\ \hfill & +b_1\left(w\left[n-1\right]+a_{1}w\left[n-2\right]+a_{2}w\left[n-3\right]+a_{3}w\left[n-4\right]\right)\hfill \\ \hfill & +b_2\left(w\left[n-2\right]+a_{1}w\left[n-3\right]+a_{2}w\left[n-4\right]+a_{3}w\left[n-5\right]\right)\hfill \end{array}& & \left(3.98\right)\end{array}$$

Rearranging the terms of Eqn. (3.98) we can write it in the form

$$\begin{array}{ccc}\begin{array}{ll}{b}_{0}x\left[n\right]+\hfill & b_{1}x\left[n-1\right]+b_{2}x\left[n-2\right]=\hfill \\ \hfill & \left(b_{0}w\left[n\right]+b_{1}w\left[n-1\right]+b_{2}w\left[n-2\right]\right)\hfill \\ \hfill & +a_1\left(b_{0}w\left[n-1\right]+b_{1}w\left[n-2\right]+b_{2}w\left[n-3\right]\right)\hfill \\ \hfill & +a_2\left(b_{0}w\left[n-2\right]+b_{1}w\left[n-3\right]+b_{2}w\left[n-4\right]\right)\hfill \\ \hfill & +a_3\left(b_{0}w\left[n-3\right]+b_{1}w\left[n-4\right]+b_{2}w\left[n-5\right]\right)\hfill \end{array}& & \left(3.99\right)\end{array}$$

and recognizing that the terms on the right side of Eqn. (3.99) are time-shifted versions of y[n] from Eqn. (3.94) we obtain

$$\begin{array}{ccc}{b}_{0}x\left[n\right]+b_{1}x\left[n-1\right]+b_{2}x\left[n-2\right]=y\left[n\right]+a_{1}y\left[n-1\right]+a_{2}y\left[n-2\right]+a_{3}y\left[n-3\right]& & \left(3.100\right)\end{array}$$

which is the original difference equation given by Eqn. (3.92). Therefore, Eqns. (3.93) and (3.94) form an equivalent representation of the system described by Eqn. (3.92).

One possible block diagram implementation of the difference equation in Eqn. (3.93) is shown in Fig. 3.22. It takes the discrete-time signal x[n] as input, and produces the intermediate signal w [n] as output.

Three delay elements are used for obtaining the samples w[n − 1], w[n − 2] and w[n − 3]. The intermediate signal w[n] is then obtained via an adder that adds scaled versions of the three past samples of w[n]. Keep in mind that our ultimate goal is to obtain the signal y[n] which is related to the intermediate signal w[n] through Eqn. (3.94). The computation of y[n] requires the knowledge of w[n] as well as its two past samples w [n − 1] and w [n − 2], both of which are available in the block diagram of Fig. 3.22. The complete block diagram for the system is obtained by adding the necessary connections to the block diagram in Fig. 3.22, and is shown in Fig. 3.23.

The development above was based on a third-order difference equation, however, the extension of the technique to a general constant-coefficient linear difference equation is straightforward. In Fig. 3.23 the feed-forward gains of the block diagram are the right-side coefficients b0, b1,..., bM of the difference equation in Eqn. (3.92). Feedback gains of the block diagram are the negated left-side coefficients −a1, −a2,..., −aN of the difference equation. Recall that we must have a0 = 1 for this to work.

Imposing initial conditions

Initial conditions can easily be incorporated into the block diagram. The third-order difference equation given by Eqn. (3.92) would typically be solved subject to initial values specified for y[−1], y[−2] and y[−3]. For the block diagram we need to determine the corresponding values of w[−1], w[−2] and w[−3] through the use of Eqns. (3.93) and (3.94). This will be illustrated in Example 3.16.

Example 3.16: Block diagram for discrete-time system

Construct a block diagram to solve the difference equation

$$y\left[n\right]-0.7y\left[n-1\right]-0.8y\left[n-2\right]+0.84y\left[n-3\right]=0.1x\left[n\right]+0.2x\left[n-1\right]+0.3x\left[n-2\right]$$

with the input signal x[n] = u[n] and subject to initial conditions

$$\begin{array}{ccc}y\left[-1\right]=0.5,& y\left[-2\right]=0.3,& y\left[-3\right]=-0.4\end{array}$$

Solution: Using the intermediate variable w[n] as outlined in the preceding discussion we can write the following pair of difference equations that are equivalent to the original difference equation:

$$\begin{array}{ccc}w\left[n\right]-0.7w\left[n-1\right]-0.8w\left[n-2\right]+0.84w\left[n-3\right]=x\left[n\right]& & \left(3.101\right)\end{array}$$

$$\begin{array}{ccc}y\left[n\right]=0.1w\left[n\right]+0.2w\left[n-1\right]+0.3w\left[n-2\right]& & \left(3.102\right)\end{array}$$

The block diagram can now be constructed as shown in Fig. 3.24.

Initial conditions specified in terms of the values of y[−1],y[−2] and y[−3] need to be translated to corresponding values of w[−1], w [−2] and w [−3]. Writing Eqn. (3.102) for n = −1, −2, −3 yields the following three equations:

$$\begin{array}{ccc}y\left[-1\right]=0.1w\left[-1n\right]+0.2w\left[-2\right]+0.3w\left[-3\right]=0.5& & \left(3.103\right)\end{array}$$

$$\begin{array}{ccc}y\left[-2\right]=0.1w\left[-2\right]+0.2w\left[-3\right]+0.3w\left[-4\right]=0.3& & \left(3.104\right)\end{array}$$

$$\begin{array}{ccc}y\left[-3\right]=0.1w\left[-3\right]+0.2w\left[-4\right]+0.3w\left[-5\right]=-0.4& & \left(3.105\right)\end{array}$$

These equations need to be solved for w[−1], w[−2] and w[−3]. The two additional unknowns, namely w[−4] and w[−5], need to be obtained in other ways. Writing Eqn. (3.101) for n = − 1 yields

$$\begin{array}{ccc}w\left[-1\right]-0.7w\left[-2\right]-0.8w\left[-3\right]+0.84w\left[-4\right]=x\left[-1\right]& & \left(3.106\right)\end{array}$$

Since x[n] = u[n] we know that x[−1] = 0, therefore w[−4] can be expressed as

$$\begin{array}{ccc}w\left[-4\right]=-1.1905w\left[-1\right]+0.8333w\left[-2\right]+0.9524w\left[-3\right]& & \left(3.107\right)\end{array}$$

which can be substituted into Eqn. (3.104) to yield

$$\begin{array}{ccc}y\left[-2\right]=-03571w\left[-1\right]+0.35w\left[-2\right]+0.4857w\left[-3\right]=0.3& & \left(3.108\right)\end{array}$$

Similarly, writing Eqn. (3.101) for n = − 2 yields

$$\begin{array}{ccc}w\left[-2\right]-0.7w\left[-3\right]-0.8w\left[-4\right]+0.84w\left[-5\right]=x\left[-2\right]& & \left(3.109\right)\end{array}$$

We know that x [−2] = 0, therefore

$$\begin{array}{ccc}\begin{array}{ll}w[-5]\hfill & =-1.1905 w[-2]+0.8333 w[-3]+0.9524 w[-4]\hfill \\ \hfill & =-1.1905 w[-2]+0.8333 w[-3]\hfill \\ \hfill & +0.9524(-1.1905 w[-1]+0.8333 w[-2]+0.9524 w[-3])\hfill \\ \hfill & =1.1338 w[-1]-0.3968 w[-2]+1.7404 w[-3]\hfill \end{array}& & (3.110)\end{array}$$

Substituting Eqns. (3.107) and (3.110) into Eqn. (3.105) we obtain

$$\begin{array}{ccc}y\left[-3\right]=-0.5782w\left[-1\right]+0.0476w\left[-2\right]+0.8216w\left[-3\right]=-0.4& & \left(3.111\right)\end{array}$$

Eqns. (3.103), (3.108) and (3.111) can be solved simultaneously to determine the initial conditions in terms of w[n] as

$$\begin{array}{ccccc}w\left[-1\right]=1.0682,& w\left[-2\right]=1.7149,& w\left[-3\right]=0.1674& & \left(3.112\right)\end{array}$$

In the block diagram of Fig. 3.24 the outputs of the three delay elements should be set equal to these values before starting the simulation.

3.7 Impulse Response and Convolution

A constant-coefficient linear difference equation is sufficient for describing a DTLTI system such that the output signal of the system can be determined in response to any arbitrary input signal. However, we will often find it convenient to use additional description forms for DTLTI systems. One of these additional description forms is the impulse response which is simply the forced response of the system under consideration when the input signal is a unit impulse. This is illustrated in Fig. 3.25.

The impulse response also constitutes a complete description of a DTLTI system. The response of a DTLTI system to any arbitrary input signal x[n] can be uniquely determined from the knowledge of its impulse response.

In the next section we will discuss how the impulse response of a DTLTI system can be obtained from its difference equation. The reverse is also possible, and will be discussed in later chapters.

3.7.1 Finding impulse response of a DTLTI system

Finding the impulse response of a DTLTI system amounts to finding the forced response of the system when the forcing function is a unit impulse, i.e., x[n] = δ[n]. In the case of a difference equation with no feedback, the impulse response is found by direct substitution of the unit impulse input signal into the difference equation. If the difference equation has feedback, then finding an appropriate form for the particular solution may be a bit more difficult. This difficulty can be overcome by finding the unit-step response of the system as an intermediate step, and then determining the impulse response from the unit-step response.

The problem of determining the impulse response of a DTLTI system from the governing difference equation will be explored in the next two examples.

Example 3.17: Impulse response of moving average filters

Find the impulse response of the length-2, length-4 and length-N moving average filters discussed in Examples 3.3, 3.4 and 3.5.

Solution: Let us start with the length-2 moving average filter. The governing difference equation is

$$y\left[n\right]=\frac{1}{2}x\left[n\right]+\frac{1}{2}x\left[n-1\right]$$

Let h2[n] denote the impulse response of the length-2 moving average filter (we will use the subscript to indicate the length of the window). It is easy to compute h2[n] is by setting x[n] = δ[n] in the difference equation:

$$h_2\left[n\right]=\text{Sys}\left\{\delta \left[n\right]\right\}=\frac{1}{2}\delta \left[n\right]+\frac{1}{2}\delta \left[n-1\right]$$

The result can also be expressed in tabular form as

$$\begin{array}{ccc}{h}_2\left[n\right]=\left\{\underset{\uparrow }{1/2},1/2\right\}& & \left(3.113\right)\end{array}$$

Similarly, for a length-4 moving average filter with the difference equation

$$y\left[n\right]=\frac{1}{4}x\left[n\right]+\frac{1}{4}x\left[n-1\right]+\frac{1}{4}x\left[n-2\right]+\frac{1}{4}x\left[n-3\right]$$

the impulse response is

$$y_4\left[n\right]=\text{Sys}\left\{\delta \left[n\right]\right\}=\frac{1}{4}\delta \left[n\right]+\frac{1}{4}\delta \left[n-1\right]+\frac{1}{4}\delta \left[n-2\right]+\frac{1}{4}\delta \left[n-3\right]$$

or in tabular form

$$\begin{array}{ccc}{h}_4\left[n\right]=\left\{\underset{\uparrow }{1/4},1/4,1/4,1/4\right\}& & \left(3.114\right)\end{array}$$

These results are easily generalized to a length-N moving average filter. The difference equation of the length-N moving average filter is

$$\begin{array}{ccc}{h}_4\left[n\right]={\displaystyle \sum _{k=0}^{N-1}}x\left[n-k\right]& & \left(3.115\right)\end{array}$$

Substituting x[n] = δ[n] into Eqn. (3.115) we get

$$\begin{array}{ccc}{h}_N\left[n\right]=\text{Sys}\left\{\delta \left[n\right]\right\}={\displaystyle \sum _{k=0}^{N-1}}\delta \left[n-k\right]& & \left(3.116\right)\end{array}$$

The result in Eqn. (3.116) can be written in alternative forms as well. One of those alternative forms is

$$h_N\left[n\right]=\{\begin{array}{ll}\frac{1}{N},\hfill & n=0,...,N-1\hfill \\ 0,\hfill & \text{otherwise}\hfill \end{array}$$

and another one is

$$h_N\left[n\right]=\frac{1}{N}\left(u\left[n\right]-u\left[n-N\right]\right)$$

Example 3.18: Impulse response of exponential smoother

Find the impulse response of the exponential smoother of Example 3.6 with y[−1] = 0.

Solution: With the initial condition y[−1] = 0, the exponential smoother described by the difference equation in Eqn. (3.14) is linear and time-invariant (refer to the discussion in Section 3.4). These two properties will allow us to use superposition in finding its impulse response. Recall that the unit-impulse function can be expressed in terms of unit-step functions as

$$\delta \left[n\right]=u\left[n\right]-u\left[n-1\right]$$

As a result, the impulse response of the linear exponential smoother can be found through the use of superposition in the form

$$\begin{array}{ccc}\begin{array}{ll}h\left[n\right]=\text{Sys}\left\{\delta \left[n\right]\right\}\hfill & =\text{Sys}\left\{u\left[n\right]-u\left[n-1\right]\right\}\hfill \\ \hfill & =\text{Sys}\left\{u\left[n\right]\right\}-\text{Sys}\left\{u\left[n-1\right]\right\}\hfill \end{array}& & \left(3.117\right)\end{array}$$

We will first find the response of the system to a unit-step signal. The homogeneous solution of the difference equation at hand was already found in Example 3.11 as

$$y_h\left[n\right]=c{\left(1-\alpha \right)}^n$$

For a unit-step input, the particular solution is in the form

$$y_p\left[n\right]=k_1$$

Using this particular solution in the difference equation we get

$$k_1=\left(1-\alpha \right)k_1+\alpha$$

which leads to k1 = 1. Combining the homogeneous and particular solutions, the forced solution is found to be in the form

$$\begin{array}{ccc}\begin{array}{ll}y[n]\hfill & =y_h[n]+y_p[n]\hfill \\ \hfill & =c {(1-\alpha )}^n+1\hfill \end{array}& & (3.118)\end{array}$$

with coefficient c yet to be determined. If we now impose the initial condition y[−1] = 0 on the result found in Eqn. (3.118) we get

$$y\left[-1\right]=c{\left(1-\alpha \right)}^{-1}+1=0$$

and consequently

$$c=-\left(1-\alpha \right)$$

Thus, the unit-step response of the linear exponential smoother is

$$y\left[n\right]=\text{Sys}\left\{u\left[n\right]\right\}=1-\left(1-\alpha \right){\left(1-\alpha \right)}^n$$

for n ≥ 0. In compact notation, this result can be written as

$$\begin{array}{ccc}y\left[n\right]=\left[1-{\left(1-\alpha \right)}^{n+1}\right]u\left[n\right]& & \left(3.119\right)\end{array}$$

Since the system is time-invariant, its response to a delayed unit-step input is simply a delayed version of y[n] found in Eqn. (3.119):

$$\begin{array}{ccc}\begin{array}{ll}\text{Sys }\{u[n-1]\}\hfill & =y[n-1]\hfill \\ \hfill & =[1-{(1-\alpha )}^n] u[n-1]\hfill \end{array}& & (3.120)\end{array}$$

The impulse response of the linear exponential smoother is found using Eqns. (3.119) and (3.120) as

$$\begin{array}{ccc}h\left[n\right]=y\left[n\right]-y\left[n-1\right]=\alpha {\left(1-\alpha \right)}^{n}u\left[n\right]& & \left(3.121\right)\end{array}$$

and is shown in Fig. 3.26 for α = 0.1.

Software resources:

ex_3_18.m

3.7.2 Convolution operation for DTLTI systems

The development of the convolution operation for DTLTI systems will be based on the impulse decomposition of a discrete-time signal. It was established in Section 1.4.3 that any arbitrary discrete-time signal can be written as a sum of scaled and shifted impulse signals, leading to a decomposition in the form

$$\begin{array}{ccc}x\left[n\right]={\displaystyle \sum _{k=-\infty }^{\infty }}x\left[k\right]\delta \left[n-k\right]& & \left(3.122\right)\end{array}$$

Time-shifting a unit-impulse signal by k samples and multiplying it by the amplitude of the k-th sample of the signal x[n] produces the signal xk[n] = x[k]δ[n − k]. Repeating this process for all integer values of k and adding the resulting signals leads to Eqn. (3.122).

If x[n] is the input signal applied to a system, the output signal can be written as

$$\begin{array}{ccc}y\left[n\right]=\text{Sys}\left\{x\left[n\right]\right\}=\text{Sys}\left\{{\displaystyle \sum _{k=-\infty }^{\infty }}x\left[k\right]\delta \left[n-k\right]\right\}& & \left(3.123\right)\end{array}$$

The input signal is the sum of shifted and scaled impulse functions. If the system under consideration is linear, then using the additivity rule given by Eqn. (3.5) we can write

$$\begin{array}{ccc}y\left[n\right]={\displaystyle \sum _{k=-\infty }^{\infty }}\text{Sys}\left\{x\left[k\right]\delta \left[n-k\right]\right\}& & \left(3.124\right)\end{array}$$

Furthermore, using the homogeneity rule given by Eqn. (3.6), Eqn. (3.124) becomes

$$\begin{array}{ccc}y\left[n\right]={\displaystyle \sum _{k=-\infty }^{\infty }}x\left[k\right]\text{ Sys}\left\{\delta \left[n-k\right]\right\}& & \left(3.125\right)\end{array}$$

For the sake of discussion, let us assume that we know the system under consideration to be linear, but not necessarily time-invariant. The response of the linear system to any arbitrary input signal x[n] can be computed through the use of Eqn. (3.125), provided that we already know the response of the system to impulse signals shifted in by all possible delay amounts. The knowledge necessary for determining the output of a linear system in response to an arbitrary signal x[n] is

$$\left\{\begin{array}{cc}\text{Sys}\left\{\delta \left[n-k\right]\right\},& \text{all }k\end{array}\right\}$$

Eqn. (3.125) provides us with a viable, albeit impractical, method of determining system output y[n] for any input signal x[n]. The amount of the prerequisite knowledge that we must possess about the system to be able to use Eqn. (3.125) diminishes its usefulness. Things improve, however, if the system under consideration is also time-invariant.

Let the impulse response of the system be defined as

$$\begin{array}{ccc}\text{h}\left[n\right]=\text{Sys}\left\{\delta \left[n\right]\right\}& & \left(3.126\right)\end{array}$$

If, in addition to being linear, the system is also known to be time-invariant, then the response of the system to any shifted impulse signal can be derived from the knowledge of h[n] through

$$\begin{array}{ccc}\text{Sys}\left\{\delta \left[n-k\right]\right\}=h\left[n-k\right]& & \left(3.127\right)\end{array}$$

consistent with the definition of time invariance given by Eqn. (3.10). This reduces the prerequisite knowledge to just the impulse response h[n], and we can compute the output signal as

$$\begin{array}{ccc}y\left[n\right]={\displaystyle \sum _{k=-\infty }^{\infty }}x\left[k\right]h\left[n-k\right]& & \left(3.128\right)\end{array}$$

Eqn. (3.128) is known as the convolution sum for discrete-time signals. The output signal y[n] of a DTLTI system is obtained by convolving the input signal x[n] and the impulse response h[n] of the system. This relationship is expressed in compact notation as

$$\begin{array}{ccc}y\left[n\right]=x\left[n\right]*h\left[n\right]& & \left(3.129\right)\end{array}$$

where the symbol * represents the convolution operator. We will show later in this section that the convolution operator is commutative, that is, the relationship in Eqn. (3.128) can also be written in the alternative form

$$\begin{array}{ccc}\begin{array}{ll}y[n]\hfill & =h[n]*x[n]\hfill \\ \hfill & ={\displaystyle \sum }_{k=-\infty }^{\infty }h[k]x[n-k]\hfill \end{array}& & (3.130)\end{array}$$

by swapping the roles of h[n] and x[n] without affecting the end result.

Example 3.19: A simple discrete-time convolution example

A discrete-time system is described through the impulse response

$$h\left[n\right]=\left\{\underset{\underset{n=0}{\uparrow }}{4},3,2,\text{ 1}\right\}$$

Use the convolution operation to find the response of the system to the input signal

$$x\left[n\right]=\left\{\underset{\underset{n=0}{\uparrow }}{-3},7,4\right\}$$

Solution: Consider the convolution sum given by Eqn. (3.128). Let us express the terms inside the convolution summation, namely x[k] and h[n − k], as functions of k.

$$\begin{array}{ll}x[n]\hfill & =\{\underset{\underset{n=0}{\uparrow }}{-3}, 7, 4\}\hfill \\ h[-k]\hfill & =\{1, 2, 3, \underset{\underset{k=0}{\uparrow }}{4}\}\hfill \\ h[n-k]\hfill & =\{1, 2, 3, \underset{\underset{k=n}{\uparrow }}{4}\}\hfill \end{array}$$

In its general form both limits of the summation in Eqn. (3.128) are infinite. On the other hand, x[k] = 0 for negative values of the summation index k, so setting the lower limit of the summation to k = 0 would have no effect on the result. Similarly, the last significant sample of x[k] is at index k = 2, so the upper limit can be changed to k =2 without affecting the result as well, leading to

$$\begin{array}{ccc}y\left[n\right]={\displaystyle \sum _{k=0}^2}x\left[k\right]h\left[n-k\right]& & \left(3.131\right)\end{array}$$

If n < 0, we have h[n − k] = 0 for all terms of the summation in Eqn. (3.131), and the output amplitude is zero. Therefore we will only concern ourselves with samples for which n ≥ 0. The factor h[n − k] has significant samples in the range

$$0\le n-k\le 3$$

which can be expressed in the alternative form

$$n-3\le k\le n$$

The upper limit of the summation in Eqn. (3.131) can be set equal to k = n without affecting the result, however, if n> 2 then we should leave it at k = 2. Similarly, the lower limit can be set to k = n − 3 provided that n − 3 > 0, otherwise it should be left at k = 0. So, a compact version of the convolution sum adapted to the particular signals of this example would be

$$\begin{array}{cccc}y\left[n\right]={\displaystyle \sum _{k=max\left(0,n-3\right)}^{min\left(2,n\right)}}x\left[k\right]h\left[n-k\right],& \text{for }n\ge 0& & \left(3.132\right)\end{array}$$

where the lower limit is the larger of k = 0 and k = n − 3, and the upper limit is the smaller of k = 2 and k = n. We will use this result to compute the convolution of x[n] and h [n].

For n = 0:

$$\begin{array}{ll}y[0]\hfill & ={\displaystyle \sum }_{k=0}^{0}x[k]h[0-k]\hfill \\ \hfill & =x[0]h[0]=(-3)(4)=-12\hfill \end{array}$$

For n = 1:

$$\begin{array}{ll}y[1]\hfill & ={\displaystyle \sum }_{k=0}^{1}x[k]h[1-k]\hfill \\ \hfill & =x[0]h[1]=x[1]h[0]\hfill \\ \hfill & =(-3)(3)+(7)(4)=19\hfill \end{array}$$

For n = 2:

$$\begin{array}{ll}y[2]\hfill & ={\displaystyle \sum }_{k=0}^{2}x[k]h[2-k]\hfill \\ \hfill & =x[0]h[2]+x[1]h[1]+x[2]h[0]\hfill \\ \hfill & =(-3)(2)+(7)(3)+(4)(4)=31\hfill \end{array}$$

For n = 3:

$$\begin{array}{ll}y[3]\hfill & ={\displaystyle \sum }_{k=0}^{2}x[k]h[3-k]\hfill \\ \hfill & =x[0]h[3]+x[1]h[2]+x[2]h[1]\hfill \\ \hfill & =(-3)(1)+(7)(2)+(4)(3)=23\hfill \end{array}$$

For n = 4:

$$\begin{array}{ll}y[4]\hfill & ={\displaystyle \sum }_{k=1}^{2}x[k]h[4-k]\hfill \\ \hfill & =x[1]h[3]+x[2]h[2]\hfill \\ \hfill & =(7)(1)+(4)(2)=15\hfill \end{array}$$

For n = 5:

$$\begin{array}{ll}y[5]\hfill & ={\displaystyle \sum }_{k=2}^{2}x[k]h[5-k]\hfill \\ \hfill & =x[2]h[3]+(4) (1)=4\hfill \end{array}$$

Thus the convolution result is

$$y\left[n\right]=\{\underset{\underset{n=0}{\uparrow }}{-12},19,31,23,15,4\}$$

Example 3.20: Simple discrete-time convolution example revisited

Rework the convolution problem of Example 3.19 with the following modifications applied to the two signals:

$$h\left[n\right]=\{\underset{\underset{n=N_2}{\uparrow }}{4},3,\text{ 2},\text{ 1}\}$$

and

$$x\left[n\right]=\{\underset{\underset{n=N_1}{\uparrow }}{-3},7,\text{ 4}\}$$

Assume the starting indices N1 and N2 are known constants.

Solution: We need to readjust limits of the summation index. The function x[k] has significant samples in the range

$$\begin{array}{ccc}{N}_1\le k\le N_1+2& & \left(3.133\right)\end{array}$$

For the function h[n − k], the significant range of the index k is found from the inequality

$$N_2\le n-k\le N_2+3$$

the terms of which can be rearranged to yield

$$\begin{array}{ccc}n-N_2-3\le k\le n-N_2& & \left(3.134\right)\end{array}$$

Using the inequalities in Eqns. (3.133) and (3.134) the convolution sum can be written as

$$\begin{array}{ccc}y\left[n\right]={\displaystyle \sum _{k=K_1}^{K_2}}x\left[k\right]h\left[n-k\right]& & \left(3.135\right)\end{array}$$

with the limits

$$\begin{array}{ccccc}{K}_1=max\left(N_1,n-N_2-3\right),& \text{and}& & K_2=min\left(N_1+2,n-N_2\right),& \left(3.136\right)\end{array}$$

For example, suppose we have N1 = 5 and N2 = 7. Using Eqn. (3.135) with the limits in Eqn. (3.136) we can write the convolution sum as

$$\begin{array}{ccc}y\left[n\right]={\displaystyle \sum _{k=max\left(5,n-10\right)}^{min\left(7,n-7\right)}}x\left[k\right]h\left[n-k\right]& & \left(3.137\right)\end{array}$$

For the summation to contain any significant terms, the lower limit must not be greater than the upper limit, that is, we need

$$max\left(5,n-10\right)\le min\left(7,n-7\right)$$

As a result, the leftmost significant sample of y[n] will occur at index n = 12. In general, it can be shown (see Problem 3.23 at the end of this chapter) that the leftmost significant sample will be at the index n = N1 + N2. The sample y[12] is computed as

$$\begin{array}{ll}y[12]\hfill & ={\displaystyle \sum }_{k=5}^{5}x[k]h[12-k]\hfill \\ \hfill & =x[5]h[7]=(-3) (4)=-12\hfill \end{array}$$

Other samples of y[n] can be computed following the procedure demonstrated in Example 3.19 and yield the same pattern of values with the only difference being the starting index. The complete solution is

$$y\left[n\right]=\{\underset{\underset{n=12}{\uparrow }}{-12},19,\text{ 31},\text{ 23},\text{ 15},4\}$$

In computing the convolution sum it is helpful to sketch the signals. The graphical steps involved in computing the convolution of two signals x[n] and h[n] at a specific index value n can be summarized as follows:

The next example will illustrate the graphical details of the convolution operation for DTLTI systems.

Example 3.21: A more involved discrete-time convolution example

A discrete-time system is described through the impulse response

$$h\left[n\right]=\left({0.9}^n\right)u\left[n\right]$$

Use the convolution operation to find the response of a system to the input signal

$$x\left[n\right]=u\left[n\right]-u\left[n-7\right]$$

Signals h[n] and x[n] are shown in Fig. 3.29.

Solution: Again we will find it useful to sketch the functions x[k], h[n − k] and their product before we begin evaluating the convolution result. Such a sketch is shown in Fig. 3.30. It reveals three distinct possibilities for the overlap of x[k] and h[n − k]. The convolution sum needs to be set up for each of the three regions of index n.

Case 1: n < 0

There is no overlap between the two functions in this case, therefore their product equals zero for all values of k. The output signal is

$$\begin{array}{ccc}y\left[n\right]=0,& \text{for}& n<0\end{array}$$

Case 2: 0 ≤ n ≤ 6

For this case, the two functions overlap for the range of the index 0 ≤ k ≤ n. Setting summation limits accordingly, the output signal can be written as

$$\begin{array}{ccc}y\left[n\right]={\displaystyle \sum _{k=0}^n}\left(1\right){\left(0.9\right)}^{n-k}& & \left(3.139\right)\end{array}$$

The expression in Eqn. (3.139) can be simplified by factoring out the common term (0.9)n and using the geometric series formula (see Appendix C) to yield

$$\begin{array}{ccc}\begin{array}{ll}y[n]\hfill & ={(0.9)}^n{\displaystyle \sum }_{k=0}^n{(0.9)}^k\hfill \\ \hfill & ={(0.9)}^n\frac{1-{(0.9)}^{-(n+1)}}{1-{(0.9)}^{-1}}\hfill \\ \hfill & =-9[{(0.9)}^n-\frac{1}{0.9}] , \text{for} 0\le n\le 6\hfill \end{array}& & (3.140)\end{array}$$

Case 3: n > 6

For n > 6 the overlap of the two functions will occur in the range 0 ≤ k ≤ 6, so the summation limits need to be adjusted.

$$\begin{array}{ccc}y\left[n\right]={\displaystyle \sum _{k=0}^6}\left(1\right){\left(0.9\right)}^{n-k}& & \left(3.141\right)\end{array}$$

Again factoring out the (0.9)n term and using the geometric series formula we get

$$\begin{array}{ccc}\begin{array}{ll}y[n]\hfill & ={(0.9)}^n{\displaystyle \sum }_{k=0}^6{(0.9)}^k\hfill \\ \hfill & ={(0.9)}^n\frac{1-{(0.9)}^{-7}}{1-{(0.9)}^{-1}}\hfill \\ \hfill & =9.8168 {(0.9)}^n , for n>6\hfill \end{array}& & (3.142)\end{array}$$

Thus, we have computed the output signal in each of the three distinct intervals we have identified. Putting these three partial solutions together, the complete solution for the output signal is obtained as

$$\begin{array}{ccc}y\left[n\right]=\{\begin{array}{cc}0,& n<0\\ -9\left[{0.9}^n-\frac{1}{0.9}\right],& 0\le n\le 6\\ 9.8168{\left(0.9\right)}^n,& n>0\end{array}& & \left(3.143\right)\end{array}$$

and is shown in Fig. 3.31.

Software resources:

ex_3_21.m

3.8 Causality in Discrete-Time Systems

Causality is an important feature of physically realizable systems. A system is said to be causal if the current value of the output signal depends only on current and past values of the input signal, but not on its future values. For example, a discrete-time system defined by the relationship

$$\begin{array}{ccc}y\left[n\right]=y\left[n-1\right]+x\left[n\right]-3x\left[n-1\right]& & \left(3.144\right)\end{array}$$

is causal, and one defined by

$$\begin{array}{ccc}y\left[n\right]=y\left[n-1\right]+x\left[n\right]-3x\left[n+1\right]& & \left(3.145\right)\end{array}$$

is non-causal. Causal systems can be implemented in real-time processing mode where a sample of the output signal is computed in response to each incoming sample of the input signal. On the order hand, implementation of non-causal systems may only be possible in post processing mode where the entire input signal must be observed and recorded before processing can begin.

In the case of a DTLTI system, the causality property can easily be related to the impulse response. Recall that the output signal y[n] of a DTLTI system can be computed as the convolution of its input signal x[n] with its impulse response h[n] as

$$\begin{array}{ccc}y\left[n\right]=h\left[n\right]*x\left[n\right]={\displaystyle \sum _{k=-\infty }^{\infty }}h\left[k\right]x\left[n-k\right]& & \left(3.146\right)\end{array}$$

For the system under consideration to be causal, the computation of y[n] should not require any future samples of the input signal. Thus, the term xn − k] in the summation should not contain index values in the future. This requires

$$\begin{array}{ccccc}n-k\le n& \Rightarrow & k\ge 0& & \left(3.147\right)\end{array}$$

The product h[k]x[n − k] should not have any non-zero values for k < 0. Therefore, the impulse response h[n] should be equal to zero for all negative index values:

$$\begin{array}{ccccc}h\left[n\right]=0& \text{for all}& n<0& & \left(3.148\right)\end{array}$$

For a causal DTLTI system, the convolution relationship in Eqn. (3.146) can be written in the right-sided form by setting the lower limit of the summation index equal to zero:

$$\begin{array}{ccc}y\left[n\right]={\displaystyle \sum _{k=0}^{\infty }}h\left[k\right]x\left[n-k\right]& & \left(3.149\right)\end{array}$$

3.9 Stability in Discrete-Time Systems

A discrete-time input signal x[n] is said to be bounded if an upper bound Bx exists such that

$$\begin{array}{ccc}\left|x\left[n\right]\right|<B_x<\infty & & \left(3.150\right)\end{array}$$

for all values of the integer index n. A discrete-time system is stable if a finite upper bound By exists for the output signal in response to any input signal bounded as described in Eqn. (3.150).

If the system under consideration is DTLTI, it is possible to relate the stability condition given by Eqn. (3.151) to the impulse response of the system as well as its difference equation. Derivation of the necessary condition follows:

Eqn. (3.158) leads us to the conclusion

Example 3.22: Stability of a length-2 moving-average filter

Comment on the stability of the length-2 moving-average filter described by the difference equation

$$y\left[n\right]=\frac{1}{2}x\left[n\right]+\frac{1}{2}x\left[n-1\right]$$

Solution: We will approach this problem in two different ways. First, let’s check directly to see if any arbitrary bounded input signal is guaranteed to produce a bounded output signal. The absolute value of the output signal is

$$\begin{array}{ccc}\left|y\left[n\right]\right|=\left|\frac{1}{2}x\left[n\right]+\frac{1}{2}x\left[n-1\right]\right|& & \left(3.160\right)\end{array}$$

Since absolute value of a sum is less than or equal to sum of absolute values, we can derive the following inequality from Eqn. (3.160):

$$\begin{array}{ccc}\left|y\left[n\right]\right|\le \frac{1}{2}\left|x\left[n\right]\right|+\frac{1}{2}\left|x\left[n-1\right]\right|& & \left(3.161\right)\end{array}$$

Furthermore, since we assume |x[n]| < Bx for all n, replacing |x[n]| and |x[n − 1]| terms on the right side of the inequality in Eqn. (3.161) does not affect the validity of the inequality, so we have

$$\begin{array}{ccc}\left|y\left[n\right]\right|\le \frac{1}{2}{B}_x+\frac{1}{2}{B}_x=B_x& & \left(3.162\right)\end{array}$$

proving that the output signal y[n] is bounded as long as the input signal x[n] is.

An alternative way to attack the problem would be to check the impulse response for the absolute summability condition in Eqn. (3.159). The impulse response of the length-2 moving-average filter is

$$\begin{array}{ccc}h\left[n\right]=\frac{1}{2}\delta \left[n\right]+\frac{1}{2}\delta \left[n-1\right]& & \left(3.163\right)\end{array}$$

which is clearly summable in an absolute sense.

Example 3.23: Stability of the loan balance system

Comment on the stability of the loan balance system discussed in Example 3.7.

Solution: Recall that the governing difference equation is

$$y\left[n\right]=\left(1+c\right)y\left[n-1\right]-x\left[n\right]$$

where c is a positive constant interest rate. This system can be analyzed in terms of its stability using the same approach that we have used in the previous example. However, we will take a more practical approach and analyze the system from a layperson’s perspective.

What if we borrowed the money and never made a payment? The loan balance would keep growing each period. If the initial value of the output signal is y[0] = A and if x[n] = 0 for n ≥ 1, then we would have

$$\begin{array}{c}y\left[1\right]=\left(1+c\right)A\\ y\left[2\right]={\left(1+c\right)}^{2}A\\ ⋮\\ y\left[n\right]={\left(1+c\right)}^{n}A\end{array}$$

which indicates that the system is unstable since we were able to find at least one bounded input signal that leads to an unbounded output signal.

It is also worth noting that the characteristic equation is

$$z-\left(1+c\right)=0$$

and its only solution is at z1 = 1 + c.

The stability of a DTLTI system can also be associated with the modes of the difference equation that governs its behavior. We have seen in Section 3.5.1 that, for a causal DTLTI system, real and complex roots zk of the characteristic polynomial for which |zk| ≥ 1 are associated with unstable behavior. Thus, for a causal DTLTI system to be stable, the magnitudes of all roots of the characteristic polynomial must be less than unity. If a circle is drawn on the complex plane with its center at the origin and its radius equal to unity, all roots of the characteristic polynomial must lie inside the circle for the corresponding causal DTLTI system to be stable.

A side note: In describing the associations between the roots of the characteristic polynomial and stability, we referred to a causal DTLTI system. If we were to consider an anti-causal system, the impulse response of which proceeds in the negative direction toward n → −∞, then the associations described above would have to be reversed. In that case roots outside the unit circle of the complex plane would lead to stable behavior.

Why is stability important for a DTLTI system?

An unstable DTLTI system is one that is capable of producing an unbounded output signal in response to at least some bounded input signals. What is the practical significance of this? Since we are dealing with numerical algorithms implemented via software on a computer, an unstable algorithm may lead to an output signal containing numbers that keep growing until they reach magnitudes that can no longer be handled by the number representation conventions of the processor or the operating system. When this occurs, the software that implements the system ceases to function in the proper way.

3.10 Further Reading

[1] S. Elaydi. An Introduction to Difference Equations. Springer Undergraduate Texts in Mathematics and Technology. Springer, 2005.

[2] W.G. Kelley and A.C. Peterson.Difference Equations: An Introduction With Applications. Harcourt/Academic Press, 2001.

[3] V. Lakshmikantham. Theory of Difference Equations Numerical Methods and Applications. Marcel Dekker, 2002.

[4] R.E. Mickens. Difference Equations: Theory and Applications. Van Nostrand Reinhold Company, 1990.

MATLAB Exercises

Problems

1. 3.1. A number of discrete-time systems are specified below in terms of their input-output relationships. For each case determine if the system is linear and/or time-invariant.

   1. y[n] = x[n]u[n]
   2. y[n] = 3x[n] + 5
   3. y[n] = 3x[n] + 5u[n]
   4. y[n] = n x[n]
   5. y[n] = cos(0.2πn) x[n]
   6. y[n] = x[n] + 3x[n − 1]
   7. y[n] = x[n] + 3 x[n − 1]x[n − 2]

2. 3.2. A number of discrete-time systems are described below. For each case determine if the system is linear and/or time-invariant.

   1. $y\left[n\right]={\displaystyle \sum _{k=-\infty }^n}x\left[k\right]$
   2. $y\left[n\right]={\displaystyle \sum _{k=0}^n}x\left[k\right]$
   3. $y\left[n\right]={\displaystyle \sum _{k=n-2}^n}x\left[k\right]$
   4. $y\left[n\right]={\displaystyle \sum _{k=n-2}^{n+2}}x\left[k\right]$

3. 3.3. Consider the cascade combination of two systems shown in Fig. P.3.3(a).

   Figure P. 3.3

   

   1. Let the input-output relationships of the two subsystems be given as

      $$\begin{array}{ccc}{\text{Sys}}_1\left\{x\left[n\right]\right\}=3x\left[n\right]& \text{and}& {\text{Sys}}_2\left\{w\left[n\right]\right\}=w\left[n-2\right]\end{array}$$

      Write the relationship between x[n] and y[n].

   2. Let the order of the two subsystems be changed as shown in Fig. P.3.3(b). Write the relationship between x[n] and $\overline{y}\left[n\right]$. Does changing the order of two subsystems change the overall input-output relationship of the system?

4. 3.4. Repeat Problem 3.3 with the following sets of subsystems:

   1. $\begin{array}{ccc}{\text{Sys}}_1\left\{x\left[n\right]\right\}=3\left[n\right]& \text{and}& {\text{Sys}}_2\left\{w\left[n\right]\right\}=nw\left[n\right]\end{array}$
   2. $\begin{array}{ccc}{\text{Sys}}_1\left\{x\left[n\right]\right\}=3x\left[n\right]& \text{and}& {\text{Sys}}_2\left\{w\left[n\right]\right\}=w\left[n\right]+5\end{array}$

5. 3.5. The response of a linear and time-invariant system to the input signal x[n] = δ [n] is given by

   $$\text{Sys}\left\{\delta \left[n\right]\right\}=\{\underset{\underset{n=0}{\uparrow }}{2},1,-1\}$$

   Determine the response of the system to the following input signals:

   1. x[n] = δ[n] + δ [n − 1]
   2. x[n] = δ[n] − 2δ[n − 1] + δ[n − 2]
   3. x[n] = u[n] − u[n − 5]
   4. x[n] = n (u[n] − u[n − 5])

6. 3.6. Consider a system that is known to be linear but not necessarily time-invariant. Its responses to three impulse signals are given below:

   $$\begin{array}{ll}\text{Sys}\{\delta [n]\}\hfill & =\{\underset{\underset{n=0}{\uparrow }}{1} , 2, 3\}\hfill \\ \text{Sys}\{\delta [n-1]\}\hfill & =\{\underset{\underset{n=1}{\uparrow }}{3} , 3, 2\}\hfill \\ \text{Sys}\{\delta [n-2]\}\hfill & =\{\underset{\underset{n=2}{\uparrow }}{3} , 2, 1\}\hfill \end{array}$$

   For each of the input signals listed below, state whether the response of the system can be determined from the information given. If the response can be determined, find it. If not, explain why it cannot be done.

   1. x[n] = 5δ[n − 1]
   2. x[n] = 3δ[n] + 2δ[n − 1]
   3. x[n] = δ[n] − 2δ[n − 1] + 4δ[n − 2]
   4. x[n] = u[n] − u[n − 3]
   5. x[n] = u[n] − u[n − 4]

7. 3.7. The discrete-time signal

   $$x\left[n\right]=\{\underset{\underset{n=0}{\uparrow }}{1.7},\text{ 2}\text{.3},3.1,3.3,3.7,2.9,2.2,1.4,0.6,-3.1,0.4\}$$

   is used as input to a length-2 moving average filter. Determine the response y[n] for n = 0,...,9. Use x[−1] = 0.

8. 3.8. Consider again the signal x[n] specified in Problem 3.7. If it is applied to a length-4 moving average filter, determine the output signal y[n] for n = 0,...,9. Use x[−1] = x[−2] = x[−3] = 0.

9. 3.9. The signal x[n] specified in Problem 3.7 is used as input to an exponential smoother with α = 0.2. The initial value of the output signal is y[−1] = 1. Determine y[n] for n = 0,...,9.

10. 3.10. Consider the difference equation model for the loan payment system explored in Example 3.7. The balance at the end of month-n is given by

    $$y\left[n\right]=\left(1+c\right)y\left[n-1\right]-x\left[n\right]$$

    where c is the monthly interest rate and x[n] represents the payment made in month-n. Let the borrowed amount be $10,000 to be paid back at the rate of $250 per month and with a monthly interest rate of 0.5 percent, that is, c = 0.005. Determine the monthly balance for n = 1,...,12 by iteratively solving the difference equation.

    Hint: Start with the initial balance of y[0] = 10000 and model the payments with the input signal

    $$x\left[n\right]=250u\left[n-1\right]$$

11. 3.11. Refer to Example 3.9 in which a nonlinear difference equation was found for computing a root of a function. The idea was adapted to the computation of the square root of a positive number A by searching for a root of the function

    $$f\left(w\right)=w^2-A$$

    By iteratively solving the difference equation given by Eqn. (3.25), approximate the square root of

    1. A = 5
    2. A = 17
    3. A = 132

    In each case carry out the iterations until the result is accurate up to the fourth digit after the decimal point.

12. 3.12. For each homogeneous difference equation given below, find the characteristic equation and show that it only has simple real roots. Find the homogeneous solution for n ≥ 0 in each case subject to the initial conditions specified.

    Hint: For part (e) use MATLAB function roots(..) to find the roots of the characteristic polynomial.

    1. $\begin{array}{ccc}y\left[n\right]+0.2y\left[n-1\right]-0.63y\left[n-2\right]=0,& y\left[-1\right]=5,& y\left[-2\right]=-3\end{array}$
    2. $\begin{array}{ccc}y\left[n\right]+1.3y\left[n-1\right]+0.4y\left[n-2\right]=0,& y\left[-1\right]=0,& y\left[-2\right]=5\end{array}$
    3. $\begin{array}{ccc}y\left[n\right]-1.7y\left[n-1\right]+0.72y\left[n-2\right]=0,& y\left[-1\right]=1,& y\left[-2\right]=2\end{array}$
    4. $\begin{array}{ccc}y\left[n\right]-0.49y\left[n-2\right]=0,& y\left[-1\right]=-3,& y\left[-2\right]=-1\end{array}$
    5. $\begin{array}{cccc}y\left[n\right]+0.6y\left[n-1\right]-0.51y\left[n-2\right]-0.28y\left[n-3\right]=0,& y\left[-1\right]=3,& y\left[-2\right]=2& y\left[-3\right]=1\end{array}$

13. 3.13. For each homogeneous difference equation given below, find the characteristic equation and show that at least some of its roots are complex. Find the homogeneous solution for n ≥ 0 in each case subject to the initial conditions specified.

    Hint: For part (d) use MATLAB function roots(..) to find the roots of the characteristic polynomial.

    1. $\begin{array}{ccc}y\left[n\right]-1.4y\left[n-1\right]+0.85y\left[n-2\right]=0,& y\left[-1\right]=2,& y\left[-2\right]=-2\end{array}$
    2. $\begin{array}{ccc}y\left[n\right]-1.6y\left[n-1\right]+y\left[n-2\right]=0,& y\left[-1\right]=0,& y\left[-2\right]=3\end{array}$
    3. $\begin{array}{ccc}y\left[n\right]+y\left[n-2\right]=0,& y\left[-1\right]=3,& y\left[-2\right]=2\end{array}$
    4. $\begin{array}{cccc}y\left[n\right]-2.5y\left[n-1\right]-2.44y\left[n-2\right]-0.9y\left[n-3\right]=0,& y\left[-1\right]=1,& y\left[-2\right]=2,& y\left[-3\right]=3\end{array}$

14. 3.14. For each homogeneous difference equation given below, find the characteristic equation and show that it has multiple-order roots. Find the homogeneous solution for n ≥ 0 in each case subject to the initial conditions specified.

    Hint: For parts (c) and (d) use MATLAB function roots(..) to find the roots of the characteristic polynomial.

    1. $\begin{array}{ccc}y\left[n\right]-1.4y\left[n-1\right]+0.49y\left[n-2\right]=0,& y\left[-1\right]=1,& y\left[-2\right]=1\end{array}$
    2. $\begin{array}{ccc}y\left[n\right]+1.8y\left[n-1\right]+0.81y\left[n-2\right]=0,& y\left[-1\right]=0,& y\left[-2\right]=2\end{array}$
    3. $\begin{array}{cccc}y\left[n\right]-1.8y\left[n-1\right]-0.64y\left[n-2\right]+0.512y\left[n-3\right]=0,& y\left[-1\right]=1,& y\left[-2\right]=1,& y\left[-3\right]=2\end{array}$
    4. $\begin{array}{cccc}y\left[n\right]+1.7y\left[n-1\right]-0.4y\left[n-2\right]-0.3y\left[n-3\right]=0,& y\left[-1\right]=1,& y\left[-2\right]=2,& y\left[-3\right]=1\end{array}$

15. 3.15. Solve each difference equation given below for the specified input signal and initial conditions. Use the general solution technique outlined in Section 3.5.2.

    1. $\begin{array}{ccc}y\left[n\right]=0.6y\left[n-1\right]+x\left[n\right],& x\left[n\right]=u\left[n\right],& y\left[-1\right]=2\end{array}$
    2. $\begin{array}{ccc}y\left[n\right]=0.8y\left[n-1\right]+x\left[n\right],& x\left[n\right]=2sin\left(0.2n\right),& y\left[-1\right]=1\end{array}$
    3. $\begin{array}{cccc}y\left[n\right]-0.2y\left[n-1\right]-0.63y\left[n-2\right]=x\left[n\right],& x\left[n\right]{=e}^{-0.2n},& y\left[-1\right]=0,& y\left[-2\right]=3\end{array}$
    4. $\begin{array}{cccc}y\left[n\right]+1.4y\left[n-1\right]+0.85y\left[n-2\right]=x\left[n\right],& x\left[n\right]=u\left[n\right],& y\left[-1\right]=-2,& y\left[-2\right]=0\end{array}$
    5. $\begin{array}{cccc}y\left[n\right]+1.6y\left[n-1\right]+0.64y\left[n-2\right]=x\left[n\right],& x\left[n\right]=u\left[n\right],& y\left[-1\right]=0,& y\left[-2\right]=1\end{array}$

16. 3.16. Consider the exponential smoother explored in Examples 3.6 and 3.14. It is modeled with the difference equation

    $$y\left[n\right]=1\left(1-\beta \right)y\left[n-1\right]+\alpha x\left[n\right]$$

    Let y[−1] = 0 so that the system is linear.

    1. Let the input signal be a unit step, that is, x[n] = u[n]. Determine the response of the linear exponential smoother as a function of α.
    2. Let the input signal be a unit ramp, that is, x[n] = n u[n]. Determine the response of the linear exponential smoother as a function of α.

17. 3.17. Consider a first-order differential equation in the form

    $$\frac{d{y}_a}{dt}+A{y}_a\left(t\right)=A{x}_a\left(t\right)$$

    The derivative can be approximated using the backward difference

    $$\frac{d{y}_a\left(t\right)}{dt}\approx \frac{y_a\left(t\right)-y_a\left(t-T\right)}{T}$$

    where T is the step size.

    1. Using the approximation for the derivative in the differential equation, express ya (t) in terms of ya (t − T) and xa (t).

    2. Convert the differential equation to a difference equation by defining discrete-time signals

       $$\begin{array}{c}x\left[n\right]=x_a\left(nT\right)\\ y\left[n\right]=y_a\left(nT\right)\\ y\left[n-1\right]=y_a\left(nT-T\right)\end{array}$$

       Show that the resulting difference equation corresponds to an exponential smoother. Determine its parameter α in terms of A and T.

18. 3.18. Construct a block diagram for each difference equation given below.

    1. y[n] + 0.2y[n − 1] − 0.63y[n − 2] = x[n] + x[n − 2]
    2. y[n]− 2.5y[n − 1] + 2.44y[n − 2]− 0.9y[n − 3] = x[n] − 3x[n − 1] + 2x[n − 2]
    3. y[n]− 0.49y[n − 2] = x[n]− x [n − 1]
    4. y[n] + 0.6y[n − 1]− 0.51y[n − 2]− 0.28y[n − 3] = x[n] − 2x[n − 2]

19. 3.19. Two DTLTI systems with impulse responses h1[n] and h2[n] are connected in cascade as shown in Fig. P.3.19(a).

    Figure P. 3.19

    

    1. Determine the impulse response heq[n] of the equivalent system, as shown in Fig. P.3.19(b) in terms of h1[n] and h2[n].

       Hint: Use convolution to express w[n] interms of x[n]. Afterwards use convolution again to express y[n] in terms of w[n].

    2. Let h1[n] = h2[n] = u [n] − u[n − 5]. Determine and sketch heq[n] for the equivalent system.

    3. With h1[n] and h2[n] as specified in part (b), let the input signal be a unit step, that is, x[n] = u [n]. Determine and sketch the signals w [n] and y[n].

20. 3.20. Two DTLTI systems with impulse responses h1[n] and h2[n] are connected in parallel as shown in Fig. P.3.20(a).

    Figure P. 3.20

    

    1. Determine the impulse response heq[n] of the equivalent system, as shown in Fig. P.3.20(b) in terms of h1[n] and h2[n].

       Hint: Use convolution to express the signals y1[n] and y2[n] in terms of x[n]. Afterwards express y[n] in terms of y1[n] and y2[n].

    2. Let h1[n] = (0.9)n u[n] and h2[n] = (−0.7)n u[n]. Determine and sketch heq[n] for the equivalent system.

    3. With h1[n] and h2[n] as specified in part (b), let the input signal be a unit step, that is, x[n] = u[n]. Determine and sketch the signals y1[n], y2[n] and y[n].

21. 3.21. Three DTLTI systems with impulse responses h1[n], h2[n] and h3[n] are connected as shown in Fig. P.3.21(a).

    Figure P. 3.21

    

    1. Determine the impulse response heq[n] of the equivalent system, as shown in Fig. P.3.21(b) in terms of h1[n], h2[n] and h3[n].
    2. Let h1[n] = e−0.1n u[n], h2[n] = δ[n − 2], and h3[n] = e−0.2n u[n]. Determine and sketch heq[n] for the equivalent system.
    3. With h1[n], h2[n] and h3[n] as specified in part (b), let the input signal be a unit step, that is, x[n] = u[n]. Determine and sketch the signals w[n], y1[n], y2[n] and y[n].

22. 3.22. Consider the DTLTI system shown in Fig. P.3.22(a).

    Figure P. 3.22

    

    1. Express the impulse response of the system as a function of the impulse responses of the subsystems.

    2. Let

       $$\begin{array}{c}{h}_1\left[n\right]=e^{-0.1n}u\left[n\right]\\ h_2\left[n\right]=h_3\left[n\right]=u\left[n\right]-u\left[n-3\right]\end{array}$$

       and

       $$h_4\left[n\right]=\delta \left[n-2\right]$$

       Determine the impulse response heq[n] of the equivalent system.

    3. Let the input signal be a unit-step, that is, x[n] = u[n]. Determine and sketch the signals w [n], y1[n], y3[n] and y4[n].

23. 3.23. Consider two finite-length signals x[n] and h[n] that are equal to zero outside the intervals indicated below:

    $$\begin{array}{l}x\left[n\right]=0\text{ if }n<N_{x1}\text{ or }n>N_{x2}\\ h\left[n\right]=0\text{ if }n<N_{h1}\text{ or }n>N_{h2}\end{array}$$

    In other words, significant samples of x[n] are in the index range Nx1,...,Nx2, and the significant samples of h[n] are in the index range Nh1,...,Nh2.

    Let y[n] be the convolution of x[n] and h[n]. Starting with the convolution sum given by Eqn. (3.128), determine the index range of significant samples Ny1,...,Ny2 for y[n].

24. 3.24. Let y[n] be the convolution of two discrete-time signals x[n] and h [n], that is

    $$y\left[n\right]=x\left[n\right]*h\left[n\right]$$

    Show that time shifting either x[n] or h [n] by m samples causes the y[n] to be time shifted by m samples also. Mathematically prove that

    $$x\left[n-m\right]*h\left[n\right]=y\left[n-m\right]$$

    and

    $$x\left[n\right]*h\left[n-m\right]=y\left[n-m\right]$$

25. 3.25. Determine the impulse response of each system described below. Afterwards determine whether the system is causal and/or stable.

    1. $y\left[n\right]=\text{Sys}\left\{x\left[n\right]\right\}={\displaystyle \sum _{k=-\infty }^n}x\left[k\right]$
    2. $y\left[n\right]=\text{Sys}\left\{x\left[n\right]\right\}={\displaystyle \sum _{k=-\infty }^n}{e}^{-0.1\left(n-k\right)}x\left[k\right]$
    3. $y\left[n\right]=\text{Sys}\left\{x\left[n\right]\right\}={\displaystyle \sum _{k=0}^n}x\left[k\right]\text{ for }n\ge 0$
    4. $y\left[n\right]=\text{Sys}\left\{x\left[n\right]\right\}={\displaystyle \sum _{k=n-10}^n}x\left[k\right]$
    5. $y\left[n\right]=\text{Sys}\left\{x\left[n\right]\right\}={\displaystyle \sum _{k=n-10}^{n+10}}x\left[k\right]$

MATLAB Problems

1. 3.26. Refer to the homogeneous difference equations in Problem 3.12. For each one, develop a MATLAB script to iteratively solve it for n = 0,..., 19 using the initial conditions specified. Compare the results of iterative solutions to the results obtained analytically in Problem 3.12.

2. 3.27. Refer to Problem 3.3. The cascade combination of the two subsystems will be tested using the input signal

   $$x\left[n\right]={\left(0.95\right)}^{n}cos\left(0.1\pi n\right)u\left[n\right]$$

   Write a script to do the following:

   1. Create an anonymous anonymous function “x” to compute the input signal at all index values specified in a vector “n”.
   2. Implement the cascade system as shown in Fig. P.3.3(a). Compute the signals w[n] and y[n] for n = 0,..., 29.
   3. Implement the cascade system in the alternative form shown in Fig. P.3.3(b). Compute the signals $\overline{w}\left[n\right]$ and $\overline{y}\left[n\right]$ for n = 0,..., 29. Compare y[n] and $\overline{y}\left[n\right]$.

3. 3.28. Repeat the steps of Problem 3.27 using the subsystems described in Problem 3.4.

4. 3.29. Refer to Problem 3.1. Linearity and time invariance of the systems listed will be tested using the two input signals

   $$x_1\left[n\right]=n{e}^{-0.2n}\left(u\left[n\right]-u\left[n-20\right]\right);$$

   and

   $$x_2\left[n\right]=cos\left(0.05\pi n\right)\left(u\left[n\right]-u\left[n-20\right]\right);$$

   Develop a script to do the following:

   1. Express the two input signals by means of two anonymous functions “x1”and “x2”. Each anonymous function should take a single argument “n” which could either be a scalar or a vector of index values.

   2. Express each of the systems described in Problem 3.1 as an anonymous function. Name the anonymous functions “sys1” through “sys5”. Each should take two arguments “n”and “x”.

   3. Compute the response of each system to

      $$\begin{array}{ll}x[n]\hfill & =x_1[n]\hfill \\ x[n]\hfill & =x_2[n]\hfill \\ x[n]\hfill & =x_1[n]+x_2[n]\hfill \\ x[n]\hfill & =5x_1[n]-3x_2[n]\hfill \end{array}$$

      Identify which systems fail the linearity test.

   4. Compute the response of each system to

      $$\begin{array}{c}x\left[n\right]=x_1\left[n-1\right]\\ x\left[n\right]=x_2\left[n-3\right]\end{array}$$

      Identify which systems fail the time-invariance test.

5. 3.30.

   1. Develop a function ss_lbal(..) to iteratively solve the loan balance difference equation explored in Problem 3.10. It should have the following interface:

       bal = ss_lbal(A,B,c,n)

      The arguments are:

      A:	Amount of the loan; this is also the balance at n = 0
      B:	Monthly payment amount
      c:	Monthly interest rate
      n:	Index of the month in which the balance is sought
      bal:	Computed balance after n months

   2. Write a script to test the function with the values specified in Problem 3.10.

6. 3.31. Refer to Problem 3.11.

   1. Develop a MATLAB function ss_sqrt(..) that iteratively solves the nonlinear difference equation given by Eqn. (3.25) to approximate the square root of a positive number A. The syntax of the function should be

       y = ss_sqrt(A,y_init,tol)

      The argument “A” represents the positive number the square root of which is being sought, “y init” is the initial value y[−1], and “tol” is the tolerance limit ∊. The function should return when the difference between two consecutive output samples is less than the tolerance limit, that is,

      $$|y\left[n\right]-y\left[n-1\right]|\le \varepsilon$$

   2. Write a script to test the function ss_sqrt(..) with the values A = 5, A = 17 and A = 132.

7. 3.32. Refer to Problem 3.16 in which the response of the linear exponential smoother to unit-step and unit-ramp signals were found as functions of the parameter α. Consider the input signal shown in Fig. P.3.32.

   Figure P. 3.32

   

   Develop a script to do the following:

   1. Create an anonymous function yu(..) to compute the unit-step response of the linear exponential smoother. It should take two arguments, “alpha”and “n”, and should return the unit-step response evaluated at each index in the vector “n”.
   2. Create an anonymous function yr(..) to compute the unit-ramp response of the linear exponential smoother. Like the function yu(..), the function yr(..) should also take two arguments, “alpha”and “n”, and should return the unit-ramp response evaluated at each index in the vector “n”.
   3. Express the input signal x[n] using a combination of scaled and time shifted unit-step and unit-ramp functions.
   4. Use the anonymous functions yu(..) and yr(..) to compute and graph the output signal y[n]. Try with α = 0.1, 0.2, 0.3 and compare.

MATLAB Projects

1. 3.33. Consider the logistic growth model explored in Example 3.8. The normalized value of the population at index n is modeled using the nonlinear difference equation

   $$y\left[n\right]=r\left(1-y\left[n-1\right]\right)y\left[n-1\right]$$

   where r is the growth rate. This is an example of a chaotic system. Our goal in this project is to simulate the behavior of a system modeled by the nonlinear difference equation given, and to determine the dependency of the population growth on the initial value y[0] and the growth rate r.

   1. Develop a function called ss_lgrowth(..) with the syntax

       y = ss_lgrowth(y_init,r,N)

      where “y_init” is the initial value of the population at n = 0, “r” is the growth rate, and “N” is the number of iterations to be carried out. The vector returned by the function should have the values

      $$\left[y\left[0\right],y\left[1\right],y\left[2\right],...y\left[N\right]\right]$$

      1. Write a script to compute y[n] for n = 1,..., 30 with specified values y[0] and r.
      2. With the growth rate set at r = 1.5, compute and graph y[n] for the cases of y[0] = 0.1, y[0] = 0.3, y[0] = 0.5, y[0] = 0.7. Does the population reach equilibrium? Comment on the dependency of the population at equilibrium on the initial value y[0].
      3. Repeat the experiment with r =2, 2.5, 2.75, 3. For each value of r compute and graph y[n] for the cases of y[0] = 0.1, y[0] = 0.3, y[0] = 0.5, y[0] = 0.7. Does the population still reach equilibrium? You should find that beyond a certain value of r population behavior should become oscillatory. What is the critical value of r?

2. 3.34. Consider the second-order homogeneous difference equation

   $$y\left[n\right]=a_{1}y\left[n-1\right]+a_{2}y\left[n-2\right]=0$$

   with initial conditions y[−1] = p1 and y[−2] = p2. The coefficients a1 and a2 of the difference equation and the initial values p1 and p2 are all real-valued, and will be left as parameters.

   1. Let z1 and z2 be the roots of the characteristic polynomial. On paper, solve the homogeneous difference equation for the three possibilities for the roots:

      1. The roots are real and distinct.
      2. The roots are a complex conjugate pair.
      3. The two roots are real and equal.

      Find the solution y[n] as a function of the roots z1 and z2 as well as the initial values p1 and p2.

   2. Develop a MATLAB function ss_de2solve(..) with the syntax

       y = ss_de2solve(a1,a2,p1,p2,n)

      The vector “n” contains the index values for which the solution should be computed. The returned vector “y” holds the solution at the index values in vector “n”so that the solution can be graphed with

       stem(n,y)

      Your function should perform the following steps:

      1. Form the characteristic polynomial and find its roots.
      2. Determine which of the three categories the roots fit (simple real roots, complex conjugate pair or multiple roots).
      3. Compute the solution accordingly.

   3. Test the function ss_de2solve(..) with the homogeneous difference equations in Problems 3.12a, b, c, d, Problems 3.13a, b, c, and Problem 3.14a and b.

3. 3.35. One method of numerically approximating the integral of a function is the trapezoidal integration method. Consider the function xa (t) as shown in Fig. P.3.35.

   Figure P. 3.35

   

   The area under the function from t = (n − 1)T to t = nT may be approximated with the area of the shaded trapezoid:

   $${\int }_{\left(n-1\right)T}^{nT}{x}_a\left(t\right)\approx \frac{T}{2}\left[x_a\left(nT-T\right)+x_a\left(nT\right)\right]$$

   Let

   $$y_a\left(t\right)={\int }_{-\infty }^t{x}_a\left(\lambda \right)d\lambda$$

   It follows that

   $$y_a\left(nT\right)\approx y_a\left(nT-T\right)+\frac{T}{2}\left[x_a\left(nT-T\right)+x_a\left(nT\right)\right]$$

   If we define discrete-time signals x[n] and y[n] as

   $$\begin{array}{ccc}x\left[n\right]=x_a\left(nT\right),& \text{and}& y\left[n\right]=y_a\left(nT\right)\end{array}$$

   then y[n − 1] = ya(nT − T), and we obtain the difference equation

   $$y\left[n\right]=y\left[n-1\right]+\frac{T}{2}\left(x\left[n\right]+x\left[n-1\right]\right)$$

   which is the basis of a trapezoidal integrator.

   1. Develop a function ss_integ(..) with the following interface:

       val = ss_integ(xa,lim1,lim2,y_init,k)

      The arguments are:

      xa:	Handle to an anonymous function for xa (t)
      lim1:	Lower limit of the integral
      lim2:	Upper limit of the integral
      y_init:	Initial value of the integral
      k:	Number of time steps from lim1 to lim2
      val:	Trapezoidal approximation to the integral

   2. Write a script to test the function with the integrand

      $$x_a\left(t\right)=e^{-t}sin\left(t\right)$$

      and compare its approximate integral with the correct result given by

      $$\int x_a\left(t\right)dt=\frac{1}{2}-\frac{1}{2}{e}^{-t}cos\left(t\right)-\frac{1}{2}{e}^{-t}sin\left(t\right)$$

      Hint: Set the lower limit of the integral to t = 0.

1 cos (a + b) = cos(a) cos(b) − sin (a) sin(b).

2 cos (a + b) = cos(a) cos(b) − sin (a) sin(b) and sin (a + b) = sin(a) cos(b) + cos(a) sin(b).