6.1 ECE 410 University of Illinois DIGITAL SIGNAL PROCESSING Chapter 6 D. Munson A.

Singer

z-Transform Representation of Discrete-Time Signals and Systems

Laplace transforms are used extensively to analyze continuous-time (analog) signals as well as systems that process continuous-time signals. As you may recall, the role of the Laplace transform was to represent a large class of continuous-time signals as a superposition of many simpler signals, sometimes called basis functions or kernels. For the Laplace transform, the kernels were complex exponential signals of the form, e st , and we represented signals for which the Laplace transform existed according to the formula st 1 x(t ) = 2 j X ( s )e ds ,
C

where the integral is taken as a line integral along a suitable closed contour C in the complex plane. While the integral form of the inverse Laplace transform can be a powerful tool in the analysis of continuous-time signals and systems, we can often avoid its direct evaluation by algebraically manipulating the expression for X ( s ) such that it can be represented as a sum of terms, each of which can be immediately recognized as the Laplace transform of a known signal x(t ) . Then, using linearity of the Laplace transform, we can construct the inverse transform, term by term. We can view the inverse Laplace transform as a way of constructing x(t ) , piece by piece, from many (an uncountably infinite number, actually) simpler signals of the form e st , where the amount of each such signal contained in the signal x(t ) is given by X ( s ) . To determine how much of each complex exponential signal e st is contained in x(t ) , we have the Laplace transform formula given by
X ( s ) = x(t )e st dt .

For signals that are zero, for negative time, this integral can be taken over positive time, giving the one-sided, or unilateral Laplace transform,
X ( s ) = x(t )e st dt .
0

(0-1)

For many linear time-invariant (LTI) continuous-time systems, the relationship between the input and output signals can be expressed in terms of linear constant coefficient differential equations. The one-sided Laplace transform can be a useful tool for solving these differential equations. For such systems, the Laplace transform of the input signal and that of the output signal can be expressed in terms of a transfer function or system function. In fact, many of the properties, such as causality or stability, of LTI systems can be conveniently explored by considering the system function of the continous-time system. Another helpful property of the Laplace transform is that it maps the convolution relationship between the input and output signals in the time domain to a conceptually simpler multiplicative relationship. In this form, LTI systems can be thought of in terms of how they change the magnitude and phase of each of the kernel signals e st individually, and then the output of the system is given by a superposition of each of these scaled kernel signals.

6.2 For discrete-time signals, we will see that an analogous relationship can be developed between signals and systems using the z-transform. The discrete-time complex exponential signal, z n , where z is a complex number, plays a similar role to the continuous-time complex exponential signal e st . We have already seen that discrete-time signals of this form play an important role in the analysis of linear, constant coefficient difference equations, through the characteristic equation. There is great elegance in the mathematics linking discrete-time signals and systems through the z-transform and we could delve deeply into this theory, devoting much more time than we will be able to here. While our treatment of the z-transform will be limited in scope, we will see that it is an equally valuable tool for the analysis of discrete-time signals and systems. We will use the z-transform to solve linear constant-coefficient difference equations, as well as develop the notion of discrete-time transfer functions. We can then use it to readily compute convolution, and analyze properties of discrete-time linear shift-invariant systems. We note that as with the Laplace transform, the z-transform is a function of a complex variable. The transform itself can also take on complex values. As a result, it is a complex function of a complex variable.

Unilateral (one-sided) z-Transform

Now, we will begin our study of the z-transform by first considering the one-sided, or unilateral, version of the transform. The unilateral z-transform of a sequence { x[n]}n =0 is given by the sum

X ( z ) = x[n] z n ,
n=0

(0-2)

for all z such that Equation (7.1) converges. Here, z is a complex variable and the set of values of z for which the sum converges are called the region of convergence (ROC) of the z-transform. The z-transform maps sequences to functions, such that X ( z ) is the z-transform of the sequence When it is clear that we are discussing sequences defined for non-negative values of the independent time axis, or n-axis, we will write x[n] . The sequences for which the ztransform is defined can be real-valued, or complex valued. As a result, this series will converge whenever | x[n] | grows no faster than exponentially. The region of convergence will be all z outside some circle in the complex z-plane of radius R, the radius of convergence for the series.

{ x[n]}n=0 .

6.3

{z}
R

{z}

Figure 0-1 A typical region of convergence for a z-transform.

When we call X ( z ) the transform of the sequence { x[n]}n =0 , we imply a form of uniqueness for

the z-transform. Namely, we imply that for a given sequence { x[n]}n =0 , there exists one and

only one z-transform X ( z ) and its associated region of convergence. Similarly, for a given ztransform X ( z ) , there exists one and only one sequence { x[n]}n =0 for which the series in Equation (7-1) converges for| z |> R . The uniqueness for z-transform derives from properties of power series expansions of complex functions of complex variables.

Example

Consider the sequence x[n] = 2n , defined for nonnegative n, as shown in the figure below.
35 30 25 20 x[n] 15 10 5 0 0 1 2 3 samples, n

This discrete-time exponential sequence has a z-transform given by

X ( z ) = 2n z n ,
n =0

which can be re-written as

2 X ( z) = . n=0 z To determine the region of convergence, or ROC, of X ( z ) , we need to consider the values of z n

6.4 for which the power series converges. This can be accomplished by recalling the method for summing infinite geometric series. Given a series of the form

S = an
n=0

where a is a complex or real number, we can observe that

S = a n = (1 + a + a 2 + a 3 +
n=0

),

and

aS = a n +1 = (a + a 2 + a 3 +
n=0

),

which leads us to S aS = a n a n +1 = (1 + a + a 2 + a 3 +
n =0 n=0

) (a + a 2 + a 3 +

).

Now, if| a |< 1 , then the terms on the right hand side become negligible leaving the well-known result that 1 S (1 a ) = 1, or S = . (1 a) This is actually a special case of the more general series S= for which we obtain,
n = N1

N2

S= and

n = N1 N2

N2

= (a N1 + a N1 +1 + a N1 + 2 +

+ a N2 ),

aS = a a n = (a N1 +1 + a N1 + 2 +
n = N1

+ a N2 + a N2 +1 ),

