Adaptive Filters

Behrouz Farhang-Boroujeny, University of Utah, USA

Preface xvii

Acknowledgments xxi

1 Introduction 1

1.1 Linear Filters 1

1.2 Adaptive Filters 2

1.3 Adaptive Filter Structures 3

1.4 Adaptation Approaches 7

1.5 Real and Complex Forms of Adaptive Filters 9

1.6 Applications 9

2 Discrete-Time Signals and Systems 28

2.1 Sequences and z-Transform 28

2.2 Parseval’s Relation 32

2.3 System Function 33

2.4 Stochastic Processes 35

Problems 44

3 Wiener Filters 48

3.1 Mean-Squared Error Criterion 48

3.2 Wiener Filter – Transversal, Real-Valued Case 50

3.3 Principle of Orthogonality 55

3.4 Normalized Performance Function 57

3.5 Extension to Complex-Valued Case 58

3.6 Unconstrained Wiener Filters 61

3.7 Summary and Discussion 79

Problems 80

4 Eigenanalysis and Performance Surface 90

4.1 Eigenvalues and Eigenvectors 90

4.2 Properties of Eigenvalues and Eigenvectors 91

4.3 Performance Surface 104

Problems 112

5 Search Methods 119

5.1 Method of Steepest Descent 120

5.2 Learning Curve 126

5.3 Effect of Eigenvalue Spread 130

5.4 Newton’s Method 131

5.5 An Alternative Interpretation of Newton’s Algorithm 133

Problems 135

6 LMS Algorithm 139

6.1 Derivation of LMS Algorithm 139

6.2 Average Tap-Weight Behavior of the LMS Algorithm 141

6.3 MSE Behavior of the LMS Algorithm 144

6.4 Computer Simulations 156

6.5 Simplified LMS Algorithms 167

6.6 Normalized LMS Algorithm 170

6.7 Affine Projection LMS Algorithm 173

6.8 Variable Step-Size LMS Algorithm 177

6.9 LMS Algorithm for Complex-Valued Signals 179

6.10 Beamforming (Revisited) 182

6.11 Linearly Constrained LMS Algorithm 186

Problems 190

Appendix 6A: Derivation of Eq. (6.39) 205

7 Transform Domain Adaptive Filters 207

7.1 Overview of Transform Domain Adaptive Filters 208

7.2 Band-Partitioning Property of Orthogonal Transforms 210

7.3 Orthogonalization Property of Orthogonal Transforms 211

7.4 Transform Domain LMS Algorithm 213

7.5 Ideal LMS-Newton Algorithm and Its Relationship with TDLMS 215

7.6 Selection of the Transform T 216

7.7 Transforms 229

7.8 Sliding Transforms 230

7.9 Summary and Discussion 242

Problems 243

8 Block Implementation of Adaptive Filters 251

8.1 Block LMS Algorithm 252

8.2 Mathematical Background 255

8.3 The FBLMS Algorithm 260

8.4 The Partitioned FBLMS Algorithm 267

8.5 Computer Simulations 276

Problems 279

Appendix 8A: Derivation of a Misadjustment Equation for the BLMS Algorithm 285

Appendix 8B: Derivation of Misadjustment Equations for the FBLMS Algorithms 288

9 Subband Adaptive Filters 294

9.1 DFT Filter Banks 295

9.2 Complementary Filter Banks 299

9.3 Subband Adaptive Filter Structures 303

9.4 Selection of Analysis and Synthesis Filters 304

9.5 Computational Complexity 307

9.6 Decimation Factor and Aliasing 308

9.7 Low-Delay Analysis and Synthesis Filter Banks 310

9.8 A Design Procedure for Subband Adaptive Filters 313

9.9 An Example 316

9.10 Comparison with FBLMS Algorithm 318

Problems 319

10 IIR Adaptive Filters 322

10.1 Output Error Method 323

10.2 Equation Error Method 327

10.3 Case Study I: IIR Adaptive Line Enhancement 332

10.4 Case Study II: Equalizer Design for Magnetic Recording Channels 343

10.5 Concluding Remarks 349

Problems 352

11 Lattice Filters 355

