Signals And Linear And Time-Invariant Systems In Discrete Time

ZIR - the case of di erent, non-zero, real characteristic values Example: Consider the di erence equation: 8k 3, 2y[k 3] 10y[k 2] 12y[k 1] 3f [k 2], with y[ 2] 1 and y[ 1] 3. That is, Q(z) z 2 m 1. 5z 6 (z 3)(z 2) and n 2, P (z) (3/2)z and So, the n 2 characteristic values are z 3, 2 and the ZIR is 8k n 2, yZI [k] c1 3k c2 2k Using the initial conditions to find the scalars c1 , c2 : 1 y[ 2] c1 3 3 y[ 1] c1 3 2 1 c2 2 c2 2 2 1 and . Exercise: Now solve for c1 and c2 . Note: When a coefficient c is worked out to be zero, it may not be exactly zero in practice, and the corresponding characteristic mode z k will increasingly contribute to ZIR yZI over time if z 1 (i.e., an “unstable” mode in discrete time). c 2016 George Kesidis 25 ZIR - the case of not-real characteristic values The characteristic polynomial Q may have non-real roots, but such roots come in complexconjugate pairs because Q’s coefficients ak are all real. For example, if the characteristic polynomial is Q(z) (z 1)(z 2 2z 2) then the characteristic values (Q’s roots) are p p 1, 1 j 3 again recalling j 1. Because we have three di erent characteristic values 2 C, we can specify three corresponding characteristic modes, p p ( 1)k , (1 j 3)k , (1 j 3)k , 8k 0, and construct the ZIR as 8k n p p 3, yZI [k] c1 ( 1)k c2 (1 j 3)k c3 (1 j 3)k c1 ( 1)k c2 2k ekj /3 c3 2k e kj /3 where – c1 2 R and c2 c3 2 C so that yZI is real-valued, and again, – these scalars are determined by the n 3 given (real) initial conditions: y[ 3], y[ 2], y[ 1]. 26

ZIR - not-real characteristic values with real characteristic modes By the Euler-De Moivre identity for the previous example, 3, yZI [k] c1 ( 1)k (c2 c3 )2k cos(k /3) j(c2 c3 )2k sin(k /3) c1 ( 1)k 2Re{c2 }2k cos(k /3) 2Im{c2 }2k sin(k /3) 8k Again, because all initial conditions are real and Q has real coefficients, yZI is real valued and so c3 c2 ) c2 c3, j(c2 c3) 2 R. In general, consider two complex conjugate characteristic values vp jq corresponding to k jk\z two complex-valued characteristic modes z e , where z v 2 q 2 and \z arctan(q/v). One can use Euler’s identity to show that the corresponding real-valued characteristic modes are z k cos(k\z), z k sin(k\z) c 2016 George Kesidis 27 ZIR - the case of repeated characteristic values Consider the case where at least one characteristic value is of order 1, i.e., there are repeated roots of the characteristic polynomial, Q. For example, Q(z) (z 0.75)3 (z and a single root at 0.5. 0.5) has a triple (twice repeated) root at Again, {( 0.75)k } is a characteristic mode because Q( ( 1 .75)( .75)k 1 Also, {k( .75)k } is a characteristic mode because Q( 1 .75)k 0 follows from 1 ( .75)k .75( .75)k ( .75)k 1 .75( .75)k 0. Similarly, (0.5)k is a characteristic mode since ( ( 1 )( 0.75 0.5)(0.5)k 0. 1 )k( .75)k 0 follows from .75)2 k( .75)k 2 1 ( 1.5 (.75)2 )k( .75)k 2 k 1 k( .75) 1.5 k( .75)k (.75)2 k( 0.75)k k 2 (k 2)( .75) 1.5(k 1)( .75)k 1 (.75)2 k( 0.75)k k 2 ( .75) ((k 2) 2(k 1) k) 0. 28