leading to S (1 a) = (a N1 a N2 +1 ), or
(a N1 a N2 +1 ) , (1 a ) which holds for all values of a 1 . Note that this holds even for values of a with magnitude greater than 1. When N 2 = , we may consider S=
N 2

lim S = lim

(a N1 a N2 +1 ) , N 2 (1 a )

which for | a |< 1 , yields,

(a N1 a N2 +1 ) a N1 , = N 2 (1 a ) (1 a ) which was the special case we saw before when N1 = 0 . To summarize, we have that lim

6.5
N2

n = N1

an =

(a N1 a N2 +1 ) , for a 1 (1 a )
Equation 0-3

and
a N1 a = (1 a) , for |a |< 1 . n = N1
n

Equation 0-4

Now returning to our example for x[n] = 2n , lets find the ROC for x[n], or ROCX . Is z = 1 in the ROC of X ( z ) ? Is z = 3 in the ROC? First consider z = 1: X (1) = 2n (1) n = 2n ,
n=0 n=0
n

which clearly diverges. Therefore, z = 1 is not in the ROC. Now consider z = 3:

1 2 X (3) = 2 (3) = = = 3. 1 2 n=0 n=0 3 3 Thus, X ( z ) is well defined (finite) at z = 3, so that z = 3 is a point in the ROC X ( z ) .
n n

In this example, we saw that the larger value of z is in ROCX, whereas the smaller value of z is not in ROCX. It should not be a surprise that larger values of z are more likely to be in the ROC. Why so? Because, in the definition of the z-transform, Equation (7-1), z is raised to a negative power and multiplied by the sequence x[n] . Therefore, the z-transform is essentially a sum of the signal x[n] multiplied by either a damped or a growing complex exponential signal z n . Thus, larger values of z offer greater likelihood for convergence of the z-transform sum, since these correspond to more rapidly decaying exponential signals. In general, X(z) converges for all z that are large enough, that is, when z is sufficiently large, that the signal x[n] z n becomes summable. Specifically, X(z) converges for all z such that |z| > R (for some R). Thus, ROCX includes all points z lying outside a circle of radius R, as illustrated in Figure 0-1. To discover the value of R for a given sequence, we need only consider the convergence test that we need to apply when we try to compute the z-transform sum. For our example, we have
2 X ( z) = , n=0 z n

which, applying Equation 0-4, leads to

1 2 2 X ( z) = = , <1 2 z n=0 z 1 z z 1 X ( z) = ,z > , z2 2
n

6.6 that is, the ROC for X ( z ) is |z|>2. We can look at a more general example, such as that considered next.
Example

Consider the sequence x[n] = a n , for n 0, where a is a (possibly complex) constant. To determine the z-transform X ( z ) , we consider the sum a n n X ( z) = a z = , n =0 n=0 z which for | z |>| a | converges to z X ( z) = . za Note that a |a| <1 < 1 | a |<| z | | z |>| a | z |z| Thus, z X ( z) = ,| z |>| a | . za What if |z| < |a|? For any such z, X(z) is undefined because the z-transform sum does not [Link] can also
Linearity

We can also use some elementary calculus to extend some of the relationships developed so far. First, lets show that the z-transform is linear, that is if X 1 ( z ) is the z-transform for the sequence x1[n] and X 2 ( z ) is the z-transform for the signal x2 [n] , then the signal x3 [n] = x1[n] + x2 [n] is given by X 3 ( z ) = X 1 ( z ) + X 2 ( z ) . This superposition property can be shown directly from the definition of the z-transform X 3 ( z ) = (ax1[n] + bx2 [n]) z n
n=0

= ax1[n]z n + bx1[n]z n
n=0 n=0

= aX 1 ( z ) + bX 2 ( z ).

Example

Now, to determine the z-transform of a sequence of the form x[n] = na n , we can use linearity of the transform to obtain the desired result. We have

6.7
X ( z) = n an z n
n =0

d = z an z n , dz n =0 which we can use to obtain the z-transform we want. Note that z ,| z |>| a | an z n = za n =0 d n n ( z a) z a z = ( z a)2 ,| z |>| a | dz n =0
a d ,| z |>| a |, z an z n = 2 dz n =0 ( z a) az d z an z n = ,| z |>| a |, 2 dz n =0 ( z a) which is the transform we wanted. That is, az n an z n = ,| z |>| a | . ( z a)2 n=0 In a similar way we can show the more general result dX ( z ) nx[n] z , dz for X ( z ) the z-transform of x[n]. In a similar manner, we can obtain that 1 a2 z n(n 1)a n ,| z |>| a | , 2 ( z a )3 and m-fold differentiation yields, 1 am z n(n -1) ( n - 2) ... (n - m + 1) a n ,| z |>| a | . m! ( z a ) m +1 Example

We can use linearity of the z-transform to obtain the z-transform for trigonometric functions, such as x[n] = sin( n) , for non-negative n. We begin with Eulers relation, 1 j n j n x[n] = sin( n) = (e e ) , n 0 2j X ( z) = which, applying linearity yields, 1 j n j n n (e e ) z n=0 2 j

6.8
1 1 j n 1 j n z e (z e ( ) ) n =0 2j n=0 z 1 z = ,| z |>| e j |= 1 j j z e 2 j z e

X ( z) =

= = =

1 z ( z e j ) z ( z e j ) ,| z |> 1 j z e j 2j z e 1 z ( z e j ) z ( z e j ) ,| z |> 1 2 j z 2 2 z cos( ) + 1 z sin( ) ,| z |> 1 z 2 z cos( ) + 1

2

We could have shortened our derivation a bit for this example by using the fact that sin( n) is a linear combination of terms of the form a n , and we already know the z-transform of a n . Lets try this approach to find the z-transform of cos( n) .
Example

Find the one-sided z-transform of x[n] = cos( n) .Using Eulers relation, we have that, x[n] = cos( n) 1 j n 1 j n e + e = 2 2 Applying the transforms that we already know, we have that, 1 z 1 z X ( z) = z > e j = 1 , + j j 2 ze 2 ze which implies that 1 2 ( z z e j + z 2 z e j ) 2 , X ( z) = ( z e j ) ( z e j ) = z 2 z cos ,| z |> 1. z 2 2 z cos + 1

