Skip to content
Textbook Guides

Solution Manual for Adaptive Filter Theory, 5th Edition

Solution Manual for Adaptive Filter Theory, 5th Edition provides you with expert textbook solutions that ensure you understand every concept thoroughly.

Preview 16 of 423 pages

See the first 16 pages exactly as they appear in the document.

  1. Page 1
    Read page 1 as text

    Solution Manual for Adaptive Filter Theory 5e Created by Simon Haykin and Kelvin Hall McMaster University H AMILTON , O NTARIO C ANADA

  2. Page 2
  3. Page 3
    Read page 3 as text

    Table of Contents Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . P ii Corrections for Question-Descriptions in the Textbook . . . . . . . . . . . . . . P iv Notes on Computer Simulations and Provided Programs . . . . . . . . . . . . P vi Chapter 1: Stochastic Processes and Models . . . . . . . . . . . . . . . . . . . . . . . . P 1 Chapter 2: Wiener Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . P 21 Chapter 3: Linear Prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . P 48 Chapter 4: Method of Steepest Descent . . . . . . . . . . . . . . . . . . . . . . . . . . P 102 Chapter 5: Method of Stochastic Gradient Descent . . . . . . . . . . . . . . . . P 120 Chapter 6: The Least-Mean-Square(LMS) Algorithm . . . . . . . . . . . . . . P 128 Chapter 7: Normalized Least-Mean-Square(LMS) Algorithm and Its Generalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . P 167 Chapter 8: Block-Adaptive Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . P 178 Chapter 9: Method of Least-Squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . P 190 Chapter 10: The Recursive Least-Squares (RLS) Algorithm . . . . . . . . P 214 Chapter 11: Robustness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . P 229 Chapter 12: Finite-Precision Effects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . P 243 Chapter 13: Adaptation in Nonstationary Environments . . . . . . . . . . . . P 251 Chapter 14: Kalman Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . P 304 Chapter 15: Square-Root Adaptive Filtering Algorithms . . . . . . . . . . . P 324 Chapter 16: Order-Recursive Adaptive Filtering Algorithm . . . . . . . . P 341 Chapter 17: Blind Deconvolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . P 380 Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . P 394 iii

  4. Page 4
    Read page 4 as text

    Notes on the Computer Simulations and Provided Programs The computer experiments completed for this solutions manual were completed al- most exclusively using Matlab®, for ease of readability. To improve the accessibility of the solutions, to the users of this manual, specialized signal processing toolkits were not used in programs included. Graphical solutions are provided along with the .m files in case the user of the textbook is interested in completing the exercises in a different pro- gramming language, in which case a graphical solution is available for comparison. The solutions of the computer problems in Chapter 13 were completed by Ashique Rupam Mahmood, Computer Science, University of Alberta, the creator of the Autostep algorithm. The solutions being completed prior to the rest of the manual are only avail- able in the programming language python, which is similar to Matlab® and therefore quite readable. vi

  5. Page 5
    Read page 5 as text

    Chapter 1 Problem 1.1 Let r u ( k ) = E [ u ( n ) u ∗ ( n − k )] (1) r y ( k ) = E [ y ( n ) y ∗ ( n − k )] (2) we are given that y ( n ) = u ( n + a ) − u ( n − a ) (3) Hence, substituting Equation (3) into Equation (2), and then using Equation (1), we get r y ( k ) = E [( u ( n + a ) − u ( n − a ))( u ∗ ( n + a − k ) − u ∗ ( n − a − k ))] =2 r u ( k ) − r u (2 a + k ) − r u ( − 2 a + k ) Problem 1.2 We know that the correlation matrix R is Hermitian; that is to say that R H = R Given that the inverse matrix R − 1 exists, we may write R − 1 R H = I where I is the identity matrix. Taking the Hermitian transpose of both sides: RR − H = I 1

  6. Page 6
    Read page 6 as text

    PROBLEM 1.3 . CHAPTER 1. Hence, R − H = R − 1 That is, the inverse matrix R − 1 is Hermitian. Problem 1.3 For the case of a two-by-two matrix, it may be stated as R u = R s + R ν = [ r 11 r 12 r 21 r 22 ] + [ σ 2 0 0 σ 2 ] = [ r 11 + σ 2 r 12 r 21 r 22 + σ 2 ] For R u to be nonsingular, we require det( R u ) 6 = 0 ( r 11 + σ 2 )( r 2 2 + σ 2 ) − r 12 r 22 6 = 0 With r 12 = r 21 for real data, this condition reduces to ( r 11 + σ 2 )( r 22 + σ 2 ) − r 2 12 6 = 0 Since this is a quadratic in σ 2 , we may impose the following conditions on σ 2 for nonsin- gularity of R u : σ 2 6 = 1 2 ( r 11 + r 22 ) (√ 1 − 4∆ r ( r 11 + r 22 ) 2 − 1 ) where ∆ r = r 11 r 22 − r 2 12 Problem 1.4 We are given R = [ 1 1 1 1 ] 2

  7. Page 7
    Read page 7 as text

    PROBLEM 1.5 . CHAPTER 1. This matrix is positive definite because it satisfies the condition: a T R a = [ a 1 a 2 ] [ 1 1 1 1 ] [ a 1 a 2 ] = a 2 1 + 2 a 1 a 2 + a 2 2 =( a 1 + a 2 ) 2 > 0 for all nonzero values of a 1 and a 2 But the matrix R is singular because: det( R ) = (1) 2 − (1) 2 = 0 Hence, it is possible for a matrix to be both positive definite and singular at the same time. Problem 1.5 a) R M +1 = [ r (0) r H r R M ] (1) Let R − 1 M +1 = [ a b H b C M ] (2) where a, b and C are to be determined. Multiply Equation (1) by Equation (2): I M +1 = [ r (0) r H r R M ] [ a b H b C ] Where I M +1 is the identity matrix. Therefore, r (0) a + r H b = 1 (3) r a + R M b = 0 (4) rb H + R M C = I M (5) r (0) b H + r H C = 0 (6) Equation (4) can be rearranged to solve for b as: b = − R − 1 M r a (7) 3

  8. Page 8
    Read page 8 as text

    PROBLEM 1.5 . CHAPTER 1. Hence, from equations (3) and (7): a = 1 r (0) − r H R − 1 M r (8) Correspondingly, b = − R − 1 M rr H R − 1 M r (0) − r H R − 1 M r (9) From Equation (5): C = R − 1 M − R − 1 M rb H C = R − 1 M + R − 1 M rr H R − 1 M r (0) − r H R − 1 M r (10) As a check, the results of Equations (9) and (10) should satisfy Equation (6) r (0) b H + r H C = − r (0) r H R − 1 M r (0) − r H R − 1 M r + r H R − 1 M + r H R − 1 M rr H R − 1 M r (0) − r H R − 1 M R = 0 We have thus shown that R − 1 M +1 = [ 0 0 0 R − 1 M ] + a [ 1 − r H R − 1 M R − 1 M r R − 1 M rr H R − 1 M ] = [ 0 0 0 R − 1 M ] + a [ 1 − R − 1 M r ] [ 1 − r H R − 1 M ] where the scalar a is defined by Equation (8) b) R M +1 = [ R M r B ∗ r BT r (0) ] (11) Let R − 1 M +1 = [ D e e H f ] (12) 4

  9. Page 9
    Read page 9 as text

    PROBLEM 1.5 . CHAPTER 1. where D , e and f are to be determined. Multiplying Equation (11) by Equation (12) you get: I M +1 = [ R M r B ∗ r BT r (0) ] [ D e e H f ] Therefore: R M D + r B ∗ e H = I (13) R M e + r B ∗ f = 0 (14) r BT e + r (0) f = 1 (15) r BT D + r (0) e H = 0 (16) From Equation (14): e = − R − 1 M r B ∗ (17) Hence, from Equation (15) and Equation (17): f = 1 r (0) − r BT R − 1 M r B ∗ (18) Correspondingly, e = − R − 1 M r B ∗ r (0) − r BT R − 1 M r B ∗ (19) From Equation (13): D = R − 1 M − R − 1 M r B ∗ e H = R − 1 M + R − 1 M r B ∗ r BT R − 1 M r (0) − r BT R − 1 M r B ∗ (20) As a check, the results of Equation (19) and Equation (20) must satisfy Equation (16): r BT D + r (0) e H = 0 r BT R − 1 M + r BT R − 1 M r B ∗ r BT R − 1 M r (0) − r BT R − 1 M r B ∗ − r (0) r BT R − 1 M r (0) − r BT R − 1 M r B ∗ = 0 We have thus shown that R − 1 M +1 = [ R − 1 M 0 0 0 ] + f [ R − 1 M r B ∗ r BT R − 1 M R − 1 M r B ∗ − r BT R − 1 M 1 ] = [ R − 1 M 0 0 0 ] + f [ − R − 1 M r B ∗ 1 ] [ − r BT R − 1 M 1 ] where the scalar f is defined by Equation (18) 5

  10. Page 10
    Read page 10 as text

    PROBLEM 1.6 . CHAPTER 1. Problem 1.6 a) We express the difference equation describing the first-order AR process u ( n ) as u ( n ) = ν ( n ) + w 1 u ( n − 1) where w 1 = − a 1 . Solving the equation by repeated substitution, we get u ( n ) = ν ( n ) + w 1 ν ( n − 1) + w 1 u ( n − 2) = ν ( n ) + w 1 ν ( n − 1) + w 2 1 ν ( n − 2) + . . . + w n − 1 1 ν (1) (1) Here we used the initial condition u (0) = 0 Taking the expected value of both sides of Equation (1) and using E [ ν ( n )] = μ we get the geometric series E [ u ( n )] = μ + w 1 μ + w 2 1 μ + . . . + w n − 1 1 μ = { μ ( 1 − w n 1 1 − w 1 ) , w 1 6 = 1 μn, w 1 = 1 } This result shows that if μ 6 = 0 , then E [ u ( n )] is a function of time n . Accordingly, the AR process u ( n ) is not stationary. If, however, the AR parameter satisfies the condition: | a 1 | < 1 or | w 1 | < 1 then E [ u ( n )] → μ 1 − w 1 as n → ∞ Under this condition, we say that the AR process is asymptotically stationary to order one. b) When the white noise process ν ( n ) has zero mean, the AR process u ( n ) will likewise have zero mean. Then var [ ν ( n )] = σ 2 ν 6

  11. Page 11
    Read page 11 as text

    PROBLEM 1.6 . CHAPTER 1. var [ u ( n )] = E [ u 2 ( n )] (2) Substituting Equation (1) into Equation (2), and recognizing that for the white noise pro- cess E [ ν ( n ) ν ( k )] = { σ 2 ν n = k 0 , n 6 = k (3) we get the geometric series var [ u ( n )] = σ 2 ν (1 + w 2 1 + w 4 1 + . . . + w 2 n − 2 1 ) =    σ 2 ν ( 1 − w 2 n 1 1 − w 2 1 ) , w 1 6 = 1 σ 2 ν n, w 1 = 1 When | a 1 | < 1 or | w 1 | < 1 , then var [ u ( n )] ≈ σ 2 ν 1 − w 2 1 = σ 2 ν 1 − a 2 1 for large n c) The autocorrelation function of the AR process u ( n ) equals E [ u ( n ) u ( n − k )] . Substituting Equation (1) into this formula, and using Equation (3), we get E [ u ( n ) u ( n − k )] = σ 2 ν ( w k 1 + w k +2 1 + . . . + w k +2 n − 2 1 ) = { σ 2 ν w k 1 ( 1 − w 2 n 1 1 − w 2 1 ) , w 1 6 = 1 σ 2 ν n, w 1 = 1 For | a 1 | < 1 or | w 1 | < 1 , we may therefore express this autocorrelation function as r ( k ) = E [ u ( n ) u ( n − k )] ≈ σ 2 ν w k 1 1 − w 2 1 for large n Case 1: 0 < a 1 < 1 In this case, w 1 = − a 1 is negative, and r ( k ) varies with k as follows: 7

  12. Page 12
    Read page 12 as text

    PROBLEM 1.7 . CHAPTER 1. 9 for large n Case 1: 0 < a 1 < 1 In this case, w 1 = - a 1 is negative, and r ( k ) varies with k as follows: Case 2: -1 < a 1 < 0 In this case, w 1 = - a 1 is positive and r ( k ) varies with k as follows: 1.7 (a) The second-order AR process u ( n ) is described by the difference equation: Hence and the AR parameters equal Accordingly, we write the Yule-Walker equations as σ v w 1 1 w 1 2 – -------------- - ≈ -4 -3 -2 -1 0 +1 +2 +3 +4 k r ( k ) -4 -2 -1 0 +2 +3 +4 k r ( k ) -3 +1 u n ( ) u n 1 – ( ) 0.5 u n 2 – ( ) – v n ( ) + = w 1 1 = w 2 0.5 – = a 1 1 – = a 2 0.5 = Case 2: − 1 < a 1 < 0 In this case, w 1 = − a 1 is positive, and r ( k ) varies with k as follows: 9 for large n Case 1: 0 < a 1 < 1 In this case, w 1 = - a 1 is negative, and r ( k ) varies with k as follows: Case 2: -1 < a 1 < 0 In this case, w 1 = - a 1 is positive and r ( k ) varies with k as follows: 1.7 (a) The second-order AR process u ( n ) is described by the difference equation: Hence and the AR parameters equal Accordingly, we write the Yule-Walker equations as σ v 2 w 1 k 1 w 1 2 – -------------- - ≈ -4 -3 -2 -1 0 +1 +2 +3 +4 k r ( k ) -4 -2 -1 0 +2 +3 +4 k r ( k ) -3 +1 u n ( ) u n 1 – ( ) 0.5 u n 2 – ( ) – v n ( ) + = w 1 1 = w 2 0.5 – = a 1 1 – = a 2 0.5 = Problem 1.7 a) The second-order AR process u ( n ) is described by the difference equation: u ( n ) = u ( n − 1) − 0 . 5 u ( n − 2) + ν ( n ) which, rewritten, states w 1 = 1 w 2 = − 0 . 5 as the AR parameters are equal to: a 1 = − 1 a 2 = 0 . 5 Accordingly, the Yule-Walker equation may be written as: [ r (0) r (1) r (1) r (0) ] [ 1 − 0 . 5 ] = [ r (1) r (2) ] b) Writing the Yule-Walker equations in expanded form: r (0) − 0 . 5 r (1) = r (1) 8

  13. Page 13
    Read page 13 as text

    PROBLEM 1.8 . CHAPTER 1. r (1) − 0 . 5 r (0) = r (2) Solving the first relation for r (1) : r (1) = 2 3 r (0) (1) Solving the second relation for r (2) : r (2) = 1 6 r (0) (2) c) Since the noise ν ( n ) has zero mean, the associated AR process u ( n ) will also have zero mean. Hence, var [ u ( n )] = E [( u 2 )] = r (0) It is known that σ 2 ν = 2 ∑ k =0 a k r ( k ) = r (0) + a 1 r (1) + a 2 r (2) (3) Substituting Equation (1) and Equation (2) into Equation (3), and solving for r (0) , we get: r (0) = σ 2 ν 1 + 2 3 a 1 + 1 6 a 2 = 1 . 2 Problem 1.8 By Definition, P 0 = Average power of the AR process u ( n ) = E [ | u ( n ) | 2 ] = r (0) (1) where r (0) is the autocorrelation function of u ( n ) with zero lag. We note that { a 1 , a 2 , . . . , a M } { r (1) r (0) , r (2) r (0) , . . . , r ( M ) r (0) } 9

  14. Page 14
    Read page 14 as text

    PROBLEM 1.9 . CHAPTER 1. Equivalently, except for the scaling factor r (0) , { a 1 , a 2 , . . . , a M } { r (1) , r (2) , . . . , r ( M ) } (2) Combining Equation (1) and Equation (2): { P 0 , a 1 , a 2 , . . . , a M } { r (0) , r (1) , r (2) , . . . , r ( M ) } (3) Problem 1.9 a) The transfer function of the MA model of Fig. 1.3 is H ( z ) = 1 + b ∗ 1 z − 1 + b ∗ 2 z − 2 + . . . + b ∗ K z − K b) The transfer function of the ARMA model of Fig. 1.4 is H ( z ) = b 0 + b ∗ 1 z − 1 + b ∗ 2 z − 2 + . . . + b ∗ K z − K 1 + a ∗ 1 z − 1 + a ∗ 2 z − 2 + . . . + a ∗ M z − M c) The ARMA model reduces to an AR model when b 0 = b 1 = . . . = b K = 0 The ARMA model reduces to MA model when a 1 = a 2 = . . . = a M = 0 10

  15. Page 15
    Read page 15 as text

    PROBLEM 1.10 . CHAPTER 1. Problem 1.10 ∗ Taking the z -transform of both sides of the correct equation: X ( z ) = (1 + 0 . 75 z − 1 + 0 . 25 z − 2 ) V ( z ) Hence, the transfer function of the MA model is: X ( z ) V ( z ) =1 + 0 . 75 z − 1 + 0 . 75 z − 1 = 1 (1 + 0 . 75 z − 1 + 0 . 75 z − 1 ) − 1 (1) Using long division we may perform the following expansion of the denominator in Equa- tion (1): (1 + 0 . 75 z − 1 + 0 . 75 z − 1 ) − 1 = 1 − 3 4 z − 1 + 5 16 z − 2 − 3 64 z − 3 − 11 256 z − 4 − 45 1024 z − 5 − 91 4096 z − 6 + 93 16283 z − 7 − 85 65536 z − 8 − 627 262144 z − 9 + 1541 1048576 z − 10 + . . . ≈ 1 − 0 . 75 z − 1 + 0 . 3125 z − 2 − 0 . 0469 z − 3 − 0 . 043 z − 4 − 0 . 0439 z − 5 − 0 . 0222 z − 6 + 0 . 0057 z − 7 − 0 . 0013 z − 8 − 0 . 0024 z − 9 + 0 . 0015 z − 10 (2) a) M = 2 Retaining terms in Equation (2) up to z − 2 , we may approximate the MA model with an AR model of order two as follows: X ( z ) V ( z ) ≈ 1 1 − 0 . 75 z − 1 + 0 . 3125 z − 2 ∗ Correction: the question was meant to ask the reader to consider an MA process x ( n ) of order two described by the difference equation x ( n ) = ν ( n ) + 0 . 75 ν ( n − 1) + 0 . 25 ν ( n − 2) not the equation x ( n ) = ν ( n ) + 0 . 75 ν ( n − 1) + 0 . 75 ν ( n − 2) 11

  16. Page 16
    Read page 16 as text

    PROBLEM 1.11 . CHAPTER 1. b) M = 5 Retaining terms in Equation (2) up to z − 5 , we may approximate the MA model with an AR model of order two as follows: X ( z ) V ( z ) ≈ 1 1 − 0 . 75 z − 1 + 0 . 3125 z − 2 − 0 . 0469 z − 3 − 0 . 043 z − 4 + 0 . 0439 z − 5 c) M = 10 Retaining terms in Equation (2) up to z − 10 , we may approximate the MA model with an AR model of order two as follows: X ( z ) V ( z ) ≈ 1 D ( z ) where D ( z ) is given by the polynomial on the right-hand side of Equation (2). Problem 1.11 a) The filter output is x ( n ) = w H u ( n ) where u ( n ) is the tap-input vector. The average power of the filter output is therefore E [ | x ( n ) | 2 ] = E [ w H u ( n ) u H ( n ) w ] = w H E [ u ( n ) u H ( n )] w = w H Rw b) If u ( n ) is extracted from a zero-mean white noise with variance σ 2 , then R = σ 2 I where I is the identity matrix. Hence, E [ | x ( n ) | 2 ] = σ 2 w H w 12

407 more pages in the full document

Unlock it once and it stays in your library, ready to chat with or turn into flashcards.

Unlock the full document

More Electrical Engineering & Electronics study materials

See all

Study this document with CramX

Once it is in your library, every tool can work from it.