ZIR - the case of repeated characteristic values (cont) Similarly, {k2 ( .75)k } is also a characteristic mode because 1 .75)3 k 2 ( .75)k 0. ( Note that without three such linearly independent characteristic modes {( .75)k , k( .75)k , k2 ( .75)k ; k 0} for the twice-repeated (triple) characteristic value -.75, the initial conditions will create an “overspecified” set of n equations involving fewer than n “unknown” coefficients (ck ) of the linear combination of modes forming the ZIR. For this example, yZI [k] c0 ( 0.75)k c1 k( 0.75)k c2 k2 ( 0.75)k c3 (0.5)k , k If the given initial conditions are, say, y[ 4] 12, y[ 3] 6, y[ 2] 4. 5, y[ 1] 10, the four equations to solve for the four unknown coefficients ck are: yZI [ yZI [ yZI [ yZI [ 4] 3] 2] 1] ( ( ( ( .75) .75) .75) .75) 4 c0 ( c0 ( 2 c0 ( 1 c0 ( 3 4)( 3)( 2)( 1)( .75) .75) .75) .75) 4 c1 ( c1 ( 2 c1 ( 1 c1 ( 3 4)2 ( 3)2 ( 2)2 ( 1)2 ( .75) .75) .75) .75) 4 4 3 3 c2 (.5) c2 (.5) 2 c2 (.5) 1 c2 (.5) c3 c3 2 c3 1 c3 12 6 5 10 29 ZIR - general case of repeated, non-zero characteristic values In general, a set of r linearly independent modes corresponding to a non-zero characteristic value z 2 C repeated r 1 times are kr 1 k z , kr 2 k z , ., kz k , z k , Also, if v jq are characteristic values repeated r we can use the 2k real-valued modes for k 0. 1 times, with v, q 2 R and q 6 0, ka z k cos(k\z), ka z k sin(k\z), for a 2 {0, 1, 2, ., r p where z v 2 q 2 and \z arctan(q/v). 1}, c 2016 George Kesidis 30

ZIR - when some characteristic values are zero Again let n0 n be the number of non-zero roots of Q (characteristic values), i.e., r : n r n0 0 is the order (1 repetition) of the characteristic value 0, and 0 is the smallest index such that (the coefficient of Q) ar 6 0. So, there is a polynomial Q̃ such that Q(z) z r Q̃(z) and Q̃(0) 6 0. Because the constant signal zero cannot be a characteristic mode, we add r n time-advanced unit-pulses: 8k n, yZI [k] r X n0 Ci [k i] yN [k] i 1 Cr [k r] Cr 1 [k r 1] . C1 [k 1] yN [k] where yN is a “natural response” (linear combination of n0 characteristic modes). The n initial conditions are then met by the r coefficients Ci of the advanced unit pulses together with the n0 n r coefficients of the characteristic modes in yN. c 2016 George Kesidis 31 ZIR - when some characteristic values are zero - example Consider a fourth-order system with characteristic polynomial Q(z) z 2 (z 1)2 . Thus the poles are 0, ( 1)k , k( 1)k . 1 each repeated and the (non-zero) characteristic modes are So, the ZIR is, for k 4: yZI [k] C2 [k 2] C1 [k 1] c1 ( 1)k c2 k( 1)k That is, the ZIR has four unknown coefficients C2 , C1 , c1 , c2 to account for the four (given) initial conditions y[ 4], y[ 3], y[ 2], y[ 1]. c 2016 George Kesidis 32

Zero State Response - the unit-pulse response Recall the LTIC system n X r ar y : Q( 1 )y P( 1 )f : r 0 m X r br f r 0 with an 1, a0 6 0 or b0 6 0, m n. We can express any input signal f [k] 1 X f [r] [k r 0 So the unit pulse r] 8k 0, i.e., 8f , f f . is the identity of the convolution operator in discrete time. Thus, by LTI, the ZSR yZS is the convolution of input f and ZSR h to unit pulse , yZS [k] 1 X f [r]h[k r 0 r] (f h)[k], 8k 0, h is called the unit-pulse response of the LTIC system, i.e., Q( 1 1 )h P ( ) s.t. h[k] 0 8k 0. 33 Computing an LTIC system’s unit-pulse response, h For the LTIC system in standard form, if a0 6 0 then h (b0 /a0 ) yN u where yN is a natural response of the system (linear combination of characteristic modes). Note that h[k] 0 for all k 0 owing to the unit step u. The n scalars of the natural response yN component of h are solved using (Q( 1 )h)[k] (P ( 1 ) )[k] for k 2 { n, n 1, ., 2, 1} c 2016 George Kesidis 34

Unit-pulse response when zero is a characteristic value If r 0 is the smallest index such that ar 6 0 (0 is a char. mode of order r), then may need to add r delayed unit-pulse terms to h: h r 1 X Ai i (b0 /ar ) r yN u, i 0 where – by definition of the standard form of the di erence equation, if r 0, a0 0 so b0 6 0, and – r n since 0 6 an : 1. So if r 0 (i.e., a0 6 0), then A0 b0 /a0 as above, where Exercise: Prove Ar b0 /ar for 0 r n. P 1 i 0 (.) : 0. 0, and Thus, zero is a characteristic value of degree r there are r characteristic modes that will all be zero. The additional unit-pulse terms introduce r degrees of freedom in the form of the coefficients A0 , A1 , ., Ar 1 to accommodate the n r n0 initial conditions of the unit-pulse response: h[ n] h[ n 1] . h[ 2] h[ 1] 0. 35 Computing the ZSR - example 1 Recall that the di erence equation y 7f standard form: 8k 3 y corresponds to the above system; in 1, y[k 1] 3y[k] 7f [k 1]. with Q(z) z 3, P (z) 7z and n 1 m. Since the system characteristic value is has the form h[k] c( 3)k u[k]. 3 and b0 0, the (zero state) unit-pulse response The scalar c is solved by evaluating the above di erence equation at time k 1 1: 1 (Q( )h)[ 1] (P ( ) )[ 1] i.e., h[0] 3h[ 1] 7 [0] ) c 3 · 0 7 · 1, c 7 36