Example

From the definition of the z-transform, it should be clear that the unit sample function, 1, n = 0 [ n] = 0, n 0 has the z-transform [n] z 1 .

6.9 Similarly, directly from the definition of the z-transform, the delayed unit sample function, i.e. [n k ], 1, n = k [n k ] = 0, n k has the transform, z k k 0 [ n] 0 k <0 Note that when the delay is negative, that is the unit sample is non-zero only for a negative value of n, then the unilateral z-transform is 0, since this non-zero sample is missed by the unilateral transform. Another sequence that is convenient to provide a unique name for is the unit-step sequence u[n], which is defined as 1 n 0 u[n] = 0 n < 0 The unit-step sequence is pictured as shown below in
unit step sequence

1.8 1.6 1.4 1.2 1 u[n] 0.8 0.6 0.4 0.2 0 -0.2 -5 0 5 n, (samples) 10 15 20

Figure 0-2 Unit step sequence, u[n] = 1, n 0 .

6.10
Properties of 1-Sided z-Transform

We will discuss a few properties of the unilateral z-transform. To facilitate this discussion, we will use the following operator notation for the z-transform, Z ( y[n]) Y ( z ) . The first property has already been shown, and is that of linearity.
Linearity: Proof:
n=0

Z ( ax[n] + by[n]) = aX ( z ) + bY ( z )

( a x[n] + b y[n]) z n = a x[n]z n + b

n =0

y[n] z n

n=0

= aX ( z ) + bY ( z )

The second property is a delay property, that is, when you delay a sequence, what happens to its z-transform.
Delay Property #1: Let k > 0 be the amount of delay. Then Z ( y[n k ] u[n k ]) = z k Y ( z ) In words, this property states that truncating a sequence at the origin, and then shifting to the right by a positive integer k, is equivalent to multiplying the z-transform of the un-shifted sequence by zk. Proof:
Z ( y[n k ] u[n k ]) = y[n k ] u[n k ]z n
n=0

= =

m = k

y[m] u[m]z ( m + k ) , (m = n k ) y[m] u[m]z ( m + k ) , (u[m] = 0, m < 0)

m=0

= z k y[m] z m
m=0

= z Y ( z)

The following delay property can be used to help solve difference equations with initial conditions.
Delay Property #2 For cases where y[-1], y[-2], ..., y[-k] are known or defined (k > 0), we have the following property. Here, the sequence y[n] is not truncated at the origin, prior to shifting. k Z ( y[n k ]) = z k Y ( z ) + y[ m]z m m =1

6.11
Proof:

Z ( y[n k ]) = y[n k ]z n
n =0

y[ ]z (

+k )

,( = n k)

= k

= z k

y[ ]z

= k

1 = z k y[ ]z + y[ ]z = k =0 1 = z k Y ( z ) + y[ ]z = k k = z k Y ( z ) + y[ m]z m , (m = ) m =1

The following sequence advance property can also be used (and will be used more extensively later) in the solution of difference equations.
Advance:
k 1 Z ( y[n + k ]u[n]) = z k Y ( z ) y z =o

Proof:
n=0

y[n + k ]u[n]z n = z k y[n + k ] z ( n + k )

n=0

= z k y[m] z m , (m = n + k ) m=k k 1 = z k y[m] z m y[m] z m m=0 m=0 k 1 = z k Y ( z ) y[m] z m m=0

Inverse 1-Sided z-Transform

One method that can be used to solve difference equations, is to take the z-transform of both sides of the difference equation, and solve the resulting algebraic equation for Y(z), and then find the inverse transform to obtain y[n]. A formula for the inverse unilateral z-transform can be written 1 y[n] = Y ( z ) z n 1dz 2 j

6.12 which is an integral taken over a closed contour in a counter clockwise direction in the region of converge of Y(z).
Im(z)

Re(z)

Other inversion methods exist if Y(z) is a rational function (i.e., a ratio of polynomials), e.g., a0 + a1 z ++ aM z M Y ( z) = b0 + b1 z ++ bN z N Direct division A straightforward, but not entirely practical method, since it does not produce a closed-form expression for y[n], is to employ long-division of the polynomials directly. This is a simple method for obtaining a power-series expansion for Y(z) from the rational expression, and then from the definition of the z-transform, the terms of the sequence can be identified one at a time.
Example

Y ( z) =

z za 1+ a a2 + z z2

za z za 0+a+0 0+a 0+0+

a2 z

a2 z a 2 a3 0+0+ 2 z z Now, from the above series expansion and from the z-transform definition, we obtain that

6.13
Y ( z ) = 1 + az 1 + a 2 z 2 + a 3 z 3 + ... (from the series expansion)
n=0

y[n]z n = y[0] + y[1] z 1 + y[2]z 2 +

which leads to, y[0] = 1, y[1] = a, y[2] = a 2 , y[3] = a 3 ,... from which we may infer the remaining values of the sequence.

z-Transform Properties

A short table of z-transform properties is given below. These can be proven either directly from the definition of the z-transform, or through application of other known properties. Superposition Delay Advance Modulation Multiplication by n Convolution Advance by k Delay by k
n

ax[n] + by[n] x[n k ] x[n + 1]u[n] a n x[n] nx[n]

aX ( z ) + bY ( z ) z k X (k ), k 0 z ( X ( z ) x[0]) X ( a 1 z ) dX ( z ) z dz X ( z )Y ( z )
k 1 z k Y ( z) y z =o k z k Y ( z ) + y[ m]z m m =1

x[k]y[n-k]
k=0

y[n + k ]u[n] y[n k ]

Table 0-1 A short table of z-transform properties.

z-Transform Table

A short table of unilateral z-transforms is given below. These can also be derived directly from the definition of the unilateral z-transform, or through application of the theorems listed in Table 0-1.

6.14
x[n] X ( z) z k X ( z ), k 0 k <0 0, z ( z a) az ( z a)2 az sin( ) 2 z 2az cos + a 2 1 az cos( ) 2 z 2az cos + a 2 z z 1 z k +1 z 1

[n k ] =
an

1, n = k 0 n k

