1 INTRODUCTION 1
1．1 Characterization of Signals 2
1．1．1 Deterministic Signals, 2
1．1．2 Random Signals,Correlation Functions,and Power Spectra, 5
1．2 Characterization of Linear Time-Invariant Systems 14
1．2．1 Time-Domain Characterization, 14
1．2．2 Frequency-Domain Characterization, 17
1．2．3 Causality and Stability, 19
1．2．4 Bandpass Systems and Signals, 20
1．2．5 Inverse Systems,Minimum-Phase Systems,and All-Pass Systems, 26
1．2．6 Response of Linear Systems to Random Input Signals, 27
1．3 Sampling of Signals 30
1．3．1 Time-Domain Sampling of Analog signals, 31
1．3．2 Sampling the Spectrum of a Discrete-Time Signal, 38
1．3．3 The Discrete Fourier Transform for Finite-Duration Sequences, 41
1．3．4 The DFT and IDFT as Matrix Transformations, 43
1．4 Linear Filtering Methods Based on the DFT 46
1．4．1 Use of the DFT in Linear Filtering, 47
1．4．2 Filtering of Long Data Sequences, 50
1．5 The Cepstrum 53
1．6 Summary and References 56
Problems 56
2 ALGORITHMS FOR CONVOLUTION AND DFT 61
2．1 Modulo Polynomials 61
2．2 Circular Convolution as Polynomial Multiplication mod uN-1 63
2．3 A Continued Fraction of Polynomials 64
2．4 Chinese Remainder Theorem for Polynomials 66
2．5 Algorithms for Short Circular Convolutions 67
2．6 How We Count Multiplications 74
2．7 Cyclotomic Polynomials 76
2．8 Elementary Number Theory 77
2．8．1 Greatest Common Divisors and Euler’s Totient Function, 78
2．8．2 The Equation ax+by=1, 78
2．8．3 Modulo Arithmetic, 81
2．8．4 The Sino Representation of Integers Modulo M, 83
2．8．5 Exponentials Modulo M, 85
2．9 Convolution Length and Dimension 88
2．10 The DFT as a Circular Convolution 92
2．11 Winograd’s DFT Algorithm 95
2．12 Number-Theoretic Analogy of DFT 98
2．13 Number-Theoretic Transform 100
2．13．1 Mersenne Number Transform, 104
2．13．2 Fermat Number Transform, 106
2．13．3 Considerations for Use of NTTs to Perform Circular Convolution, 107
2．13．4 Use of Surrogate Fields for Complex Arithmetic, 108
2．14 Split-Radix FFT 110
2．15 Autogen Technique 116
2．16 Summary 122
Problems 123
3 LINEAR PREDICTION AND OPTIMUM LINEAR FILTERS 125
3．1 Innovations Representation of a Stationary Random Process 125
3．1．1 Rational Power Spectra, 128
3．1．2 Relationships between the Filter Parameters and the Autocorrelation Sequence, 129
3．2 Forward and Backward Linear Prediction 131
3．2．1 Forward Linear Prediction, 131
3．2．2 Backward Linear Prediction, 135
3．2．3 Optimum Reflection Coefficients for the Lattice Forward and Backward Predictors, 139
3．2．4 Relationship of an AR Process to Linear Prediction, 139
3．3 Solution of the Normal Equations 140
3．3．1 Levinson-Durbin Algorithm, 140
3．3．2 The Schur Algorithm, 144
3．4 Properties of the Linear Prediction-Error Filters 148
3．5 AR Lattice and ARMA Lattice-Ladder Filters 152
3．5．1 AR Lattice Structure, 152
3．5．2 ARMA Processes and Lattice-Ladder Filters, 154
3．6 Wiener Filters for Filtering and Prediction 157
3．6．1 FIR Wiener Filter, 157
3．6．2 Orthogonality Principle in Linear Mean-Square Estimation, 160
3．6．3 IIR Wiener Filter, 161
3．6．4 Noncausal Wiener Filter, 165
3．7 Summary and References 167
Problems 168
4 LEAST-SQUARES METHODS FOR SYSTEM MODELING AND FILTER DESIGN 177
4．1 System Modeling and Identification 178
4．1．1 System Identification Based on FIR(MA)System Model, 178
4．1．2 System Identification Bascd on All-Pole(AR)System Model, 181
4．1．3 System Identification Based on Pole-Zero(ARMA)System Model, 183
4．2 Least-Squares Filter Design for Prediction and Deconvolution 189
4．2．1 Least-Squares Linear Prediction Filter, 190
4．2．2 FIR Least-Squares Inverse Filters, 191
4．2．3 Predictive Deconvolution, 195
4．3 Solution of Least-Squares Estimation Problems 197
4．3．1 Definition and Basic Concepts, 198
4．3．2 Matrix Formulation of Least-Squares Estimation, 199
4．3．3 Cholesky Decomposition, 203
4．3．4 LDU Decomposition, 205
4．3．5 QR Decomposition, 207
4．3．6 Gram-Schmidt Orthogonalization, 209
4．3．7 Givens Rotation, 211
4．3．8 Householder Reflection, 214
4．3．9 Singular-Value Decomposition, 217
4．4 Summary and References 225
Problems 226
5 ADAPTIVE FILTERS 231
5．1 Applications of Adaptive Filters 231
5．1．1 System Identification or System Modeling, 233
5．1．2 Adaptive Channel Equalization, 235
5．1．3 Echo Cancellation in Data Transmission over Telephone Channels, 238
5．1．4 Suppression of Narrowband Interference in a Wideband Signal, 242
5．1．5 Adaptive Line Enhancer, 246
5．1．6 Adaptive Noise Cancelling, 247
5．1．7 Linear Predictive Coding of Speech Signals, 248
5．1．8 Adaptive Arrays, 251
5．2 Adaptive Direct-Form FIR Filters 253
5．2．1 Minimum Mean-Square-Error Criterion, 254
5．2．2 The LMS Algorithm, 256
5．2．3 Properties of the LMS Algorithm, 259
5．2．4 Recursive Least-Squares Algorithms for Direct-Form FIR Filters, 265
5．2．5 Properties of the Direct-Form RLS Algorithms, 273
5．3 Adaptive Lattice-Ladder Filters 276
5．3．1 Recursive Least-Squares Lattice-Ladder Algorithms, 276
5．3．2 Gradient Lattice-Ladder Algorithm, 300
5．3．3 Properties of Lattice-Ladder Algorithms, 304
5．4 Summary and References 309
Problems 309
6 RECURSIVE LEAST-SQUARES ALGORITHMS FOR ARRAY SIGNAL PROCESSING 314
6．1 QR Decomposition for Least-Squares Estimation 315
6．2 Gram-Schmidt Orthogonalization for Least-Squares Estimation 318
6．2．1 Least-Squares Estimation Using the MGS Algorithm, 319
6．2．2 Physical Meaning of the Quantities in the MGS Algorithm, 320
6．2．3 Time-Recursive Form of the Modified Gram-Schmidt Algorithm, 321
6．2．4 Variations of the RMGS Algorithm, 328
6．2．5 Implementation of the RMGS Algorithm Using VLSI Arrays,and Its Relationship to the Least-Squares Lattice Algorithm, 332
6．3 Givens Algorithm for Time-Recursive Least-Squares Estimation 337
6．3．1 Time-Recursive Givens Algorithm, 337
6．3．2 Givens Algorthm without Square Roots, 340
6．3．3 The CORDIC Approach to Givens Transformations, 344
6．4 Recursive Least-Squares Estimation Based on the Householder Transformation 358
6．4．1 Block Time-Recursive Least-Squares Estimation Using the Householder Transformation, 358
6．5 Order-Recursive Least-Squares Estimation Algorithms 363
6．5．1 Fundamental Relations of ORLS Estimation, 364
6．5．2 Canonical Structures for ORLS Estimation Algorithms, 370
6．5．3 Variations in the Basic Processing Cells of ORLS Algorithms, 376
6．5．4 Systematic Investigation and Derivation of ORLS Algorithms, 381
6．6 Summary and References 382
Problems 384
7 QRD-BASED FAST ADAPTIVE FILTER ALGORITHMS 387
7．1 Background 388
7．1．1 Signal Flow Graphs, 388
7．1．2 QRD-based RLS,Revisited, 390
7．1．3 Residual Extraction, 392
7．2 QRD Lattice 394
7．3 Multichannel Lattice 402
7．4 Fast QR Algorithm 411
7．5 Multichannel Fast QR Algorithm 416
7．6 Summary and References 427
Problems 429
8 POWER SPECTRUM ESTIMATION 432
8．1 Estimation of Spectra from Finite-Duration Observations of Signals 433
8．1．1 Computation of the Energy Density Spectrum, 433
8．1．2 Estimation of the Autocorrelation and Power Spectrum of Random Signals：The Periodogram, 438
8．1．3 Use of the DFT in Power Spectrum Estimation, 443
8．2 Nonparametric Methods for Power Spectrum Estimation 445
8．2．1 Bartlett Method:Averaging Periodograms, 446
8．2．2 Welch Method:Averaging Modified Periodograms, 447
8．2．3 Blackman and Tukey Method:Smoothing the Periodogram, 449
8．2．4 Performance Characteristics of Nonparametric Power Spectrum Estimators, 452
8．2．5 Computational Requirements of Nonparametric Power Spectrum Estimates, 456
8．3 Parametric Methods for Power Spectrum Estimation 457
8．3．1 Relationships Between the Autocorrelation and the Model Parameters, 459
8．3．2 Yule-Walker Method for the AR Model Parameters, 461
8．3．3 Burg Method for the AR Model Parameters, 462
8．3．4 Unconstrained Least-Squares Method for the AR Model Parameters, 465
8．3．5 Sequential Estimation Methods for the AR Model Parameters, 467
8．3．6 Selection of AR Model Order, 468
8．3．7 MA Model for Power Spectrum Estimation, 469
8．3．8 ARMA Model for Power Spectrum Estimation, 470
8．3．9 Experimental Results, 473
8．4 Minimum-Variance Spectral Estimation 481
8．5 Eigenanalysis Algorithms for Spectrum Estimation 483
8．5．1 Pisarenko Harmonic Decompsition Method, 484
8．5．2 Eigendecomposition of the Autocorrelation Matrix for Sinusoids in White Noise, 486
8．5．3 MUSIC Algorithm, 488
8．5．4 ESPRIT Algorithm, 489
8．5．5 Order Selection Criteria, 492
8．5．6 Experimental Results, 492
8．6 Summary and References 495
Problems 496
9 SIGNAL ANALYSIS WITH HIGHER-ORDER SPECTRA 504
9．1 Use of Higher-Order Spectra in Signal Processing 504
9．2．1 Moments and Cumulants of Random Signals, 506
9．2 Definition and Properties of Higher-Order Spectra 506
9．2．2 Higher-Order Spectra (Cumulant Spectra), 508
9．2．3 Linear Non-Gaussian Processes, 510
9．2．4 Nonlinear Processes, 512
9．3 Conventional Estimators for Higher-Order Spectra 514
9．3．1 Indirect Method, 514
9．3．2 Direct Method, 516
9．3．3 Statistical Properties of Conventional Estimators, 517
9．3．4 Test for Aliasing with the Bispectrum, 518
9．4 Parametric Methods for Higher-Order Spectrum Estimation 520
9．4．1 MA Methods, 522
9．4．2 Noncausal AR Methods, 525
9．4．3 ARMA Methods, 526
9．4．4 AR Methods for the Detection of Quadratic Phase Coupling, 528
9．5 Cepstra of Higher-Order Spectra 531
9．5．1 Preliminaries, 531
9．5．2 Complex and Differentical Cepstra, 532
9．5．3 Bicepstrum, 533
9．5．4 Cepstrum of the Power Spectrum, 535
9．5．5 Cepstrum of the Bicoherence, 536
9．5．6 Summary of Cepstra and Key Observation, 537
9．6 Phase and Magnitude Retrieval from the Bispectrum 537
9．7 Summary and Refefences 540
Problems 541
REFERENCES 542
INDEX 559