Digital Signal Processing (4th Edition)

A significant revision of a best-selling text for the introductory digital signal processing course. This book presents the fundamentals of discrete-time signals, systems, and modern digital processing and applications for students in electrical engineering, computer engineering, and computer science.The book is suitable for either a one-semester or a two-semester undergraduate level course in discrete systems and digital signal processing. It is also intended for use in a one-semester first-year graduate-level course in digital signal processing. PREFACE 1 INTRODUCTION 1.1 Signals, Systems. and Signal Processing 2 1.1.1 Basic Elements of a D~gital 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-Tlme Signals. 8 1.2.3 Continuous-Valued Versus Discrete-Valued Signals. 10 1.2.4 Determinist~c 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 Contents 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 Finlte-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 Soiution of Linear Constant-Coefficient Difference Equations. 100 2.4.4 The Impulse Response of a Linear Tirne-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 ReaIizations 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 v 3 THE I-TRANSFORM AND ITS APPLICATION TO THE ANALYSS 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 hg Power Serles 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 Definit~on and Properties. 197 y.52 Solution of Difference Equations. 201 3.6 Analysis of Linear Time-Invariant Systems in the :-Domain 303 -3.6.1 Response ol Systems with Rational System Functions. 203 3,6.2 Response of Pole-Zero Systems with Nonzero Initial Condi~ions. 204 3.6.3 Transient and Steady-State Responses, 206 3.6.4 Causalit!, and Stability. 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.6.8 Stability of Second-Order Systems. 215 3.7 Summary and References 219 Problems 220 4 FREQUENCY ANALYSIS OF SIGNALS AND SYSTEMS 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 Contents 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 Fourier Transform to the z-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-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 MathematicaI Dualities. 282 4.3 Properties of the Fourier Transform for Discrete-Time Signals 286 4.3.1 Symmetry Properlies 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. 3% 4.4.2 Steady-State and Transient Response to Sinusaidal Input Signals. 314 4.4.3 Steady-State Response to Periodic Input Signals, 315 4.4.4 Response lo 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 Fihers. 350 4.5.7 Digital Sinusoidal Oscil~ators. 352 4.6 Inverse Systems and Deconvolution 355 4.6.1 Invertibility of Linear T~me-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 Deconvo~ution. 365 Contents 4.7 Summary and References 367 Problems 368 5 THE DISCRETE FOURIER TRANSFORM: ITS PROPERTIES AND A PPLICATIONS 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 D l T 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 Properties. 421 5.3 Linear Filtering Methods Based on the DFT 425 5.3.1 Use of thc 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 ReaI 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 D l T 479 6.3.1 The Goertzel Algorithm, 480 6.3.2 The Chirp-z Transform Algorithm, 482 viii Contents 6.4 Quantization Effects in the Compuration 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 7.1 Structures for the Realization of Discrete-Time Systems 500 7.2 Structures for FIR Svstems 502 7.2.1 Direcl-Form Structure. SO3 7.2.2 Cascade-Form Structures. 504 7.2.3 Frequency-Sampling Structurest. 506 7.2.4 Lattice Structure. 511 7.3 Structures for IIR Systems 519 7.3.1 Direct-Form Structures. 519 7.3.3 Signal Flow Graphs and Transposed Structures. 521 7.3.3 Cascade-Form Strucrures. 526 7.3.4 Parallel-Form Structures. 529 7.3.5 Latticc and Lattice-Ladder Structures for IIR Syslcms. 531 7.4 State-Space System Analvsis and Structures 5.19 7.4.1 State-Space Descriptions of Svstems Characlerizcd h! Diflerencc Equations. 540 7.4.2 Solution of the State-Space Equations. 543 7.4.3 Relationships Between Input-Outpur 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-Poinr Representation of Numbers. 557 7.5.2 Binary Floating-Point Representation of Numbers. 561 7.5.3 Errors Resulting from Rounding and Truncation. 56d 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.7.2 Scaling to Prevent Overflow. 588 7.7.3 Statistical Characterizatton of Quantization Effects in Fixed-Point Realizations of Digital Filters. 590 7.8 Summary and References 598 Problems 600 Contents 8 DESIGN OF DIGITAL FILTERS 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 Antisymmerrir FIR Filters. 620 8.2.2 Design of Linear-Phase FIR Filters Using Windows. 623 8.2,3 Design of Llnear-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 11R 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 Same 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 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 Contents 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 DIA Converters, 774 9.4 Summary and References 774 Problems 775 10 MULTIRATE DIGITAL SIGNAL PROCESSING 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 IID 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 oi 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 Oversampiing A/D and D/A Conversion. 843 10.10 Summary and References 844 Problems 846 Contents 1 I LINEAR PREDICTION AND OPTIMUM LINEAR FILTERS 11.1 Inno\.rations Representation of a Stationary Random Process 852 11.1.1 Rational Power Spectra. 853 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.3.2 Backward Linear 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 Schiir Algorithm. S6S 11.4 Properties of the Linear Prediction-Error Filters 873 11.5 AR Lattice and ARMA Lattice-Ladder Filters 876 11.5.1 AR Lalticc Structure. 677 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 Estimat~on. StiJ 11.6.3 IIR Wlener Filter. 885 11.6.4 Noncausal Wiener Filter. 889 11.7 Summary and References 890 Problems 892 12 POWER SPECTRUM ESTIMATION 896 2 . Estimation of Spectra from Finite-Duration Observations of Signals 896 12.1.1 Computation of the Energy Denslty Spectrum. 897 12.1.2 Estimation of the Autocorrelation and Power Spectrum of Random Signals: The Periodopram. 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 Periodoprams. 911 12.2.3 The Blackman and Tukey Method: Smoothing the Periodogram, 913 12.2.4 Performance Characteristics of Nonparametric Power Spectrum Estimators. 976 Contents 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. 975 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. 931 12.3.9 Some Experimental Results. 936 12.4 Minimum Variance Spectral Estimation 942 Eigenanatysis 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. 951 12.5.4 ESPRIT Algorithm. 953 12.5.5 Order Selection Crrteria. 955 12.5.6 Experimental Results. 956 2 . 6 Summary and References 959 Problems 960 A RANDOM SIGNALS, CORRELATION FUNCTIONS, AND POWER SPECTRA A1 8 RANDOM NUMBER GENERATORS 8 1 C TABLES OF TRANSITION COEFFICIENTS FOR THE DESIGN OF LINEAR-PHASE FIR FILTERS C I D LIST OF MATLAB FUNCTIONS D l REFERENCES AND BlBLlOGRAPHY R1 INDEX I1 Introduction -- Discrete-time Signals And Systems -- The Z-transform And Its Application To The Analysis Of Lti Systems -- Frequency Analysis Of Signals -- Frequency-domain Analysis Of Lti Systems -- Sampling And Reconstruction Of Signals -- The Discrete Fourier Transform: Its Properties And Applications -- Efficient Computation Of The Dft: Fast Fourier Transform Algorithms -- Implementation Of Discrete-time Systems -- Design Of Digital Filters -- Multirate Digital Signal Processing -- Linear Prediction And Optimum Linear Filters -- Adaptive Filters -- Power Spectrum Estimation. John G. Proakis, Dimitris G. Manolakis. Includes Bibliographical References (p. 1053-1066) And Index.