na n a n sin( n) a n cos( n) u[n] = {1, n 0

1, n k , k 0 u[n k ] = n<k 0
Table 0-2 A short table of unilateral z-transforms.

Inverse One-sided z-transform methods: Partial Fraction Expansion (PFE)

One method for finding the inverse of a unilateral (one-sided) z-transform is to recognize the transform of interest as the transform of a signal whose z-transform you already know, or have access to via a lookup table, such as that found at the end of the last chapter. For example, if you know that the transform of the unit-sample (or discrete-time impulse) is X ( z ) = 1 , then given a transform of the form X 2 ( z ) = 2 + z 1 , you might use the linearity property of the z-transform together with the delay property to identify x[n] = 2 [n] + [n 1] . This method is sometimes referred to as the table lookup method. We can generalize this idea to find the inverse transform of more elaborate functions by learning how to decompose complex expressions into a linear combination of terms, each of which we might be able to identify their inverse by inspection. This simply amounts to using linearity to break a complex transform into a sum of simpler terms, and then using a lookup table to find the inverse of each of the terms independently. The overall inverse transform would then be the sum of the inverses of each of the simpler terms, exploiting the linearity of the transform. The inverse transform method we will describe will work well in the case when X ( z ) is a rational function, that is, when it can be expressed as a ratio of finite order polynomials in z . The method is based on the notion that every rational function can be expanded in terms of partial fractions. If the rational function X ( z ) is proper, that is, the degree of the numerator polynomial is less than the degree of the denominator polynomial, and if the roots of the denominator polynomial are distinct, then we can factor X ( z ) in the form

6.15 a0 + a1 z ++ aM z M a0 + a1 z ++ aM z M , = b0 + + bN 1 z N 1 + z N ( z r1 )( z r2 ) ( z rN )

X ( z) =

. where, here, X ( z ) is proper if M < N , and the roots of denominator polynomial are {ri } iN =1 When the ri are distinct (or simple), then, we can write N Ai , X ( z) = i =1 z ri where the constants Ai are called the residues of X ( z ) . In this form, we can use a simple method to find the residues when all of the roots are distinct. We see that they can be obtained by the formula

Ai = ( z ri ) X ( z )
since the term

( z ri ) makes each term in the sum become zero when evaluated at z = ri , except for the one term in the sum that had ( z ri ) in the denominator. This term is has Ai in the

z = ri

,(9.1)

numerator, and hence yields the formula above. Once we have expanded X ( z ) in this form, we can then read off the inverse transform as N N N Ai z n 1 = z 1 Ai x[n] = Ai ri u[n 1] , X ( z) = z ri i =1 z ri i =1 i =1 once again using a combination of the linearity property of the unilateral z-transform and the delay property. We can see how this works in practice by looking at an example.
Example

We can use this approach to find the inverse transform for the following unilateral z-transform: z 1 Y ( z) = ( z 2) ( z 3) Now we wish to find the signal y[n], n 0. We have that

Y ( z) =
Applying the (9.1), we have that

z 1 A1 A2 = + . ( z 2)( z 3) ( z 2) ( z 3) z 1 z 3 A2 ( z 2) ( z 3)

Y ( z )( z 2) =

= A1 + which, when evaluated at z = 2 , yields,

A1 =

z 1 z 3 z = 2

= 1.

6.16 Similarly, we have that

A2 = Putting these together yields that 1 2 + z 2 z 3 z z 1 = z 1 + 2z . z2 z 3 From the table of unilateral z-transform pairs, we have that z an , za Y ( z) = and applying the Delay Property #l, we know that z . za Therefore, we can use the linearity of the transform to invert each of the terms individually, and add the result, to obtain n 1 y[ n] = ( 2 ) u[ n 1] + 2 ( 3n 1 u[n 1]) . a n 1u[n 1] z 1 If we prefer, we can rewrite this as 1 n 2 n 2 + 3 y[n] = 2 3 0 n 1 n=0 z 1 z2 z =3

= 2.

We can avoid the need to apply the delay property to each term, by expanding z 1Y ( z ) in a PFE as B Y ( z ) B1 B = + 2 + 3 . z z z 2 z 3 Then, we can obtain Y ( z ) as Bz Bz Y ( z ) = B1 + 2 + 3 . z 2 z 3 Now, each individual term is easy to invert. Working out the details for this example, we obtain Y ( z) z 1 = z z ( z 2) ( z 3) B B B = 1+ 2 + 3 , z z 2 z 3 and that z 1 1 = , B1 = ( z 2) ( z 3) z =0 6 B2 = z 1 z ( z 3) 1 = , 2 z =2

6.17 z 1 z ( z 2) 2 . 3

B3 = Putting these together, yields,

=
z =3

2 1 Y ( z) 1 = 6 2 + 3 , z z z 2 z 3

or that
2 1 1 z z 6 z 2 + 3 . z z 2 z 3 We can again invert each term and add the results to obtain

Y ( z) =

1 1 2 y[n] = [n] 2n u[n] + 3n u[n] , 6 2 3 Where we have identified that the inverse transform of a constant is a discrete-time impulse. This can be obtained either from the table of transforms, or by noting that if a z-transform is constant, say X ( z ) = C , then we have that X ( z ) = C = x[0] + x[1]z 1 + x[2]z 2 + x[3]z 3 + The only way the right side can be constant (i.e., independent of the value of z) is if C n = 0 x[n] = . 0 n > 0 Thus, 1 n=0 1 6 6 n>0 0 This finally yields that 1 n 2 n 2 + 3 n 1 2 3 y[n] = 1 1 + 2 n=0 6 2 3 1 n 2 n 2 + 3 n 1 y[n] = 2 3 n=0 0 as we had before. In this example, the PFE for z 1Y ( z ) was more complicated (involved one more term) than the PFE for Y ( z ) . In many cases this extra complication does not arise. If the numerator of Y ( z ) contains a power of z (say z or z2), then the z in the denominator of z 1Y ( z ) is cancelled, in which case the PFE for z 1Y ( z ) has exactly the same form as the PFE of Y ( z ) . If the ri are not distinct, we will need to modify the partial fraction expansion slightly. Suppose rj is a root that is repeated q times. We then must replace the single term corresponding to rj

6.18 with a set of q terms, one for each occurrence of the root, where the denominator is raised to each power, starting from the first power up to the qth power, i.e. we replace q Aj Bi i ( z rj ) i =1 ( z r ) j in the partial fraction expansion, where the new constants satisfy q 1 d q i Bi = z r Y ( z) ( ) j q i (q i )! dz z=r

j While it is important to know that this formula exists, in practice, the form of the expansion is more important than the explicit formula for determination of the constants. For example, you can determine the constants by simply matching terms in the expansion as shown in the next example.

Example

Determine the partial fraction expansion of the z-transform z Y ( z) = ( z 1) ( z 3) 2 To accomplish this, we need only know the form of the expansion, and not dwell on the formula for the constants of the repeated roots. First, we obtain A3 Y ( z) 1 A1 A2 = = + + 2 z ( z 1) ( z 3) ( z 1) ( z 3) ( z 3) 2 as the form of the partial fraction expansion. We can now obtain the first term directly, using the non-repeated roots formula 1 1 = , 2 ( z 3) z = 1 4 which gets us started. Now, we find A3 before we find A2. In general, if we find the coefficient over the highest power denominator first, the resulting algebra will be simplified. By multiplying both sides of the PFE by (z3)2 we obtain Y ( z )( z 3) 2 1 A ( z 3) 2 = = 1 + A2 ( z 3) + A3 , z ( z 1) ( z 1) which upon evaluation at z = 3 gives, 1 1 A3 = = . z 1 z = 3 2 Now, one way to find A2 is to first differentiate the PFE with respect to z, yielding 2 A1 ( z 3) ( z 1) A1 ( z 3) 2 1 = + A2 ( z 1) 2 ( z 1) 2 which, upon evaluating both sides at z = 3 yields 1 1 = . A2 = 2 ( z 1) z = 3 4 A1 =

6.19 Another way to obtain A2 is to simply fill in the known constants, and cross multiply the PFE, yielding 1 1/ 4 A2 1/ 2 = + + 2 ( z 1) ( z 3) ( z 1) ( z 3) ( z 3) 2 1 (1/ 4)( z 3) 2 + (1/ 2)( z 1) + A2 ( z 1)( z 3) = ( z 1) ( z 3) 2 ( z 1)( z 3) 2 1 = (1/ 4)( z 3) 2 + (1/ 2)( z 1) + A2 ( z 1)( z 3) Now, we notice that the right hand side has two terms containing z2, one of which contains A2. Since these terms must sum to zero (since the left hand side has no such terms) we again obtain that 1 A2 = . 4 Substituting the values of the constants into the PFE, we have (1/ 4) z (1/ 4) z (1/ 2) z Y ( z) = + . ( z 1) ( z 3) ( z 3) 2 The first two terms are easy to invert. For the third term, recall that az na n ( z a)2 Therefore, we have 1 1 1 1 y[n] = (1) n (3) n + n(3) n 4 4 2 3 1 1 1 = (3) n + n(3) n 4 4 6 Consider another example.
Example

Given the following z-transform, find the sequence y[n]. 2 z3 + z2 z + 4 Y ( z) = ( z 2)3 Recall that for a strictly proper rational function, we require that the degree of the numerator polynomial be strictly less than the degree of the denominator polynomial. This condition is necessary for us to use the form of the partial fraction expansion we have considered thus far. We can use the PFE form if we choose to expand Y ( z ) / z in PFE, since this will be a strictly proper rational function. We begin with Y ( z) 2 z3 + z 2 z + 4 = z z ( z 2)3 A A A3 A4 = 1+ 2 + + 2 z z 2 ( z 2) ( z 2)3 and immediately note that

6.20 2 z3 + z2 z + 4 1 = . 3 ( z 2) 2 z=0 Now, we again find the coefficient of repeated-root term with highest power denominator first. Mutliplying Y ( z ) / z by ( z 2 )3, we obtain A1 = 2 z3 + z2 z + 4 ( z 2)3 = + A2 ( z 2) 2 + A3 ( z 2) + A4 z 2z which can be evaluated at z = 2 to obtain A4, yielding 16 + 4 2 + 4 = 11 . A4 = 2 Expanding the PFE and cross multiplying terms, yields, ( z 2)3 2 z3 + z 2 z + 4 = + A2 z ( z 2) 2 + A3 z ( z 2) + 11z 2 We can now match terms with the same powers of z to obtain two equations in the remaining two unknowns: ( z 2)3 2 z3 + z 2 z + 4 = + A2 z ( z 2) 2 + A3 z ( z 2) + 11z 2 3 5 z 2 z 3 = + A2 z 3 A2 = 2 2 2 6z 5 z2 = + (4) z 2 + A3 z 3 A3 = 8 2 2 Putting the terms all together, yields, 5 z 1 8z 11 z + . Y(z) = + 2 + 2 2 ( z 2) ( z 2)3 z2 Now, we can invert each of the terms one by one and use linearity of the transform to obtain y[n]. First we have 1 n=0 1 1 Z = 2 2 0 n 1 for the first term. For the second and third terms we have 5 2z 5 n 1 Z 2 n 0, = 2 z 2 8z 1 = 8 n 2n n 0. Z1 2 2 ( z 2) To find the inverse transform of the fourth term, we use that 1 a2 z n (n 1) an , 2 ( z a )3 which yields

6.21
11 z 1 = (11) (n 1) n (2)n2 n 0. Z1 3 2 ( z 2) Combining all of the terms yields the result: 2 y[n] = 1 (11n2 + 21 n + 20 ) 2n 8 n=0 n 1

Two-Sided z-Transform
When the input to a discrete-time LSI system is of the form zn for all n, i.e. the two-sided sequence that has non-zero terms for arbitrarily large positive and negative n, the output of the system is simply a scaled version of the input. This is the eigenfunction property of LSI systems in discrete-time. The eigenfunction property of continuous-time systems tells us that when the input to a continuous-time LTI system is of the form est for all t, then the output will be a scaled version of the input. This is easily shown as a consequence of the convolution integral for LTI systems
y (t ) = h( ) x(t )d ,

where h() is the impulse response of the continuous-time LTI system. Letting the input take the form of a complex exponential, we have
y (t ) = h( )e s ( t ) d

= e st h( )e s d

= H ( s )e st when the integral exists. We call the signals of the form est eigenfunctions of continuous-time LTI systems, since they satisfy the property that, when taken as input to an LTI system, they produce an output that is identical except for a (possibly complex) scale factor. The scale factor H(s) is called the eigenvalue associated with the eigenfunction. Note that eigenvalue for a given s is the same as the Laplace transform of the impulse response, evaluated at that value of s. The only signals that have this property, i.e. the only eigenfunctions for LTI systems, are signals of the form est , for different possible values of the complex parameter s. Note that sinusoids are not eigenfunctions for LTI systems! That means that if a sinusoid is input to an LTI system, the output will not be a simple scaled version of the input. However, since a sinusoid can be simply constructed as a sum of two such eigenfunctions, we can easily see what the output will be:

y (t ) = h( ) cos( (t ))d
j ( t ) y (t ) = h( ) 1 + e j ( t ) ) d 2 (e

= =

1 2 1 2

e j t h( )e j d + e j t h( )e j d
j t

(e

H ( j ) + e j t H ( j ) ) .

6.22 Now, if the impulse response is a purely real-valued function, then its Fourier transform will have complex conjugate symmetry, such that j t y (t ) = 1 H ( j ) + e j t H * ( j ) ) 2 (e
j t =1 + e j t ) 2 H ( j ) ( e

=| H ( j ) | cos( t + H ( j )). While the output is not simply a scaled version of the input, when we decompose the sinusoid into a sum of two eigenfunctions, we can use linearity of the LTI system to construct the output as a sum of the two eigenfunction outputs. Returning to discrete-time LSI systems, when the input to an LSI system is of the form zn for all n, the convolution sum yields that
y[n] =
m =

h[m]z
m = n

nm

= zn

h[m]z

= z H ( z) when the sum converges. Once again, we call signals of the form zn eigenfunctions of discretetime LSI systems, and the associated eigenvalues, H( z), correspond to the two-sided z-transform of the impulse response, evaluated at the particular value of z. We define the two-sided z-transform of a sequence y[n] as follows Y ( z) =
n=

y[n]z n ,

for values of z for which the sum converges. We call the values of z for which the sum converges the region of convergence of Y(z), or simply the ROCY. Note that as with the unilateral z-transform, the two-sided (or bilateral) z-transform is again a complex function of a complex variable, meaning that it can take on complex values and that its argument is itself a complex variable. For the two-sided transform, we can consider again a few example sequences for which the sequence values are non-zero for both positive and negative index values.
Example
a n n 0 y[n] = n = a n u[n] + b n u[ n 1] . b n < 0 Now, using the definition of the z-transform, we have for this sequence,

6.23

Y ( z) =

n=

bn z n + a n z n
n=0 k k n

a = b z + k =1 n=0 z
k

1 a z , < 1 | z |>| a | = 1 + + a z k =0 b 1 z z 1 1 , < 1 | a |<| z |<| b | = 1 + + z a b 1 1 b z where we must combine the two conditions on |z|, to ensure convergence of both of the summations in the expression. Otherwise, one of the terms in the expression will be invalid, and the resulting algebraic expression will not be meaningful. b z b z + + Y ( z) = ,| a |<| z |<| b | z b z b z a z z = + ,| a |<| z |<| b | z b z a Note that the region of convergence, ROCY, in this case is a ring, or annulus, in the complex plane.

Im(z)

O R

C
R Re(z) R+

In this example, R = |a|, R+ = |b|. If |a| |b| then ROCY would be the empty set and z-transform would be undefined (i.e. is infinite) for all z. The reason that the region of convergence turns out to be a ring in the complex plane comes from properties of the summations that were assumed to converge in deriving the algebraic expression for the resulting z-transform. Specifically, looking at the definition of the z-transform, we obtain

6.24

Y(z) =

n=

y[n] z

y[n]z
n=0

Note that R is determined by y[n], n 0 and R+ is determined by y[n], n < 0 . If y[n]= 0, for n < 0, then Y ( z ) = y[n] z n and R + = ,
n=0

converges for converges for z large enough, i.e., z small enough |z| > R i.e., for |z| < R+

which is essentially a one-sided (unilateral) z-transform. As a result, the region of convergence corresponds to ROCY Im(z)

ROC
R Re(z)

If y[n] = 0, for n > 0, then we have that Y ( z) =

n=

y[n] z n and R = 0,

and that the region of convergence corresponds to a solid disk in the complex plane, i.e. we have ROCY:

6.25
Im(z)

iu rad

sR

Re(z)

Note that in contrast to the one-sided z-transform, the two-sided z-transform can accommodate a wider range of signal behaviors (since they can be left-sided, right-sided, or two-sided). As such, we must state ROC for Y(z) to uniquely identify y[n]. A right-sided sequence is one that is zero for all n before some index, i.e. y[n] = 0, n < n0 , for some n0. A left-sided sequence is zero for all n after some index, i.e. y[n] = 0, n > n0 , and a twosided sequence is one that has non-zero terms for arbitrarily large positive and negative indices. Examples include u[n], the unit step sequence, which is right sided, u[-n], which is left sided, and a |n| ,

which is two sided. Since the two-sided z-transform multiplies the sequence y[n] by z n and then sums the resulting modulated sequence for each value of z, in Y(z), then whether a sequence is left-sided, rightsided or two-sided play an important role in the convergence (and the ROC) of the z-transform. Specifically, a right-sided sequence will have an infinite number of terms for large positive n, and, hence, the z-transform can converge when the magnitude of z is sufficiently large that z n dominates, making the sequence convergent. Therefore, right-sided sequences will have a ROC that is the entire z-plane outside of a circle of some radius (with the possible exception of infinity). Similarly, a left-sided sequence can converge when the magnitude of z is sufficiently small, such that z n, for large negative n decays sufficiently rapidly to dominate, making the series convergent. Therefore, a left-sided sequence will have a ROC for a disc-shaped region in the complex plane (with the possible exception of zero). A two-sided sequence, having both left-sided and right-sided elements must balance the effects such that the ROC will result in an annulus in the complex plane.

Example
n ( a ) n < 0 x[n] = n0 0 0 n < 0 y[n] = n a n 0

For x[n], we have

6.26
X ( z) = an z n
n=

= a k z k
k =1

z z a = , <1 z a 1 a z ,| z |<| a | = za

Similarly, we have that z ,| z |>| a | . za So, we see that the algebraic form of X(z) and Y(z) are identical, but they are not the same functions, since they are defined on completely different regions of the complex plane. The ztransform of a sequence is not simply defined by the algebraic expression alone, but rather, the combination of the algebraic expression together with the region of convergence. In order to uniquely specify a sequence from its z-transform, we must include both the algebraic form as well as the region of the complex plane over which the form is valid. uniquely defined sequence z-transform and region of convergence z ,| z |>| a | a nu[n] za z ,| z |<| a | a n u[n 1] za Y ( z) =
Poles and Zeros When sequences correspond to z-transforms that are rational functions (ratios of finite-order polynomials in z), we can explore some of the properties of the sequences and their z-transforms by examining the roots of the numerator and denominator polynomials. These are referred to as the zeros and the poles, respectively, of a rational z-transform. Specifically, for a z-transform given by B( z ) , z ROC X , X ( z) = A( z ) we refer to the values of z such that B(z) = 0, as the zeros of X(z), and the values of z for which A(z) = 0, as the poles of X(z). That is, zeros: {z : B ( z ) = 0}

poles: {z : A( z ) = 0} for rational X(z) = B(z) / A(z). Rational z-transforms always have ROCs that are bounded by poles. This means that the ROC is either a disc, an annulus, or the entire plane minus a disc, with the possible exclusion of zero and infinity.

6.27
Example

Consider the rational transform z |z| > 1, z 1 which has a pole at z = 1. This corresponds to the sequence y[n] = u[n]. The region of convergence is as shown below. Im(z) Y ( z) =

Re(z)

Example

Consider the sequence with rational transform z |z| < 2, Y ( z) = z2 which has a pole is at z = 2. This corresponds to the sequence y[n] = - (2)n u[-n-1]. The region of convergence is now the disk shown below. Im(z)

Re(z)

6.28
Example

Now consider the sequence with rational transform z Y ( z) = |z| < 2, ( z 2) 2 which has a second-order pole at z = 2. For multiple poles and a left-sided sequence, we use the same methods we did for the right-sided case. We can easily show that az na n u[ n 1] |z| < |a|. ( z a)2 Thus, 1 y[n] = n(2) n u[n 1]. 2 Example Now consider the sequence with rational transform given by z z Y ( z) = + ,1 <| z |< 2, z 1 z 2 which has poles at z = 1 and z = 2. The region of convergence is an annulus in the complex plane, and the sequence will turn out to be two sided, n0 1 y[n] = n 2 n < 0
= u[n] 2n u[ n 1]. The region of convergence is depicted in the figure below.
Im(z)

Re(z)

Example Consider the sequence given by

1 x[n] = , < n < . 3 Does X(z) exist? Examine the z-transform from the definition, we have that
1 1 X ( z) = z n + n=0 3 n=
n

1 n z . 3

6.29 The first sum converges for |z| > 1/3 and the second sum converges for |z| < 1/3. There is no z for which both sums converge. Thus, X(z) does not exist for any z. The z-transform of this sequence cannot be defined, since the sums do not converge.
Example Consider the two-sided sequence defined by n 1 x[n] = 3 What is X(z)? In this case, we can write

< n < .

1 n 3 x[n] = n 1 3
n

n0 n<0

1 = u[n] + (3) n u[ n 1]. 3 We can transform the right-sided and left-sided pieces individually, and add the results, by linearity of the transform, taking into account the regions in the complex plane for which the series will converge. Since each series has a different region of convergence, we need to consider, for the total sequence, only that portion of the complex plane that is common to both the ROC for the right-sided part and the left-sided part. That is, we need to know for which values of the complex plain will the total z-transform converge. This leads us to the following transform for the sequence:

1 3 This transform brings to bear an important property of the region of convergence for a two-sided z-transform. If the algebraic form for a z-transform is A(z), e.g.,X(z) = A(z), z ROCX, where, N ( z) A( z ) = , ( z p1 )( z p2 ) ( z pN ) then ROCX is generally smaller than the set of z where A(z) alone is well defined. Indeed, A(z) is well defined at all z except the pole locations z = pi, 1 i N, whereas ROCX must be a ring in the complex plane. It is important to remember that the z-transform of a sequence is not defined solely by an algebraic expression, but rather by the combination of an algebraic expression and the region of the complex plane over which the expression is correct. Outside of this region, the algebraic expression is not the z-transform of the sequence of interest. Some points to remember are that z 1) Poles cannot lie in ROCX (because even A(z) is undefined at the pole locations). 2) ROCX is generally smaller than the set of z where A(z) is defined. 3) The z-transform, X(z), is given by the pair of A(z) and the ROCX.

