Thind Edition DIGITAL SIGNAL PROCESSING Principles,Algorithms,and Applications John G.Proakis Dimitris G.Manolakis
Digital Signal Processing Principles, Algorithms, and Applications Third Edition John G. Proakis Northeastem University Dimitris G. Manolakis Boston College PRENTICE-HALL INTERNATIONAL, INC
Contents PREFACE x成 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.7 1.2.2 Continuous-Time Versus Discrete-Time Signals.8 12.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.]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.42 The Sampling Theorem.29 1.43 Quantization of Continuous-Amplitude Signals,33 1.44 Quantization of Sinusoidal Signals.36 14.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 印
iv Contents 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 23.4 Properties of Convolution and the Interconnection of LTI Systems,82 23.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
Contents 3 THE Z-TRANSFORM AND ITS APPLICATION TO THE ANALYSIS OF LTI SYSTEMS 151 3.1 The :-Transform 151 3.1.1 The Direet :-Transform.152 3.1.2 The inverse :-Transform,160 3.2 Properties of the z-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 Senes Expansion.186 3.4.3 The Inverse :-Transform by Partial-Fraction Expansion.188 3.44 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.I 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 Stabilty.208 3.6.5 Pole-Zero Cancellations.210 3.6.6 Multiple-Order Poles and Stabihty.211 3.6.7 The Schur-Cohn Stability Test.213 3.68 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.12 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
vi Contents 4.22 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 Fourier Transform to the z-Transform.264 4.2.7 The Cepstrum.265 42.8 The Fourier Transform of Signals with Poles on the Unit Circle,267 4.29 The Sampling Theorem Revisited.269 4.2.10 Frequency-Domain 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 Fourier 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.43 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 Random 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-Phasc.Maximum-Phase,and Mixed-Phase Systems.359 4.6.3 System Identification and Deconvolution,363 4.6.4 Homomorphic Deconvolution.365
Contents i 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.]Periodicity.Linearity.and Symmetry Properties.410 5.2.2 Multiplication of Two DFTs and Circular Convolution.415 5.2.3 Additional DFT Properties.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 Filtering 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-z Transform Algorithm.482
vili Contents 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 73.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 Diflerence Equations.540) 7.4.2 Solution of the State-Space Equations.543 7.43 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 Filter 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.72 Scaling to Prevent Overfow.588 7.7.3 Statistical Characterization of Quantization Effects in Fixed-Point Realizations of Digital Filters,590 7.8 Summary and References 598 Problems 600
Contents i度 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 FIR 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 Transformations 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 Pade 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.11 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 92.2 Quantization and Coding.750 9.2.3 Analysis of Quantization Errors,753 9.2.4 Oversampling A/D Converters,756
X Contents 9.3 Digital-to-Analog Conversion 763 9.3.1 Sample and Hold.765 9.3.2 First-Order Hoid.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 787 10.4 Sampling Rate Conversion by a Rational Factor //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 Filters.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