11.1 Forward Linear Prediction 355

11.2 Backward Linear Prediction 357

11.3 Relationship Between Forward and Backward Predictors 359

11.4 Prediction-Error Filters 359

11.5 Properties of Prediction Errors 360

11.6 Derivation of Lattice Structure 362

11.7 Lattice as an Orthogonalization Transform 367

11.8 Lattice Joint Process Estimator 369

11.9 System Functions 370

11.10 Conversions 370

11.11 All-Pole Lattice Structure 376

11.12 Pole-Zero Lattice Structure 376

11.13 Adaptive Lattice Filter 378

11.14 Autoregressive Modeling of Random Processes 383

11.15 Adaptive Algorithms Based on Autoregressive Modeling 385

Problems 400

Appendix 11A: Evaluation of E[ua(n)xT(n)K(n)x(n)uTa (n)] 407

Appendix 11B: Evaluation of the parameter γ 408

12 Method of Least-Squares 410

12.1 Formulation of Least-Squares Estimation for a Linear Combiner 411

12.2 Principle of Orthogonality 412

12.3 Projection Operator 415

12.4 Standard Recursive Least-Squares Algorithm 416

12.5 Convergence Behavior of the RLS Algorithm 421

Problems 430

13 Fast RLS Algorithms 433

13.1 Least-Squares Forward Prediction 434

13.2 Least-Squares Backward Prediction 435

13.3 Least-Squares Lattice 437

13.4 RLSL Algorithm 440

13.5 FTRLS Algorithm 453

Problems 460

14 Tracking 463

14.1 Formulation of the Tracking Problem 463

14.2 Generalized Formulation of LMS Algorithm 464

14.3 MSE Analysis of the Generalized LMS Algorithm 465

14.4 Optimum Step-Size Parameters 469

14.5 Comparisons of Conventional Algorithms 471

14.6 Comparisons Based on Optimum Step-Size Parameters 475

14.7 VSLMS: An Algorithm with Optimum Tracking Behavior 477

14.8 RLS Algorithm with Variable Forgetting Factor 485

14.9 Summary 486

Problems 488

15 Echo Cancellation 492

15.1 The Problem Statement 492

15.2 Structures and Adaptive Algorithms 495

15.3 Double-Talk Detection 512

15.4 Howling Suppression 521

15.5 Stereophonic Acoustic Echo Cancellation 524

Appendix 15A: Multitaper method 542

Appendix 15B: Derivation of the Two-Channel Levinson–Durbin

Algorithm 549

16 Active Noise Control 551

16.1 Broadband Feedforward Single-Channel ANC 553

16.2 Narrowband Feedforward Single-Channel ANC 559

16.3 Feedback Single-Channel ANC 573

16.4 Multichannel ANC Systems 577

Appendix 16A: Derivation of Eq. (16.46) 582

Appendix 16B: Derivation of Eq. (16.53) 583

17 Synchronization and Equalization in Data Transmission Systems 584

17.1 Continuous Time Channel Model 585

17.2 Discrete Time Channel Model and Equalizer Structures 589

17.3 Timing Recovery 593

17.4 Equalizers Design and Performance Analysis 606

17.5 Adaptation Algorithms 617

17.6 Cyclic Equalization 618

17.7 Joint Timing Recovery, Carrier Recovery, and Channel Equalization 628

17.8 Maximum Likelihood Detection 629

17.9 Soft Equalization 631


17.10 Single-Input Multiple-Output Equalization 643

17.11 Frequency Domain Equalization 645

17.12 Blind Equalization 649

Problems 654

18 Sensor Array Processing 659

18.1 Narrowband Sensor Arrays 660

18.2 Broadband Sensor Arrays 678

18.3 Robust Beamforming 683

Problems 692

19 Code Division Multiple Access Systems 695

19.1 CDMA Signal Model 695

19.2 Linear Detectors 699

19.3 Adaptation Methods 707

Problems 709

20 OFDM and MIMO Communications 711

20.1 OFDM Communication Systems 711

20.2 MIMO Communication Systems 730

20.3 MIMO–OFDM 743

Problems 743

References 746

Index 761