X ( z) =

z 1 , < | z| < 3 . z 3 3

6.30 Another example that will illustrate this point follows. 1 Example x[n] = u[n]. The z-transform of the sequence can readily be found to be 2 1 z ,| z |> . X ( z) = 1 2 z 2 The algebraic form for X(z) is defined everywhere except at z = 1 / 2 , and yet the z-transform is not defined for |z| 1 / 2 . For example, consider z = 1 / 4. We can evaluate the algebraic expression to be z = 1 . 1 z 2 z=1 4 1 However, this does not imply X ( 4 ) = 1 . Indeed, z = 1 4 is not in ROCX, i.e.
n

X( ) =
1 4

n=

1 n u[n]z 2

z=

= 2n , 1
4 n=0

which fails to converge.

Properties of 2-Sided z-Transform

1. Linearity: Z[{a xn + b y n}] = a X(z) + b Y(z)

ROC usually equals ROCX ROCY Sometimes is larger.

Example

Let wn = xn + yn with X(z) = z (z + 2) (z + 3) 2 z+2 |z| < 2 z + 2(z + 3) (z + 2)(z + 3) |z| < 2

Y(z) =

W(z) = X(z) + Y(z) =

6.31 = 3 3(z + 2) = (z + 2)(z + 3) z + 3