Computing the ZSR - example 1 (cont) So, h[k] 7( 3)k u[k]. If the input is f [k] 4(0.5)k u[k], the system ZSR is, for all k yZS [k] k X h[r]f [k r] r 0 k X 0, 7( 3)r 4(0.5)k r r 0 28(0.5)k k X ( 6)r 28(0.5)k r 0 ( 6)k 1 1 u[k] 6 1 (24( 3)k 4(0.5)k )u[k]. Note how the ZIR yZI has a term that is a characteristic mode (excited by the input f ) and a term that is proportional to the input f (this forced response is an eigenresponse). Exercise: For the di erence equation, y[k 1] 3y[k] 7f [k] 8k 1: draw the block diagram, show that h[k] 21( 3)k 1u[k] (7/3) [k], and find the ZSR to the above input f . Exercise: Read “sliding tape” method to compute convolution in Lathi, p. 595. c 2016 George Kesidis 37 Computing the unit pulse response - example 2 Find the ZSR of the following system to input f [k] 2( 5)k u[k]: Exercise: show the di erence equation for this system (in direct canonical form) is: 8k 0, y[k 2] That is, Q(z) z 2 m 1. 5y[k 1] 6y[k] 1.5f [k 1] 5z 6 (z 3)(z 2) and n 2, P (z) 1.5z and So, the n 2 characteristic values are z 3, 2 and b0 0 so the unit-pulse response h[k] (c1 3k c2 2k )u[k]. c 2016 George Kesidis 38

