DIGITAL SIGNAL PROCESSING/ Principles, Algorithms, and Applications

Contents
Preface xvii

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 Nonzero 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
241
4.2 Frequency Analysis of Discrete-Time Signals
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 The Cepstrum 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
5.1.1 Response to Complex Exponential and Sinusoidal Signals: The Frequency Response Function 300
5.1.2 Steady-State and Transient Response to Sinusoidal Input Signals 301
5.1.3 Steady-State Response to Periodic Input Signals 310
5.1.4 Response to Aperiodic Input Signals 311
5.2 Frequency Response of LTI Systems
5.2.1 Frequency Response of a System with a Rational System Function 312
5.2.2 Computation of the Frequency Response Function 314
5.3 Correlation Functions and Spectra at the Output of LTI Systems 314
5.3.1 Input-Output Correlation Functions and Spectra 317
5.3.2 Correlation Functions and Power Spectra for Random Input Signals 321
5.4 Linear Time-Invariant Systems as Frequency-Selective Filters
5.4.1 Ideal Filter Characteristics 323
5.4.2 Lowpass, Highpass, and Bandpass Filters 326
5.4.3 Digital Resonators 327
5.4.4 Notch Filters 329
5.4.5 Comb Filters 335
341
345
5.4.6 All-Pass Filters
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
8.3.1 The Goertzel Algorithm
8.3.2 The Chirp-z Transform Algorithm
8.4 Quantization Effects in the Computation of the DFT
8.4.1 Quantization Errors in the Direct Computation of the DFT
8.4.2 Quantization Errors in FFT Algorithms
8.5 Summary and References
Problems
542
542
544
549
549
552
555
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
12.2 Innovations Representation of a Stationary Random Process
12.2.1 Rational Power Spectra
12.2.2 Relationships Between the Filter Parameters and the Autocorrelation Sequence
12.3 Forward and Backward Linear Prediction
12.3.1 Forward Linear Prediction
12.3.2 Backward Linear Prediction
12.3.3 The Optimum Reflection Coefficients for the Lattice Forward and Backward Predictors
12.3.4 Relationship of an AR Process to Linear Prediction
12.4 Solution of the Normal Equations
12.4.1 The Levinson-Durbin Algorithm
12.4.2 The Schur Algorithm
12.5 Properties of the Linear Prediction-Error Filters
12.6 AR Lattice and ARMA Lattice-Ladder Filters
12.6.1 AR Lattice Structure
12.6.2 ARMA Processes and Lattice-Ladder Filters
12.7 Wiener Filters for Filtering and Prediction
12.7.1 FIR Wiener Filter
12.7.2 Orthogonality Principle in Linear Mean-Square Estimation
12.7.3 IIR Wiener Filter
12.7.4 Noncausal Wiener Filter
12.8 Summary and References
Problems

13 Adaptive Filters
13.1 Applications of Adaptive Filters
13.1.1 System Identification or System Modeling
13.1.2 Adaptive Channel Equalization
13.1.3 Echo Cancellation in Data Transmission over Telephone Channels
13.1.4 Suppression of Narrowband Interference in a Wideband Signal
13.1.5 Adaptive Line Enhancer
13.1.6 Adaptive Noise Cancelling
13.1.7 Linear Predictive Coding of Speech Signals
13.1.8 Adaptive Arrays
13.2 Adaptive Direct-Form FIR Filters—The LMS Algorithm
13.2.1 Minimum Mean-Square-Error Criterion
13.2.2 The LMS Algorithm

834
836
837
838
839
841
845
846
846
847
850
855
858
858
860
863
864
866
867
872
873
874
880
880
882
883
887
891
895
896
897
900
902
903
905

DIGITAL SIGNAL PROCESSING
Principles, Algorithms, and Applications — Fourth Edition
John G. Proakis • Dimitris G. Manolakis

This fourth edition covers the fundamentals of discrete-time signals, systems, and modern digital signal processing. Appropriate for students of electrical engineering, computer engineering, and computer science, the book is suitable for undergraduate and graduate courses and provides balanced coverage of both theory and practical applications.

The first ten chapters treat basic DSP topics suitable for undergraduate-level DSP courses. The last four chapters treat more advanced DSP topics, including multirate digital signal processing, linear prediction, and optimum linear filters, adaptive filters, and power spectrum estimation. This material is appropriate for a graduate-level course in digital signal processing.

New to the fourth edition:

Newly written and updated chapter on sampling and reconstruction of signals

New addition on the discrete cosine transform

Updated chapter on multirate digital signal processing

New chapter on adaptive filters

Student Manual based on the use of MATLAB to solve problems in digital signal processing

The book also contains a large number of well-designed problems. Additionally, PowerPoint slides of text figures as well as a solutions manual are available to instructors.

Contents
Preface
1 Introduction
2 Discrete-Time Signals and Systems
3 The Z-Transform and its Application to the Analysis of LTI Systems
4 Frequency Analysis of Signals
5 Frequency-Domain Analysis of LTI Systems
6 Sampling and Reconstruction of Signals
7 The Discrete Fourier Transform: Its Properties and Applications
8 Efficient Computation of the DFT: Fast Fourier Transform Algorithms
9 Implementation of Discrete-Time Systems
10 Design of Digital Filters
11 Multirate Digital Signal Processing
12 Linear Prediction and Optimum Linear Filters
13 Adaptive Filters
14 Power Spectrum Estimation
Appendix A Random Number Generators
Appendix B Tables of Transition Coefficients for the Design of Linear-Phase FIR Filters
References and Bibliography
Answers to Selected Problems
Index

Ingeniería Electrónica