ROC = ? Know two facts: i) ROC bounded by poles ii) ROC contains ROCX ROCY For this ex., pole = 3 For this ex., ROCX ROCY = {z : |z| < 2}

x
3 radius = 2

ROC = {z: |z| < 3}

So, ROC can be larger than intersection if have pole-zero cancellation on boundary of intersection, in which case the ROC expands outward or inward to be bounded by another pole. 2. Shift:
k Z {yn k } n= = z Y(z)

ROC = ROCY except for possible addition or deletion of z = 0, or |z| = .

Example

yn = n2 Y(z) = z2

|z| > 0 0 |z| <

y n = yn+3 = n+1 Y(z)= z

6.32 So, ROC Y includes z = 0 whereas ROCY does not. Similarly, ROCY includes |z| = (more precisely, lim Y(z) is finite) whereas ROC Y does not.
|z|

Proof of Shifting Property Z

{yn + k } n=
=

n =

yn+k zn

=n+k

yl z(lk)

= zk

yl zl = zk Y(z)

3. Convolution: yn =

m =

hm xnm

iff

Y(z) = H(z) X(z) ROCY contains ROCH ROCX ROCY can be larger than if have cancellation of pole on boundary of . If have cancellation, then ROC expands out to next pole.
Example

Y(z) = H(z) X(z)

