1 INTRODUCTION 2
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 7
1.2.2 Continuous-Time Versus Discrete-Time Signals 8
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 14
1.3.1 Continuous-Time Sinusoidal Signals 14
1.3.2 Discrete-Time Sinusoidal Signals 16
1.3.3 Harmonically Related Complex Exponentials 19
1.4 Analog-to-Digital and Digital-to-Analog Conversion 21
1.4.1 Sampling of Analog Signals 23
1.4.2 The Sampling Theorem 29
1.4.3 Quantization of Continuous-Amplitude Signals 33
1.4.4 Quantization of Sinusoidal Signals 36
1.4.5 Coding of Quantized Samples 38
1.4.6 Digital-to-Analog Conversion 38
1.4.7 Analysis of Digital Signals and Systems Versus Discrete-Time Signals and Systems 39
1.5 Summary and References 39
Problems 40
2 DISCRETE-TIME SIGNALS AND SYSTEMS 43
2.1 Discrete-Time Signals 43
2.1.1 Some Elementary Discrete-Time Signals 45
2.1.2 Classification of Discrete-Time Signals 47
2.1.3 Simple Manipulations of Discrete-Time Signals 52
2.2 Discrete-Time Systems 56
2.2.1 Input-Output Description of Systems 56
2.2.2 Block Diagram Representation of Discrete-Time Systems 59
2.2.3 Classification of Discrete-Time Systems 62
2.2.4 Interconnection of Discrete-Time Systems 70
2.3 Analysis of Discrete-Time Linear Time-Invariant Systems 72
2.3.1 Techniques for the Analysis of Linear Systems 72
2.3.2 Resolution of a Discrete-Time Signal into Impulses 74
2.3.3 Response of LTI Systems to Arbitrary Inputs:The Convolution Sum 75
2.3.4 Properties of Convolution and the Interconnection of LTI Systems 82
2.3.5 Causal Linear Time-Invariant Systems 86
2.3.6 Stability of Linear Time-Invariant Systems 87
2.3.7 Systems with Finite-Duration and Infinite-Duration Impulse Response 90
2.4 Discrete-Time Systems Described by Difference Equations 91
2.4.1 Recursive and Nonrecursive Discrete-Time Systems 92
2.4.2 Linear Time-Invariant Systems Characterized by Constant-Coefficient Difference Equations 95
2.4.3 Solution of Linear Constant-Coefficient Difference Equations 100
2.4.4 The Impulse Response of a Linear Time-Invariant Recursive System 108
2.5 Implementation of Discrete-Time Systems 111
2.5.1 Structures for the Realization of Linear Time-Invariant Systems 111
2.5.2 Recursive and Nonrecursive Realizations of FIR Systems 116
2.6 Correlation of Discrete-Time Signals 118
2.6.1 Crosscorrelation and Autocorrelation Sequences 120
2.6.2 Properties of the Autocorrelation and Crosscorrelation Sequences 122
2.6.3 Correlation of Periodic Sequences 124
2.6.4 Computation of Correlation Sequences 130
2.6.5 Input-Output Correlation Sequences 131
2.7 Summary and References 134
Problems 135
3 THE Z-TRANSFORM AND ITS APPLICATION TO THE ANALYSIS OF LTI SYSTEMS 151
3.1 The ?-Transform 151
3.1.1 The Direct ?-Transform 152
3.1.2 The Inverse ?-Transform 160
3.2 Properties of the ?-Transform 161
3.3 Rational ?-Transforms 172
3.3.1 Poles and Zeros 172
3.3.2 Pole Location and Time-Domain Behavior for Causal Signals 178
3.3.3 The System Function of a Linear Time-Invariant System 181
3.4 Inversion of the ?-Transform 184
3.4.1 The Inverse ?-Transform by Contour Integration 184
3.4.2 The Inverse ?-Transform by Power Series Expansion 186
3.4.3 The Inverse ?-Transform by Partial-Fraction Expansion 188
3.4.4 Decomposition of Rational ?-Transforms 195
3.5 The One-sided ?-Transform 197
3.5.1 Definition and Properties 197
3.5.2 Solution of Difference Equations 201
3.6 Analysis of Linear Time-Invariant Systems in the ?-Domain 203
3.6.1 Response of Systems with Rational System Functions 203
3.6.2 Response of Pole-Zero Systems with Nonzero Initial Conditions 204
3.6.3 Transient and Steady-State Responses 206
3.6.4 Causality and Stability 208
3.6.5 Pole-Zero Cancellations 210
3.6.6 Multiple-Order Poles and Stability 211
3.6.7 The Schur-Cohn Stability Test 213
3.6.8 Stability of Second-Order Systems 215
3.7 Summary and References 219
Problems 220
4 FREQUENCY ANALYSIS OF SIGNALS AND SYSTEMS 230
4.1 Frequency Analysis of Continuous-Time Signals 230
4.1.1 The Fourier Series for Continuous-Time Periodic Signals 232
4.1.2 Power Density Spectrum of Periodic Signals 235
4.1.3 The Fourier Transform for Continuous-Time Aperiodic Signals 240
4.1.4 Energy Density Spectrum of Aperiodic Signals 243
4.2 Frequency Analysis of Discrete-Time Signals 247
4.2.1 The Fourier Series for Discrete-Time Periodic Signals 247
4.2.2 Power Density Spectrum of Periodic Signals 250
4.2.3 The Fourier Transform of Discrete-Time Aperiodic Signals 253
4.2.4 Convergence of the Fourier Transform 256
4.2.5 Energy Density Spectrum of Aperiodic Signals 260
4.2.6 Relationship of the Four?er Transform to the ?-Transform 264
4.2.7 The Cepstrum 265
4.2.8 The Fourier Transform of Signals with Poles on the Unit Circle 267
4.2.9 The Sampling Theorem Revisited 269
4.2.10 Frequency-Do?ain Classification of Signals:The Concept of Bandwidth 279
4.2.11 The Frequency Ranges of Some Natural Signals 282
4.2.12 Physical and Mathematical Dualities 282
4.3 Properties of the Fcurier Transform for Discrete-Time Signals 286
4.3.1 Symmetry Properties of the Fourier Transform 287
4.3.2 Fourier Transform Theorems and Properties 294
4.4 Frequency-Domain Characteristics of Linear Time-Invariant Systems 305
4.4.1 Response to Complex Exponential and Sinusoidal Signals:The Frequency Response Function 306
4.4.2 Steady-State and Transient Response to Sinusoidal Input Signals 314
4.4.3 Steady-State Response to Periodic Input Signals 315
4.4.4 Response to Aperiodic Input Signals 316
4.4.5 Relationships Between the System Function and the Frequency Response Function 319
4.4.6 Computation of the Frequency Response Function 321
4.4.7 Input-Output Correlation Functions and Spectra 325
4.4.8 Correlation Functions and Power Spectra for Randon Input Signals 327
4.5 Linear Time-Invariant Systems as Frequency-Selective Filters 330
4.5.1 Ideal Filter Characteristics 331
4.5.2 Lowpass Highpass and Bandpass Filters 333
4.5.3 Digital Resonators 340
4.5.4 Notch Filters 343
4.5.5 Comb Filters 345
4.5.6 All-Pass Filters 350
4.5.7 Digital Sinusoidal Oscillators 352
4.6 Inverse Systems and Deconvolution 355
4.6.1 Invertibility of Linear Time-Invariant Systems 356
4.6.2 Minimum-Phase Maximum-Phase and Mixed-Phase Systems 359
4.6.3 System Identification and Deconvolution 363
4.6.4 Homomorphic Deconvolution 365
4.7 Summary and References 367
Problems 368
5 THE DISCRETE FOURIER TRANSFORM:ITS PROPERTIES AND APPLICATIONS 394
5.1 Frequency Domain Sampling:The Discrete Fourier Transform 394
5.1.1 Frequency-Domain Sampling and Reconstruction of Discrete-Time Signals 394
5.1.2 The Discrete Fourier Transform(DFT) 399
5.1.3 The DFT as a Linear Transformation 403
5.1.4 Relationship of the DFT to Other Transforms 407
5.2 Properties of the DFT 409
5.2.1 Periodicity,Linearity and Symmetry Properties 410
5.2.2 Multiplication of Two DFTs and Circular Convolution 415
5.2.3 Additional DFT Propeties 421
5.3 Linear Filtering Methods Based on the DFT 425
5.3.1 Use of the DFT in Linear Filtering 426
5.3.2 Filtering of Long Data Sequences 430
5.4 Frequency Analysis of Signals Using the DFT 433
5.5 Summary and References 440
Problems 440
6 EFFICIENT COMPUTATION OF THE DFT:FAST FOURIER TRANSFORM ALGORITHMS 448
6.1 Efficient Computation of the DFT:FFT Algorithms 448
6.1.1 Direct Computation of the DFT 449
6.1.2 Divide-and-Conquer Approach to Computation of the DFT 450
6.1.3 Radix-2 FFT Algorithms 456
6.1.4 Radix-4 FFT Algorithms 465
6.1.5 Split-Radix FFT Algorithms 470
6.1.6 Implementation of FFT Algorithms 473
6.2 Applications of FFT Algorithms 475
6.2.1 Efficient Computation of the DFT of Two Real Sequences 475
6.2.2 Efficient Computation of the DFT of a 2N-Point Real Sequence 476
6.2.3 Use of the FFT Algorithm in Linear Fitering and Correlation 477
6.3 A Linear Filtering Approach to Computation of the DFT 479
6.3.1 The Goertzel Algorithm 480
6.3.2 The Chirp-?Transform Algorithm 482
6.4 Quantization Effects in the Computation of the DFT 486
6.4.1 Quantization Errors in the Direct Computation of the DFT 487
6.4.2 Quantization Errors in FFT Algorithms 489
6.5 Summary and References 493
Problems 494
7 IMPLEMENTATION OF DISCRETE-TIME SYSTEMS 500
7.1 Structures for the Realization of Discrete-Time Systems 500
7.2 Structures for FIR Systems 502
7.2.1 Direct-Form Structure 503
7.2.2 Cascade-Form Structures 504
7.2.3 Frequency-Sampling Structures 506
7.2.4 Lattice Structure 511
7.3 Structures for IIR Systems 519
7.3.1 Direct-Form Structures 519
7.3.2 Signal Flow Graphs and Transposed Structures 521
7.3.3 Cascade-Form Structures 526
7.3.4 Parallel-Form Structures 529
7.3.5 Lattice and Lattice-Ladder Structures for IIR Systems 531
7.4 State-Space System Analysis and Structures 539
7.4.1 State-Space Descriptions of Systems Characterized by Difference Equations 540
7.4.2 Solution of the State-Space Equations 543
7.4.3 Relationships Between Input-Output and State-Space Descriptions 545
7.4.4 State-Space Analysis in the z-Domain 550
7.4.5 Additional State-Space Structures 554
7.5 Representation of Numbers 556
7.5.1 Fixed-Point Representation of Numbers 557
7.5.2 Binary Floating-Point Representation of Numbers 561
7.5.3 Errors Resulting from Rounding and Truncation 564
7.6 Quantization of Fiter Coefficients 569
7.6.1 Analysis of Sensitivity to Quantization of Filter Coefficients 569
7.6.2 Quantization of Coefficients in FIR Filters 578
7.7 Round-Off Effects in Digital Filters 582
7.7.1 Limit-Cycle Oscillations in Recursive Systems 583
7.7.2 Scaling to Prevent Overflow 588
7.7.3 Statistical Characteriztion of Quantization Effects in Fixed-Point Realizations of Digital Filters 590
7.8 Summary and References 598
Problems 600
8 DESIGN OF DIGITAL FILTERS 614
8.1 General Considerations 614
8.1.1 Causality and Its Implications 615
8.1.2 Characteristics of Practical Frequency-Selective Filters 619
8.2 Design of EIR Filters 620
8.2.1 Symmetric and Antisymmetric FIR Filters 620
8.2.2 Design of Linear-Phase FIR Filters Using Windows 623
8.2.3 Design of Linear-Phase FIR Filters by the Frequency-Sampling Method 630
8.2.4 Design of Optimum Equiripple Linear-Phase FIR Filters 637
8.2.5 Design of FIR Differentiators 652
8.2.6 Design of Hilbert Transformers 657
8.2.7 Comparison of Design Methods for Linear-Phase FIR Filters 662
8.3 Design of IIR Filters From Analog Filters 666
8.3.1 IIR Filter Design by Approximation of Derivatives 667
8.3.2 IIR Filter Design by Impulse Invariance 671
8.3.3 IIR Filter Design by the Bilinear Transformation 676
8.3.4 The Matched-? Transformation 681
8.3.5 Characteristics of Commonly Used Analog Filters 681
8.3.6 Some Examples of Digital Filter Designs Based on the Bilinear Transformation 692
8.4 Frequency Transformation 692
8.4.1 Frequency Transformations in the Analog Domain 693
8.4.2 Frequency Transformations in the Digital Domain 698
8.5 Design of Digital Filters Based on Least-Squares Method 701
8.5.1 Padé Approximation Method 701
8.5.2 Least-Squares Design Methods 706
8.5.3 FIR Least-Squares Inverse(Wiener)Filters 711
8.5.4 Design of IIR Filters in the Frequency Domain 719
8.6 Summary and References 724
Problems 726
9 SAMPLING AND RECONSTRUCTION OF SIGNALS 738
9.1 Sampling of Bandpass Signals 738
9.1.1 Representation of Bandpass Signals 738
9.1.2 Sampling of Bandpass Signals 742
9.1.3 Discrete-Time Processing of Continuous-Time Signals 746
9.2 Analog-to-Digital Conversion 748
9.2.1 Sample-and-Hold 748
9.2.2 Quantization and Coding 750
9.2.3 Analysis of Quantization Errors 753
9.2.4 Oversampling A/D Converters 756
9.3 Digital-to-Analog Conversion 763
9.3.1 Sample and Hold 765
9.3.2 First-Order Hold 768
9.3.3 Linear Interpolation with Delay 771
9.3.4 Oversampling D/A Converters 774
9.4 Summary and References 774
Problems 775
10 MULTIRATE DIGITAL SIGNAL PROCESSING 782
10.1 Introduction 783
10.2 Decimation by a Factor D 784
10.3 Interpolation by a Factor I 787
10.4 Sampling Rate Conversion by a Rational Factor I/D 790
10.5 Filter Design and Implementation for Sampling-Rate Conversion 792
10.5.1 Direct-Form FIR Filter Structures 793
10.5.2 Polyphase Filter Structures 794
10.5.3 Time-Variant Filter Structures 800
10.6 Multistage Implementation of Sampling-Rate Conversion 806
10.7 Sampling-Rate Conversion of Bandpass Signals 810
10.7.1 Decimation and Interpolation by Frequency Conversion 812
10.7.2 Modulation-Free Method for Decimation and Interpolation 814
10.8 Sampling-Rate Conversion by an Arbitrary Factor 815
10.8.1 First-Order Approximation 816
10.8.2 Second-Order Approximation(Linear Interpolation) 819
10.9 Applications of Multirate Signal Processing 821
10.9.1 Design of Phase Shifters 821
10.9.2 Interfacing of Digital Systems with Different Sampling Rates 823
10.9.3 Implementation of Narrowband Lowpass Filters 824
10.9.4 Implementation of Digital Filter Banks 825
10.9.5 Subband Coding of Speech Signals 831
10.9.6 Quadrature Mirror Fiters 833
10.9.7 Transmultiplexers 841
10.9.8 Oversampling A/D and D/A Conversion 843
10.10 Summary and References 844
Problems 846
11 LINEAR PREDICTION AND OPTIMUM LINEAR FILTERS 852
11.1 Innovations Representation of a Stationary Random Process 852
11.1.1 Rational Power Spectra 854
11.1.2 Relationships Between the Filter Parameters and the Autocorrelation Sequence 855
11.2 Forward and Backward Linear Prediction 857
11.2.1 Forward Linear Prediction 857
11.2.2 Backward Liear Prediction 860
11.2.3 The Optimum Reflection Coefficients for the Lattice Forward and Backward Predictors 863
11.2.4 Relationship of an AR Process to Linear Prediction 864
11.3 Solution of the Normal Equations 864
11.3.1 The Levinson-Durbin Algorithm 865
11.3.2 The Schur Algorithm 868
11.4 Properties of the Linear Prediction-Error Filters 873
11.5 AR Lattice and ARMA Lattice-Ladder Filters 876
11.5.1 AR Lattice Structure 877
11.5.2 ARMA Processes and Lattice-Ladder Filters 878
11.6 Wiener Filters for Filtering and Prediction 880
11.6.1 FIR Wiener Filter 881
11.6.2 Orthogonality Principle in Linear Mean-Square Estimation 884
11.6.3 IIR Wiener Filter 885
11.6.4 Noncausal Wiener Filter 889
11.7 Summary and References 890
Problems 892
12 POWER SPECTRUM ESTIMATION 896
12.1 Estimation of Spectra from Finte-Duration Observations of Signals 896
12.1.1 Computation of the Energy Density Spectrum 897
12.1.2 Estimation of the Autocorrelation and Power Spectrum of Random Signals:The Peridogram 902
12.1.3 The Use of the DFT in Power Spectrum Estimation 906
12.2 Nonparametric Methods for Power Spectrum Estimation 908
12.2.1 The Bartlett Method:Averaging Periodograms 910
12.2.2 The Welch Method:Averaging Modified Periodograms 911
12.2.3 The Blackman and Tukey Method:Smoothing the Periodogram 913
12.2.4 Performance Characteristics of Nonparametric Power Spectrum Estimators 916
12.2.5 Computational Requirements of Nonparametric Power Spectrum Estimates 919
12.3 Parametric Methods for Power Spectrum Estimation 920
12.3.1 Relationships Between the Autocorrelation and the Model Parameters 923
12.3.2 The Yule-Walker Method for the AR Model Parameters 925
12.3.3 The Burg Method for the AR Model Parameters 925
12.3.4 Unconstrained Least-Squares Method for the AR Model Parameters 929
12.3.5 Sequential Estimation Methods for the AR Model Parameters 930
12.3.6 Selection of AR Model Order 931
12.3.7 MA Model for Power Spectrum Estimation 933
12.3.8 ARMA Model for Power Spectrum Estimation 934
12.3.9 Some Experimental Results 936
2.4 Minimum Variance Spectral Estimation 942
2.5 Eigenanalysis Algorithms for Spectrum Estimation 946
12.5.1 Pisarenko Harmonic Decomposition Method 948
12.5.2 Eigen-decomposition of the Autocorrelation Matrix for Sinusoids in White Noise 950
12.5.3 MUSIC Algorithm 952
12.5.4 ESPRIT Algorithm 953
12.5.5 Order Selection Criteria 955
12.5.6 Experimental Results 956
12.6 Summary and References 959
Problems 960