Computing the unit pulse response - example 2 (cont) To find the constants, evaluate the di erence equation at k 2h[1] ) (2 · 3 and at k 2h[0] Thus, c2 2: 10h[0] 12h[ 1] ) 2h[1] 10h[0] 10 · 1)c1 (2 · 2 10 · 1)c2 ) 4c1 6c2 1: 3 [0] 3 3 3 10h[ 1] 12h[ 2] 3 [ 1] ) 12h[0] 0 ) h[0] 0 ) c1 c2 0. 1.5 c1 so that h[k] ( 1.5(3)k 1.5(2)k )u[k] and for k yZS [k] (h f )[k] k X h[r]f [k 0 r]. r 0 Exercise: Write the ZSR as a sum of system modes 2k and 3k and a (force) term like the input, here taken as f [k] 4( 5)k u[k]. c 2016 George Kesidis 39 Convolution - other important properties Again, for a LTI system with impulse response h and input f , the ZSR is yZS f h, where 1 X (f h)[k] f [r]h[k r] r 1 By simply changing the dummy variable of summation to r0 h is commutative: f h h f . r, can show convolution One can directly show that convolution f h is a bi-linear mapping from pairs of signals (f, h) to signals (yZS), consistent with convolution’s commutative property and the (zero state) system with impulse response h being LTI; that is, 8 signals f, g, h and scalars , 2 C, ( f g) h (f h) (g h) By changing order of summation (Fubini’s theorem), one can easily show that convolution is associative, i.e., 8 signals f, g, h, (f g) h f (g h). c 2016 George Kesidis 40

Convolution - other important properties (cont) We’ll use these properties when composing more complex systems from simpler ones. By just changing variables of integration, we can show how to exchange time-shift with convolution, i.e., 8 signals f, h : Z ! C and times k 2 Z, ( k f) h k (f h); recall how convolution represents the ZSR of linear and time-invariant systems. By the ideal sampling property, recall that the identity signal for convolution is the unit pulse , i.e., 8 signals f , f f f Exercise: Adapt the proofs of these properties in continuous time to this discrete-time case. Exercise: In particular, show that if f and h are causal signals, then y f h is causal; i.e., if the unit-pulse response h of a system is a causal signal, then the system is causal. c 2016 George Kesidis 41 System stability - ZIR - asymptotically stable Consider a SISO system with input f and output y . Recall that the ZIR yZI is a linear combination of the system’s characteristic modes, where the coefficients depend on the initial conditions, possibly including some initial unit-pulse terms if zero is a characteristic value (system pole). A system is said to be asymptotically stable if for all initial conditions, lim yZI [k] 0. k!1 So, a system is asymptotically stable if and only if all of its characteristic values have magnitude less than 1. c 2016 George Kesidis 42

System stability - ZIR - asymptotically stable: Example If the characteristic polynomial Q(z) (z 0.5)(z 2 0.0625), then the system’s characteristic values (roots of Q) are 0.5, 0.25j each with magnitude less than one, and the ZIR is of the form, yZI [k] c1 (0.5)k c2 (0.25j)k c2 ( 0.25j)k u[k] c1 (0.5)k 2Re{c2 }(0.25)k cos(k /2) 2Im{c2 }(0.25)k sin(k /2) u[k], recalling that j k ejk /2 . So, yZI [k] ! 0 as k ! 1 for all c1 , c2 (i.e., for all initial conditions), and hence is asymptotically stable. 43 System stability - bounded signals A signal y is said to be bounded if 9 M 1 s.t. 8k 2 Z, y[k] M ; otherwise y is said to be unbounded. p For example, y[k] 0.25( 1 j2 3 k ) u[k] is bounded (can use M 0.25). Also, 3 cos(5k) is bounded (can use M 3). But both 2k cos(5k) and 3 · ( 2)k are unbounded. c 2016 George Kesidis 44

System stability - ZIR - marginally stable A system is said to be marginally stable if it is not asymptotically stable but yZI is always (for all initial conditions) bounded. A system is marginally stable if and only if – it has no characteristic values with magnitude strictly greater than 1, – it has at least one characteristic value with magnitude exactly 1, and – all magnitude-1 characteristic values are not repeated. That is, a marginally stable system has – some characteristic modes of the form cos( k) or sin( k), – while the rest of the modes are all of the form kr z k cos( k) or kr z k sin( k), with z 1 and integer degree r 0. – Exercise: Explain why we can take 2 ( , ] without loss of generality. – Note: the dimension of frequency is [ ] radians per unit time. c 2016 George Kesidis 45 System stability - ZIR - marginally stable: Example The characteristic polynomial is Q(z) z(z 2 1)(z 0, 0.25, j , 0.25) gives characteristic values then the system is marginally stable with modes (0.25)k , cos(k /2), sin(k /2), the last two of which are bounded but do not tend to zero as time k ! 1. c 2016 George Kesidis 46