H(z) =

1 (z + 1)(z + 2) z +1 z+2

1 < |z| < 2

X(z) = ROCH ROCX = {z: 1 < |z| < 2} But ROCY = {z: |z| < 2}.

|z| < 2

6.33 Proof of Convolution Formula Just show direction, steps reversible. yn = hn * xn Y(z) =
h x m nm z n n = m =

m =

h m x nm z n
n=

m =

hm

k =

xk z (k +m )

k=nm =

m =

hm

z m

k=

x k z k

= H(z) X(z) Note: Soon we will use z-transform to compute convolution of 2-sided sequences. Then we will need ROCY to invert Y(z).
Definition

The transfer function of an LSI system is H(z) = Y(z) X(z) zero ICs Y(z) is independent of xn!) X(z)

(For LSI systems

hn} . Can get H(z) directly from block diagram and compute Z1 to find {

Example

6.34
xn z1 3
hn} . Find H(z) and {

yn z1 1

yn = yn1 + xn + 3 xn1 Y(z) = z1 Y(z) + X(z) + 3 z1 X(z) Y(z) [1 + z 1] = X(z) [1 + 3z 1 ] H(z) = H(z) = Y(z) 1 + 3z 1 z + 3 = = X(z) z +1 1 + z 1 3 z + z +1 z +1

Assume causal system (difference equation recurses in forward direction, as written). hn right-sided hn = (1)n un + 3(1)n1 un1 0 = 1 2(1)n n<0 n=0 n>0

This is the same answer we found before by solving the D.E.

6.35
Inverting 2-Sided Z-Transform

Main thing to remember:

Im(z) ROC R R+ Re(z) piRHS

piLHS

Here piRHS are poles in PFE in terms that correspond to RHS [{yn }]. piLHS are poles in PFE in terms that correspond to LHS [{yn }].
Why are piRHS inside the ROC doughnut? Why are piLHS outside the ROC doughnut? Answer: Know ROC associated with Z[RHS{ yn} ] must have looked like:
Im(z)

R Re(z)

z : | z | > R }. i.e., ROC = {

6.36 Since poles pRHS associated with Z[RHS{ yn} ] cant be in ROC, they must satisfy i

R. Similarly, ROC associated with Z[LHS{ y n }] must look like: 0 pRHS i

Im(z) R+

ROC

Re(z)

R+ they must satisfy pLHS i

Bottom line: a) 0 pRHS R i b) pLHS R+ i
Example

