1 Introduction 1
1.1 Signals, Systems, and Signal Processing 2
1.1.1 Basic Elements of a Digital Signal Processing System 4
1.1.2 Advantages of Digital over Analog Signal Processing 5
1.2 Classification of Signals 6
1.2.1 Multichannel and Multidimensional Signals 6
1.2.2 Continuous-Time Versus Discrete-Time Signals 9
1.2.3 Continuous-Valued Versus Discrete-Valued Signals 10
1.2.4 Deterministic Versus Random Signals 11
1.3 The Concept of Frequency in Continuous-Time and Discrete-Time Signals 12
1.3.1 Continuous-Time Sinusoidal Signals 12
1.3.2 Discrete-Time Sinusoidal Signals 14
1.3.3 Harmonically Related Complex Exponentials 17
1.4 Analog-to-Digital and Digital-to-Analog Conversion 19
1.4.1 Sampling of Analog Signals 21
1.4.2 The Sampling Theorem 26
1.4.3 Quantization of Continuous-Amplitude Signals 31
1.4.4 Quantization of Sinusoidal Signals 34
1.4.5 Coding of Quantized Samples 35
1.4.6 Digital-to-Analog Conversion 36
1.4.7 Analysis of Digital Signals and Systems Versus Discrete-Time Signals and Systems 36
1.5 Summary and References 37
Problems 37
2 Discrete-Time Signals and Systems 41
2.1 Discrete-Time Signals 42
2.1.1 Some Elementary Discrete-Time Signals 43
2.1.2 Classification of Discrete-Time Signals 45
2.1.3 Simple Manipulations of Discrete-Time Signals 50
2.2 Discrete-Time Systems 53
2.2.1 Input-Output Description of Systems 54
2.2.2 Block Diagram Representation of Discrete-Time Systems 57
2.2.3 Classification of Discrete-Time Systems 59
2.2.4 Interconnection of Discrete-Time Systems 67
2.3 Analysis of Discrete-Time Linear Time-Invariant Systems 69
2.3.1 Techniques for the Analysis of Linear Systems 69
2.3.2 Resolution of a Discrete-Time Signal into Impulses 71
2.3.3 Response of LTI Systems to Arbitrary Inputs: The Convolution Sum 73
2.3.4 Properties of Convolution and the Interconnection of LTI Systems 80
2.3.5 Causal Linear Time-Invariant Systems 83
2.3.6 Stability of Linear Time-Invariant Systems 85
2.3.7 Systems with Finite-Duration and Infinite-Duration Impulse Response 88
2.4 Discrete-Time Systems Described by Difference Equations 89
2.4.1 Recursive and Nonrecursive Discrete-Time Systems 90
2.4.2 Linear Time-Invariant Systems Characterized by Constant-Coefficient Difference Equations 93
2.4.3 Solution of Linear Constant-Coefficient Difference Equations 98
2.4.4 The Impulse Response of a Linear Time-Invariant Recursive System 106
2.5 Implementation of Discrete-Time Systems 109
2.5.1 Structures for the Realization of Linear Time-Invariant Systems 109
2.5.2 Recursive and Nonrecursive Realizations of FIR Systems 113
2.6 Correlation of Discrete-Time Signals 116
2.6.1 Crosscorrelation and Autocorrelation Sequences 118
2.6.2 Properties of the Autocorrelation and Crosscorrelation Sequences 120
2.6.3 Correlation of Periodic Sequences 123
2.6.4 Input-Output Correlation Sequences 125
2.7 Summary and References 128
Problems 129
3 The Z-Transform and Its Application to the Analysis of LTI Systems 147
3.1 The z-Transform 147
3.1.1 The Direct z-Transform 147
3.1.2 The Inverse z-Transform 156
3.2 Properties of the z-Transform 157
3.3 Rational z-Transforms 170
3.3.1 Poles and Zeros 170
3.3.2 Pole Location and Time-Domain Behavior for Causal Signals 174
3.3.3 The System Function of a Linear Time-Invariant System 177
3.4 Inversion of the z-Transform 180
3.4.1 The Inverse z -Transform by Contour Integration 180
3.4.2 The Inverse z-Transform by Power Series Expansion 182
3.4.3 The Inverse z-Transform by Partial-Fraction Expansion 184
3.4.4 Decomposition of Rational z-Transforms 192
3.5 Analysis of Linear Time-Invariant Systems in the z-Domain 193
3.5.1 Response of Systems with Rational System Functions 194
3.5.2 Transient and Steady-State Responses 195
3.5.3 Causality and Stability 196
3.5.4 Pole-Zero Cancellations 198
3.5.5 Multiple-Order Poles and Stability 200
3.5.6 Stability of Second-Order Systems 201
3.6 The One-sided z-Transform 205
3.6.1 Definition and Properties 206
3.6.2 Solution of Difference Equations 210
3.6.3 Response of Pole-Zero Systems with Nonzer0 Initial Conditions 211
3.7 Summary and References 214
Problems 214
4 Frequency Analysis of Signals 224
4.1 Frequency Analysis of Continuous-Time Signals 225
4.1.1 The Fourier Series for Continuous-Time Periodic Signals 226
4.1.2 Power Density Spectrum of Periodic Signals 230
4.1.3 The Fourier Transform for Continuous-Time Aperiodic Signals 234
4.1.4 Energy Density Spectrum of Aperiodic Signals 238
4.2 Frequency Analysis of Discrete-Time Signals 241
4.2.1 The Fourier Series for Discrete-Time Periodic Signals 241
4.2.2 Power Density Spectrum of Periodic Signals 245
4.2.3 The Fourier Transform of Discrete-Time Aperiodic Signals 248
4.2.4 Convergence of the Fourier Transform 251
4.2.5 Energy Density Spectrum of Aperiodic Signals 254
4.2.6 Relationship of the Fourier Transform to the z-Transform 259
4.2.7 TheCepstrum 261
4.2.8 The Fourier Transform of Signals with Poles on the Unit Circle 262
4.2.9 Frequency-Domain Classification of Signals: The Concept of Bandwidth 265
4.2.10 The Frequency Ranges of Some Natural Signals 267
4.3 Frequency-Domain and Time-Domain Signal Properties 268
4.4 Properties of the Fourier Transform for Discrete-Time Signals 271
4.4.1 Symmetry Properties of the Fourier Transform 272
4.4.2 Fourier Transform Theorems and Properties 279
4.5 Summary and References 291
Problems 292
5 Frequency-Domain Analysis of LTI Systems 300
5.1 Frequency-Domain Characteristics of Linear Time-Invariant Systems 300
5.1.1 Response to Complex Exponential and Sinusoidal Signals: The Frequency Response Function 301
5.1.2 Steady-State and Transient Response to Sinusoidal Input Signals 310
5.1.3 Steady-State Response to Periodic Input Signals 311
5.1.4 Response to Aperiodic Input Signals 312
5.2 Frequency Response of LTI Systems 314
5.2.1 Frequency Response of a System with a Rational System Function 314
5.2.2 Computation of the Frequency Response Function 317
5.3 Correlation Functions and Spectra at the Output of LTI Systems 321
5.3.1 Input-Output Correlation Functions and Spectra 322
5.3.2 Correlation Functions and Power Spectra for Random Input Signals 323
5.4 Linear Time-Invariant Systems as Frequency-Selective Filters 326
5.4.1 Ideal Filter Characteristics 327
5.4.2 Lowpass, Highpass, and Bandpass Filters 329
5.4.3 Digital Resonators 335
5.4.4 Notch Filters 339
5.4.5 Comb Filters 341
5.4.6 All-Pass Filters 345
5.4.7 Digital Sinusoidal Oscillators 347
5.5 Inverse Systems and Deconvolution 349
5.5.1 Invertibility of Linear Time-Invariant Systems 350
5.5.2 Minimum-Phase, Maximum-Phase, and Mixed-Phase Systems 354
5.5.3 System Identification and Deconvolution 358
5.5.4 Homomorphic Deconvolution 360
5.6 Summary and References 362
Problems 363
6 Sampling and Reconstruction of Signals 384
6.1 Ideal Sampling and Reconstruction of Continuous-Time Signals 384
6.2 Discrete-Time Processing of Continuous-Time Signals 395
6.3 Analog-to-Digital and Digital-to-Analog Converters 401
6.3.1 Analog-to-Digital Converters 401
6.3.2 Quantization and Coding 403
6.3.3 Analysis of Quantization Errors 406
6.3.4 Digital-to-Analog Converters 408
6.4 Sampling and Reconstruction of Continuous-Time Bandpass Signals 410
6.4.1 Uniform or First-Order Sampling 411
6.4.2 Interleaved or Nonuniform Second-Order Sampling 416
6.4.3 Bandpass Signal Representations 422
6.4.4 Sampling Using Bandpass Signal Representations 426
6.5 Sampling of Discrete-Time Signals 427
6.5.1 Sampling and Interpolation of Discrete-Time Signals 427
6.5.2 Representation and Sampling of Bandpass Discrete-Time Signals 430
6.6 Oversampling A/D and D/A Converters 433
6.6.1 Oversampling A/D Converters 433
6.6.2 Oversampling D/A Converters 439
6.7 Summary and References 440
Problems 440
7 The Discrete Fourier Transform: Its Properties and Applications 449
7.1 Frequency-Domain Sampling: The Discrete Fourier Transform 449
7.1.1 Frequency-Domain Sampling and Reconstruction of Discrete-Time Signals 449
7.1.2 The Discrete Fourier Transform (DFT) 454
7.1.3 The DFT as a Linear Transformation 459
7.1.4 Relationship of the DFT to Other Transforms 461
7.2 Properties of the DFT 464
7.2.1 Periodicity, Linearity, and Symmetry Properties 465
7.2.2 Multiplication of Two DFTs and Circular Convolution 471
7.2.3 Additional DFT Properties 476
7.3 Linear Filtering Methods Based on the DFT 480
7.3.1 Use of the DFT in Linear Filtering 481
7.3.2 Filtering of Long Data Sequences 485
7.4 Frequency Analysis of Signals Using the DFT 488
7.5 The Discrete Cosine Transform 495
7.5.1 Forward DCT 495
7.5.2 Inverse DCT 497
7.5.3 DCT as an Orthogonal Transform 498
7.6 Summary and References 501
Problems 502
8 Efficient Computation of the DFT: Fast Fourier Transform Algorithms 511
8.1 Efficient Computation of the DFT: FFT Algorithms 511
8.1.1 Direct Computation of the DFT 512
8.1.2 Divide-and-Conquer Approach to Computation of the DFT 513
8.1.3 Radix-2 FFT Algorithms 519
8.1.4 Radix-4 FFT Algorithms 527
8.1.5 Split-Radix FFT Algorithms 532
8.1.6 Implementation of FFT Algorithms 536
8.2 Applications of FFT Algorithms 538
8.2.1 Efficient Computation of the DFT of Two Real Sequences 538
8.2.2 Efficient Computation of the DFT of a 2N-Point Real Sequence 539
8.2.3 Use of the FFT Algorithm in Linear Filtering and Correlation 540
8.3 A Linear Filtering Approach to Computation of the DFT 542
8.3.1 The Goertzel Algorithm 542
8.3.2 The Chirp-z Transform Algorithm 544
8.4 Quantization Effects in the Computation of the DFT 549
8.4.1 Quantization Errors in the Direct Computation of the DFT 549
8.4.2 Quantization Errors in FFT Algorithms 552
8.5 Summary and References 555
Problems 556
9 Implementation of Discrete-Time Systems 563
9.1 Structures for the Realization of Discrete-Time Systems 563
9.2 Structures for FIR Systems 565
9.2.1 Direct-Form Structure 566
9.2.2 Cascade-Form Structures 567
9.2.3 Frequency-Sampling Structures 569
9.2.4 Lattice Structure 574
9.3 Structures for IIR Systems 582
9.3.1 Direct-Form Structures 582
9.3.2 Signal Flow Graphs and Transposed Structures 585
9.3.3 Cascade-Form Structures 589
9.3.4 Parallel-Form Structures 591
9.3.5 Lattice and Lattice-Ladder Structures for IIR Systems 594
9.4 Representation of Numbers 601
9.4.1 Fixed-Point Representation of Numbers 601
9.4.2 Binary Floating-Point Representation of Numbers 605
9.4.3 Errors Resulting from Rounding and Truncation 608
9.5 Quantization of Filter Coefficients 613
9.5.1 Analysis of Sensitivity to Quantization of Filter Coefficients 613
9.5.2 Quantization of Coefficients in FIR Filters 620
9.6 Round-Off Effects in Digital Filters 624
9.6.1 Limit-Cycle Oscillations in Recursive Systems 624
9.6.2 Scaling to Prevent Overflow 629
9.6.3 Statistical Characterization of Quantization Effects in Fixed-Point Realizations of Digital Filters 631
9.7 Summary and References 640
Problems 641
10 Design of Digital Filters 654
10.1 General Considerations 654
10.1.1 Causality and Its Implications 655
10.1.2 Characteristics of Practical Frequency-Selective Filters 659
10.2 Design of FIR Filters 660
10.2.1 Symmetric and Antisymmetric FIR Filters 660
10.2.2 Design of Linear-Phase FIR Filters Using Windows 664
10.2.3 Design of Linear-Phase FIR Filters by the Frequency-Sampling Method 671
10.2.4 Design of Optimum Equiripple Linear-Phase FIR Filters 678
10.2.5 Design of FIR Differentiators 691
10.2.6 Design of Hilbert Transformers 693
10.2.7 Comparison of Design Methods for Linear-Phase FIR Filters 700
10.3 Design of IIR Filters From Analog Filters 701
10.3.1 IIR Filter Design by Approximation of Derivatives 703
10.3.2 IIR Filter Design by Impulse Invariance 707
10.3.3 IIR Filter Design by the Bilinear Transformation 712
10.3.4 Characteristics of Commonly Used Analog Filters 717
10.3.5 Some Examples of Digital Filter Designs Based on the Bilinear Transformation 727
10.4 Frequency Transformations 730
10.4.1 Frequency Transformations in the Analog Domain 730
10.4.2 Frequency Transformations in the Digital Domain 732
10.5 Summary and References 734
Problems 735
11 Multirate Digital Signal Processing 750
11.1 Introduction 751
11.2 Decimation by a Factor D 755
11.3 Interpolation by a Factor I 760
11.4 Sampling Rate Conversion by a Rational Factor I/D 762
11.5 Implementation of Sampling Rate Conversion 766
11.5.1 Polyphase Filter Structures 766
11.5.2 Interchange of Filters and Downsamplers/Upsamplers 767
11.5.3 Sampling Rate Conversion with Cascaded Integrator Comb Filters 769
11.5.4 Polyphase Structures for Decimation and Interpolation Filters 771
11.5.5 Structures for Rational Sampling Rate Conversion 774
11.6 Multistage Implementation of Sampling Rate Conversion 775
11.7 Sampling Rate Conversion of Bandpass Signals 779
11.8 Sampling Rate Conversion by an Arbitrary Factor 781
11.8.1 Arbitrary Resampling with Polyphase Interpolators 782
11.8.2 Arbitrary Resampling with Farrow Filter Structures 782
11.9 Applications of Multirate Signal Processing 784
11.9.1 Design of Phase Shifters 784
11.9.2 Interfacing of Digital Systems with Different Sampling Rates 785
11.9.3 Implementation of Narrowband Lowpass Filters 786
11.9.4 Subband Coding of Speech Signals 787
11.10 Digital Filter Banks 790
11.10.1 Polyphase Structures of Uniform Filter Banks 794
11.10.2 Transmultiplexers 796
11.11 Two-Channel Quadrature Mirror Filter Bank 798
11.11.1 Elimination of Aliasing 799
11.11.2 Condition for Perfect Reconstruction 801
11.11.3 Polyphase Form of the QMF Bank 801
11.11.4 Linear Phase FIR QMF Bank 802
11.11.5 IIR QMF Bank 803
11.11.6 Perfect Reconstruction Two-Channel FIR QMF Bank 803
11.11.7 Two-Channel QMF Banks in Subband Coding 806
11.12 A/-Channel QMF Bank 807
11.12.1 Alias-Free and Perfect Reconstruction Condition 808
11.12.2 Polyphase Form of the M-Channel QMF Bank 808
11.13 Summary and References 813
Problems 813
12 Linear Prediction and Optimum Linear Filters 823
12.1 Random Signals, Correlation Functions, and Power Spectra 823
12.1.1 Random Processes 824
12.1.2 Stationary Random Processes 825
12.1.3 Statistical (Ensemble) Averages 825
12.1.4 Statistical Averages for Joint Random Processes 826
12.1.5 Power Density Spectrum 828
12.1.6 Discrete-Time Random Signals 829
12.1.7 Time Averages for a Discrete-Time Random Process 830
12.1.8 Mean-Ergodic Process 831
12.1.9 Correlation-Ergodic Processes 832
12.2 Innovations Representation of a Stationary Random Process 834
12.2.1 Rational Power Spectra 836
12.2.2 Relationships Between the Filter Parameters and the Autocorrelation Sequence 837
12.3 Forward and Backward Linear Prediction 838
12.3.1 Forward Linear Prediction 839
12.3.2 Backward Linear Prediction 841
12.3.3 The Optimum Reflection Coefficients for the Lattice Forward and Backward Predictors 845
12.3.4 Relationship of an AR Process to Linear Prediction 846
12.4 Solution of the Normal Equations 846
12.4.1 The Levinson-Durbin Algorithm 847
12.4.2 The Schur Algorithm 850
12.5 Properties of the Linear Prediction-Error Filters 855
12.6 AR Lattice and ARMA Lattice-Ladder Filters 858
12.6.1 AR Lattice Structure 858
12.6.2 ARMA Processes and Lattice-Ladder Filters 860
12.7 Wiener Filters for Filtering and Prediction 863
12.7.1 FIR Wiener Filter 864
12.7.2 Orthogonality Principle in Linear Mean-Square Estimation 866
12.7.3 IIR Wiener Filter 867
12.7.4 Noncausal Wiener Filter 872
12.8 Summary and References 873
Problems 874
13 Adaptive Filters 880
13.1 Applications of Adaptive Filters 880
13.1.1 System Identification or System Modeling 882
13.1.2 Adaptive Channel Equalization 883
13.1.3 Echo Cancellation in Data Transmission over Telephone Channels 887
13.1.4 Suppression of Narrowband Interference in a Wideband Signal 891
13.1.5 Adaptive Line Enhancer 895
13.1.6 Adaptive Noise Cancelling 896
13.1.7 Linear Predictive Coding of Speech Signals 897
13.1.8 Adaptive Arrays 900
13.2 Adaptive Direct-Form FIR Filters--The LMS Algorithm 902
13.2.1 Minimum Mean-Square-Error Criterion 903
13.2.2 The LMS Algorithm 905
13.2.3 Related Stochastic Gradient Algorithms 907
13.2.4 Properties of the LMS Algorithm 909
13.3 Adaptive Direct-Form Filters--RLS Algorithms 916
13.3.1 RLS Algorithm 916
13.3.2 The LDU Factorization and Square-Root Algorithms 921
13.3.3 Fast RLS Algorithms 923
13.3.4 Properties of the Direct-Form RLS Algorithms 925
13.4 Adaptive Lattice-Ladder Filters 927
13.4.1 Recursive Least-Squares Lattice-Ladder Algorithms 928
13.4.2 Other Lattice Algorithms 949
13.4.3 Properties of Lattice-Ladder Algorithms 950
13.5 Summary and References 954
Problems 955
14 Power Spectrum Estimation 960
14.1 Estimation of Spectra from Finite-Duration Observations of Signals 961
14.1.1 Computation of the Energy Density Spectrum 961
14.1.2 Estimation of the Autocorrelation and Power Spectrum of Random Signals: The Periodogram 966
14.1.3 The Use of the DFT in Power Spectrum Estimation 971
14.2 Nonparametric Methods for Power Spectrum Estimation 974
14.2.1 The Bartlett Method: Averaging Periodograms 974
14.2.2 The Welch Method: Averaging Modified Periodograms 975
14.2.3 The Blackman and Tukey Method: Smoothing the Periodogram 978
14.2.4 Performance Characteristics of Nonparametric Power Spectrum Estimators 981
14.2.5 Computational Requirements of Nonparametric Power Spectrum Estimates 984
14.3 Parametric Methods for Power Spectrum Estimation 986
14.3.1 Relationships Between the Autocorrelation and the Model Parameters 988
14.3.2 The Yule-Walker Method for the AR Model Parameters 990
14.3.3 The Burg Method for the AR Model Parameters 991
14.3.4 Unconstrained Least-Squares Method for the AR Model Parameters 994
14.3.5 Sequential Estimation Methods for the AR Model Parameters 995
14.3.6 Selection of AR Model Order 996
14.3.7 MA Model for Power Spectrum Estimation 997
14.3.8 ARM A Model for Power Spectrum Estimation 999
14.3.9 Some Experimental Results 1001
14.4 Filter Bank Methods 1009
14.4.1 Filter Bank Realization of the Periodogram 1010
14.4.2 Minimum Variance Spectral Estimates 1012
14.5 Eigenanalysis Algorithms for Spectrum Estimation 1015
14.5.1 Pisarenko Harmonic Decomposition Method 1017
14.5.2 Eigen-decomposition of the Autocorrelation Matrix for Sinusoids in White Noise 1019
14.5.3 MUSIC Algorithm 1021
14.5.4 ESPRIT Algorithm 1022
14.5.5 Order Selection Criteria 1025
14.5.6 Experimental Results 1026
14.6 Summary and References 1029
Problems 1030
A Random Number Generators 1041
B Tables of Transition Coefficients for the Design of Linear-Phase FIR Filters 1047
References and Bibliography 1053
Answers to Selected Problems 1067
Index 1077