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 36 and Systems 1.5 Summary and References 37 Problems 37 vi Contents 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 88 Response 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 93 Constant-Coefficient Difference Equations 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 Contents vii 3 The z -Transform and Its Application to the Analysis of LT I 147 Systems 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 viii Contents 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 Aperiodk 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 265 Bandwidth 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 301 Frequency Response Function 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 Contents ix 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 AID Converters 433 6.6.2 Oversampling DI A Converters 439 6.7 Summary and References 440 Problems 440 X Contents 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 449 Signals 7.1.2 The Discrete Fourier Transform (OFT) 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 OFT 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 OFT Properties 476 7.3 Linear Filtering Methods Based on the OFT 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 OFT 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 511 Algorithms 8.1 Efficient Computation of the OFT: FFT Algorithms 511 8.1.1 Direct Computation of the DFT 512 8.1.2 Oivide-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