i.e., ROC = { z : | z | < R+ }. Since poles pLHS associated with Z[LHS{ y n }] cant be in ROC, i

Y(z) =

z (z 1)(z 2)

Cannot invert Y(z) unless someone tells us ROCY. Are three possibilities: 1) ROCY = {z : |z| < 1}

{ y n } is left-sided
2) ROCY = {z : 1 < | z | < 2}
y n }is 2-sided {

6.37 3) ROCY = {z : |z| > 2}

y n } is right-sided {

Find PFE: Y(z) A B 1 = = + z (z 1)(z 2) z 1 z 2 A=1,B=1

Y(z) =

z z + z 1 z 2

Now, to invert terms in PFE, need to know ROCY. Three possibilities. 1) ROCY = {z : |z| < 1}

z-plane

{y n } left-sided
1 2 n yn = 0
n<0 n0

2) ROCY = {z : 1 < |z| < 2}

z-plane

6.38

{y n } is 2-sided where pole at z = 1 caused by RHS {y n } and pole at z = 2 caused by y n }. LHS {

2 n yn = 1
n<0 n0

3) ROCY = {z : |z| > 2}

z-plane 1

{y n } right-sided
n<0 0 yn = 1 + 2 n n 0

Again, someone must tell us which of the ROCs is the correct one if we hope to find { y n }.
Example

Y(z) =

z (z 2)(z 3)(z 4)

2 < |z| < 3

z-plane

6.39

RHS: 2 ; LHS: 3, 4 PFE: 1 1 z z z Y(z) = 2 + 2 z3 z2 z4 RHS LHS LHS

1 2n n0 2 yn = 1 3n 4 n n < 0 2

Example

Given X(z), find { x n } n = . X(z) = = X(z) = z = Know C = B* A= 1 =1 (z + j)(z j) z = 0 1 1 = 2 z (z j) z = j 1 2

z2

1 + 1)

|z| < 1

1 (z + j)(z j) 1 z(z + j)(z j) A B C + + z z+j z j

B =

C = B* =

6.40

X(z) = 1

z+j

1 z 2

1 z 2

z j
radius = 1

LHS since |pole| R+

0 xn = 1 1 1 ( j)n + ( j)n 2 2

n>0 n=0 n<0

Now, since xn is a sum of two complex-conjugate terms, we can express xn in real form. Write j n j n (j)n + (j)n = e 2 + e 2
jn j n 2 =e +e 2

= 2 cos

n 2

0 n>0 n=0 xn = 1 cos n n < 0 2

n>0 0 cos n n 0 2