System stability - ZIR - unstable A system that is neither asymptotically nor marginally stable (i.e., a system with unbounded modes) is said to be unstable. For example, the system with Q(z) (z 2 0.5)(z 3) is unstable owing to the characteristic value 3 with unbounded mode ( 3)k . For another example, if the characteristic polynomial is Q(z) (z 2 1)2 (z 0.5) then the purely imaginary characteristic values j are repeated, and hence the two additional modes k sin(k /2), k cos(k /2) are unbounded, so this system is unstable. Similarly, if Q(z) (z 2 1)2 (z 0.5) then the characteristic values 1 are repeated and the modes k and k( 1)k are unbounded, so this system is unstable too. c 2016 George Kesidis 47 ZIR stability - stability of poles c 2016 George Kesidis 48

System stability - ZSR - BIBO stable A SISO system is said to be Bounded Input, Bounded Output (BIBO) stable if 8 bounded input signals f , the ZSR yZS is bounded. A sufficient condition for BIBO stability is absolute summability of the unit-pulse response, 1 X k 0 h[k] 1. To see why: If the input f is bounded (by Mf with 0 Mf 1) then 8k 0: yZS [k] (f h)[k] k X f [k r]h[r] r 0 k X r 0 k X r 0 Mf f [k r]h[r] (by the triangle inequality) Mf h[r] 1 X r 0 h[r] : My 1, 49 System stability - ZSR - BIBO stable The condition of absolute summability of the unit-pulse response, 1 X r 0 h[r] 1, is also necessary for, and hence equivalent to, BIBO stability. If any component characteristic mode of h is unbounded, then h will not to be absolutely summable. Thus, if the system (ZIR) is asymptotically stable it will be BIBO stable; the converse is also true. c 2016 George Kesidis 50

ZSR - the transfer function, H Recall that for any polynomial Q and z 2 C (including s jw, w 2 R), Q( 1 )z k Q(z)z k , 8k 0. 1 )y P ( 1 )f with So, if we guess that a “particular” solution of the system Q( input f [k] Az k u[k] is of the form yp[k] AH(z)z k H(z)f [k], k 0, then we get by substitution that 8k 0, z 2 C, (Q( 1 )yp )[k] (P ( 1 )f )[k] ) AH(z)Q(z)z k AP (z)z k ) H(z) P (z)/Q(z). The “rational polynomial” H P/Q is known as the system’s transfer function and will figure prominently in our study of frequency-domain analysis. So, the ZSR (forced response characteristic modes) would be of the form: yZS [k] (AH(z)z k linear combination of char. modes)u[k]. Recall that for the example with Q(z) z 3 and P (z) 7z , we computed the unit-pulse response h[k] 7( 3)k u[k] and the ZSR to input f [k] 4(0.5)k u[k] as yZS [k] (24( 3)k 4(0.5)k )u[k]. Here, note that H(0.5) P (0.5)/Q(0.5) 1, i.e., the forced response component of yZS is H(0.5)f [k] 1 · 4(0.5)k u[k] 4(0.5)k u[k]. 51 ZSR - unit-pulse response h, transfer function H , and eigenresponse yZS [k] (H(z)Az k linear combination of char. modes )u[k] is the ZSR to input f [k] Az k u[k], where H(z) P (z)/Q(z). The

Time-domain analysis of discrete-time LTI systems Discrete-time signals Di erence equation single-input, single-output systems in discrete time The zero-input response (ZIR): characteristic values and modes The zero (initial) state response (ZSR): the unit-pulse response, convolution System stability The eigenresponse .