1 INTRODUCTION 1
2 DISCRETE-TIME SIGNALS AND SYSTEMS 8
2.0 Introduction 8
2.1 Discrete-Time Signals: Sequences 9
2.1.1 Basic Sequences and Sequence Operations 11
2.2 Discrete-Time Systems 16
2.2.1 Memoryless Systems 18
2.2.2 Linear Systems 18
2.2.3 Time-Invariant Systems 20
2.2.4 Causality 21
2.2.5 Stability 21
2.3 Linear Time-Invariant Systems 22
2.4 Properties of Linear Time-Invariant Systems 28
2.5 Linear Constant-Coefficient Difference Equations 34
2.6 Frequency-Domain Representation of Discrete-Time Signals and Systems 40
2.6.1 Eigenfunctions for Linear Time-Invariant Systems 40
2.6.2 Suddenly Applied Complex Exponential Inputs 46
2.7 Representation of Sequences by Fourier Transforms 48
2.8 Symmetry Properties of the Fourier Transform 55
2.9 Fourier Transform Theorems 58
2.9.1 Linearity of the Fourier Transform 59
2.9.2 Time Shifting and Frequency Shifting 59
2.9.3 Time Reversal 60
2.9.4 Differentiation in Frequency 60
2.9.5 Parseval s Theorem 60
2.9.6 The Convolution Theorem 60
2.9.7 The Modulation or Windowing Theorem 61
2.10 Discrete-Time Random Signals 65
2.11 Summary 70
Problems 70
3 THE Z-TRANSFORM 94
3.0 Introduction 94
3.1 z-Transform 94
3.2 Properties of the Region of Convergence for the z-Transform 105
3.3 The Inverse z-Transform 111
3.3.1 Inspection Method 111
3.3.2 Partial Fraction Expansion 112
3.3.3 Power Series Expansion 116
3.4 z-Transform Properties 119
3.4.1 Linearity 119
3.4.2 Time Shifting 120
3.4.3 Multiplication by an Exponential Sequence 121
3.4.4 Differentiation of X(z) 122
3.4.5 Conjugation of a Complex Sequence 123
3.4.6 Time Reversal 123
3.4.7 Convolution of Sequences 124
3.4.8 Initial-Value Theorem 126
3.4.9 Summary of Some z-Transform Properties 126
3.5 Summary 126
Problems 127
4 SAMPLING OF CONTINUOUS-TIME SIGNALS 140
4.0 Introduction 140
4.1 Periodic Sampling 140
4.2 Frequency-Domain Representation of Sampling 142
4.3 Reconstruction of a Bandlimited Signal from Its Samples 150
4.4 Discrete-Time Processing of Continuous-Time Signals 153
4.4.1 Linear Time-Invariant Discrete-Time Systems 154
4.4.2 Impulse Invariance 160
4.5 Continuous-Time Processing of Discrete-Time Signals 163
4.6 Changing the Sampling Rate Using Discrete-Time Processing 167
4.6.1 Sampling Rate Reduction by and Integer Factor 167
4.6.2 Increasing the Sampling Rate by and Integer Factor 172
4.6.3 Changing the Sampling Rate by a Noninteger Factor 176
4.7 Multirate Signal Processing 179
4.7.1 Interchange of Filtering and Downsampling/Upsampling 179
4.7.2 Polyphase Dccompositions 180
4.7.3 Polyphase Implementation of Decimation Filters 182
4.7.4 Polyphase Implementation of Interpolation Filters 183
4.8 Digital Processing of Analog Signals 185
4.8.1 Prefiltering to Avoid Aliasing 185
4.8.2 Analog-to-Digital (A/D)Conversion 187
4.8.3 Analysis of Quantization Errors 193
4.8.4 D/A Conversion 197
4.9 Oversampling and Noise Shaping in A/D and D/A Conversion 201
4.9.1 Oversampled A/D Conversion with Direct Quantization 201
4.9.2 Oversampled A/D Conversion with Noise Shaping 206
4.9.3 Oversampling and Noise Shaping in D/A Conversion 210
4.10 Summary 213
Problems 214
5 TRANSFORM ANALYSIS OF LINEAR TIME-INVARIANT SYSTEMS 240
5.0 Introduction 240
5.1 The Frequency Response of LTI Systems 241
5.1.1 Ideal Frequency Selective Filters 241
5.1.2 Phase Distortion and Delay 242
5.2 System Functions for Systems Characterized by Linear Constant-Coefficient Difference Equations 245
5.2.1 Stability and Causality 247
5.2.2 Inverse Systems 248
5.2.3 Impulse Response for Rational System Functions 250
5.3 Frequency Response for Rational System Functions 253
5.3.1 Frequency Response of a Single Zero or Pole 258
5.3.2 Examples with Multiple Poles and Zeros 265
5.4 Relationship between Magnitude and Phase 270
5.5 All-Pass Systems 274
5.6 Minimum-Phase Systems 280
5.6.1 Minimum-Phase and All-Pass Decomposition 280
5.6.2 Frequency-Response Compensation 282
5.6.3 Properties of Minimum-Phase Systems 287
5.7 Linear Systems with Generalized Linear Phase 291
5.7.1 Systems with Linear Phase 292
5.7.2 Generalized Linear Phase 295
5.7.3 Causal Generalized Linear-Phase Systems 297
5.7.4 Relation of FIR Linear-Phase Systems to Minimum-Phase Systems 308
5.8 Summary 311
Problems 312
6 STRUCTURES FOR DISCRETE-TIME SYSTEMS 340
6.0 Introduction 340
6.1 Block Diagram Representation of Linear Constant-Coefficient Difference Equations 341
6.2 Signal Flow Graph Representation of Linear Constant-Coefficient Difference Equations 348
6.3 Basic Structures for IIR Systems 354
6.3.1 Direct Forms 354
6.3.2 Cascade Form 356
6.3.3 Parallel Form 359
6.3.4 Feedback in IIR Systems 361
6.4 Transposed Forms 363
6.5 Basic Network Structures for FIR Systems 366
6.5.1 Direct Form 367
6.5.2 Cascade Form 367
6.5.3 Structures for Linear-Phase FIR Systems 368
6.6 Overview of Finite-Precision Numerical Effects 370
6.6.1 Number Representations 371
6.6.2 Quantization in Implementing Systems 374
6.7 The Effects of Coefficient Quantization 377
6.7.1 Effects of Coefficient Quantization in IIR Systems 377
6.7.2 Example of Coefficient Quantization in an Elliptic Filter 379
6.7.3 Poles of Quantized Second-Order Sections 382
6.7.4 Effects of Coefficient Quantization in FIR Systems 384
6.7.5 Example of Quantization of an Optimum FIR Filter 386
6.7.6 Maintaining Linear Phase 390
6.8 Effects of Round-off Noise in Digital Filters 391
6.8.1 Analysis of the Direct-Form IIR Structures 391
6.8.2 Scaling in Fixed-Point Implementations of IIR Systems 399
6.8.3 Example of Analysis of a Caseade IIR Structure 403
6.8.4 Analysis of Direct-Form FIR Systems 410
6.8.5 Floating-Point Realizations of Discrete-Time Systems 412
6.9 Zero-Input Limit Cycles in Fixed-Point Realizations of IIR Digital Filters 413
6.9.1 Limit Cycles due to Round-off and Truncation 414
6.9.2 Limit Cycles Due to Overflow 416
6.9.3 Avoiding Limit Cycles 417
6.10 Summary 418
Problems 419
7 FILTER DESIGN TECHNIQUES 439
7.0 Introduction 439
7.1 Design of Discrete-Time IIR Filters from Continuous-Time Filters 442
7.1.1 Filter Design by Impulse Invariance 443
7.1.2 Bilinear Transformation 450
7.1.3 Examples of Bilinear Transformation Design 454
7.2 Design of FIR Filters by Windowing 465
7.2.1 Properties of Commonly Used Windows 467
7.2.2 Incorporation of Generalized Linear Phase 469
7.2.3 The Kaiser Window Filter Design Method 474
7.2.4 Relationship of the Kaiser Window to Other Windows 478
7.3 Examples of FIR Filter Design by the Kaiser Window Method 478
7.3.1 Highpass Filter 479
7.3.2 Discrete-Time Differentiatiors 482
7.4 Optimum Approximations of FIR Filters 486
7.4.1 Optimal Type I Lowpass Filters 491
7.4.2 Optimal Type II Lowpass Filters 497
7.4.3 The Parks-McClellan Algorithm 498
7.4.4 Characteristics of Optimum FIR Filters 501
7.5 Examples of FIR Equiripple Approximation 503
7.5.1 Lowpass Filter 503
7.5.2 Compensation for Zero-Order Hold 506
7.5.3 Bandpass Filter 507
7.6 Comments on IIR and FIR Discrete-Time Filters 510
7.7 Summary 511
Problems 511
8 THE DISCRETE FOURIER TRANSFORM 541
8.0 Introduction 541
8.1 Representation of Periodic Sequences: The Discrete Fourier Series 542
8.2 Properties of the Discrete Fourier Series 546
8.2.1 Linearity 546
8.2.2 Shift of a Sequence 546
8.2.3 Duality 547
8.2.4 Symmetry Properties 547
8.2.5 Periodic Convolution 548
8.2.6 Summary of Properties of the DFS Representation of Periodic Sequences 550
8.3 The Fourier Transform of Periodic Signals 551
8.4 Sampling the Fourier Transform 555
8.5 Fourier Representation of Finite-Duration Sequences: The Discrete Fourier Transform 559
8.6 Properties of the Discrete Fourier Transform 564
8.6.1 Linearity 564
8.6.2 Circular Shift of a Sequence 564
8.6.3 Duality 567
8.6.4 Symmetry Properties 568
8.6.5 Circular Convolution 571
8.6.6 Summary of Properties of the Discrete Fourier Transform 575
8.7 Linear Convolution Using the Discrete Fourier Transform 576
8.7.1 Linear Convolution of Two Finite-Length Sequences 577
8.7.2 Circular Convolution as Linear Convolution with Aliasing 577
8.7.3 Implementing Linear Time-Invariant Systems Using the DFT 582
8.8 The Discrete Cosine Transform (DCT) 589
8.8.1 Definitions of the DCT 589
8.8.2 Definition of the DCT-1 and DCT-2 590
8.8.3 Relationship between the DFT and the DCT-1 593
8.8.4 Relationship between the DFT and the DCT-2 594
8.8.5 Energy Compaction Property of the DCT-2 595
8.8.6 Application of the DCT 598
8.9 Summary 599
Problems 600
9 COMPUTATION OF THE DISCRETE FOURIER TRANSFORM 629
9.0 Introduction 629
9.1 Efficient Computation of the Discrete Fourier Transform 630
9.2 The Goertzel Algorithm 633
9.3 Decimation-in-Time FFT Algorithms 635
9.3.1 In-Place Computations 640
9.3.2 Alternative Forms 643
9.4 Decimation-in-Frequency FFT Algorithms 646
9.4.1 In-Place Computation 650
9.4.2 Alternative Forms 650
9.5 Practical Considerations 652
9.5.1 Indexing 652
9.5.2 Coefficients 654
9.5.3 Algorithms for More General Values of N 655
9.6 Implementation of the DFT Using Convolution 655
9.6.1 Overview of the Winograd Fourier Transform Algorithm 655
9.6.2 The Chirp Transform Algorithm 656
9.7 Effects of Finite Register Length 661
9.8 Summary 669
Problems 669
10 FOURIER ANALYSIS OF SIGNALS USING THE DISCRETE FOURIER TRANSFORM 693
10.0 Introduction 693
10.1 Fourier Analysis of Signals Using the DFT 694
10.2 DFT Analysis of Sinusoidal Signals 697
10.2.1 The Effect of Windowing 698
10.2.2 The Effect of Spectral Sampling 703
10.3 The Time-Dependent Fourier Transform 714
10.3.1 The Effect of the Window 717
10.3.2 Sampling in Time and Frequency 718
10.4 Block Convolution Using the Time-Dependent Fourier Transform 722
10.5 Fourier Analysis of Nonstationary Signals 723
10.5.1 Time-Dependent Fourier Analysis of Speech Signals 724
10.5.2 Time-Dependent Fourier Analysis of Radar Signals 728
10.6 Fourier Analysis of Stationary Random Signals: The Periodogram 730
10.6.1 The Periodogram 731
10.6.2 Properties of the Periodogram 733
10.6.3 Periodogram Averaging 737
10.6.4 Computation of Average Periodograms Using the DFT 739
10.6.5 An Example of Periodogram Analysis 739
10.7 Spectrum Analysis of Random signals Using Estimates of the Autocorrelation Sequence 743
10.7.1 Computing Correlation and Power Spectrum Estimates Using the DFT 746
10.7.2 An Example of Power Spectrum Estimation Based on Estimation of the Autocorrelation Sequence 748
10.8 Summary 754
Problems 755
11 DISCRETE HILBERT TRANSFORMS 775
11.0 Introduction 775
11.1 Real-and Imaginary-Part Sufficiency of the Fourier Transform for Causal Sequences 777
11.2 Sufficiency Theorems for Finite-Length Sequences 782
11.3 Relationships Between Magnitude and Phase 788
11.4 Hilbert Transform Relations for Complex Sequences 789
11.4.1 Design of Hilbert Transformers 792
11.4.2 Representation of Bandpass Signals 796
11.4.3 Bandpass Sampling 799
11.5 Summary 801
Problems 802
APPENDIX A RANDOM SIGNALS 811
A.1 Discrete-Time Random Processes 811
A.2 Averages 813
A.2.1 Definitions 813
A.2.2 Time Averages 815
A.3 Properties of Correlation and Covariance Sequences 817
A.4 Fourier Transform Representation of Random Signals 818
A.5 Use of the z-Transform in Average Power Computations 820
APPENDIX B CONTINUOUS-TIME FILTERS 824
B.1 Butterworth Lowpass Filters 824
B.2 Chebyshev Filters 826
B.3 Elliptic Filters 828
APPENDIX C ANSWERS TO SELECTED BASIC PROBLEMS 830
BIBLIOGRAPHY 851
INDEX 859
Example2.1 Combining Basic Sequences 13
Example2.2 Periodic and Aperiodic Discrete-Time Sinusoids 15
Example2.3 The Ideal Delay System 17
Example2.4 Moving Average 17
Example2.5 A Memoryless System 18
Example2.6 The Accumulator System 19
Example2.7 A Nonlinear System 19
Example2.8 The Accumulator as a Time-Invariant System 20
Example2.9 The Compressor System 20
Example2.10 The Forward and Backward Difference Systems 21
Example2.11 Testing for Stability or Instability 22
Example2.12 Computation of the Convolution Sum 25
Example2.13 Analytical Evaluation of the Convolution Sum 26
Example2.14 Difference Equation Representation of the Accumulator 34
Example2.15 Differentce Equation Representation of the Moving-Average Systgem 35
Example2.16 Recursive Computation of Difference Equations 37
Example2.17 Frequency Response of the Ideal Delay System 41
Example2.18 Sinusoidal Response of LTI Systems 42
Example2.19 Ideal Frequency-Selective Filters 43
Example2.20 Frequency Response of the Moving-Average System 44
Example2.21 Absolute Summability for a Suddenly-Applied Exponential 51
Example2.22 Square-Summability for the Ideal Lowpass Filter 52
Example2.23 Fourier Transform of a Constant 53
Example2.24 Fourier Transform of Complex Exponential Sequences 54
Example2.25 Illustration of Symmetry Properties 57
Example2.26 Determining a Fourier Transform Using Tables 2.2 and 2.3 63
Example2.27 Determining an Inverse Fourier Transform Using Tables 2.2 and 2.3 63
Example2.28 Determining the Impulse Response from the Frequency Response 64
Example2.29 Determining the Impulse Response for a Difference Equation 64
Example2.30 White Noise 69
Example3.1 Right-Sided Exponential Sequence 98
Example3.2 Left-Sided Exponential Sequence 99
Example3.3 Sum of Two Exponential Sequences 100
Example3.4 Sum of Two Exponentials (Again) 101
Example3.5 Two-Sided Exponential Sequence 102
Example3.6 Finite-Length Sequence 103
Example3.7 Stability, Causality, and the ROC 110
Example3.8 Second-Order z-Transform 113
Example3.9 Inverse by Partial Fractions 115
Example3.10 Finite-Length Sequence 117
Example3.11 Inverse Transform by Power Series Expansion 117
Example3.12 Power Series Expansion by Long Division 118
Example3.13 Power Series Expansion for a Left-Sided Sequence 118
Example3.14 Shifted Exponential Sequence 120
Example3.15 Exponential Multiplication 121
Example3.16 Inverse of Non-Rational z-Transform 122
Example3.17 Second-Order Pole 123
Example3.18 Time-Reversed Exponential Sequence 124
Example3.19 Evaluating a Convolution Using the z-Transform 125
Example4.1 Sampling and Reconstruction of a Sinusoidal Signal 147
Example4.2 Aliasing in the Reconstruction of an Undersampled Sinusoidal Signal 148
Example4.3 A Second Example of Aliasing 149
Example4.4 Ideal Continuous-Time Lowpass Filtering Using a Discrete-Time Lowpass Filter 155
Example4.5 Discrete-Time Implementation of an Ideal Continuous-Time Bandlimited Differentiator 158
Example4.6 Illustration of Example 4.5 with a Sinusoidal Input 159
Example4.7 A Discrete-Time Lowpass Filter Obtained By Impulse Invariance 162
Example4.8 Impulse Invariance Applied to Continuous-Time Systems with Rational System Functions 162
Example4.9 Noninteger Delay 164
Example4.10 Moving-Average System with Noninteger Delay 165
Example4.11 SamplingRate Conversion by a Noninteger Rational Factor 177
Example4.12 Quantization Error For a Sinusoidal Signal 194
Example5.1 Effects of Attenuation and Group Delay 243
Example5.2 Second-Order System 246
Example5.3 Determining the ROC 247
Example5.4 Inverse System for First-Order System 249
Example5.5 Inverse for System with a Zero in the ROC 250
Example5.6 A First-Order IIR System 251
Example5.7 A Simple FIR System 252
Example5.8 Second-Order IIR System 265
Example5.9 Second-Order FIR System 268
Example5.10 Third-Order IIR System 268
Example5.11 Systems with the Same C (z) 271
Example5.13 First-and Second-Order All-Pass Systems 275
Example5.14 Minimum-Phase/All-Pass Decomposition 281
Example5.15 Compensation of an FIR System 283
Example5.16 Ideal Lowpass with Linear Phase 293
Example5.17 Type I Linear-Phase System 300
Example5.18 Type II Linear-Phase System 302
Example5.19 Type III Linear-Phase System 302
Example5.20 Type IV Linear-Phase System 302
Example5.21 Decomposition of a Linear-Phase System 308
Example6.1 Block Diagram Representation of a Difference Equation 342
Example6.2 Direct Form I and Direct Form II Implementation of and LTI System 347
Example6.3 Determination of the System Function from a Flow Graph 352
Example6.4 Illustration of Direct Form I and Direct Form II Structures 355
Example6.5 Illustration of Cascade Structures 358
Example6.6 Illustration of Parallel-Form Structures 360
Example6.7 Transposed Form for a First-Order System with No Zeroes 363
Example6.8 Transposed Form for a Basic Second-Order Section 364
Example6.9 Round-Off Noise in a First-Order System 396
Example6.10 Round-Off Noise in a Second-Order System 397
Example6.11 Interaction Between Scaling and Round-off Noise 402
Example6.12 Scaling Considerations for the FIR System in Section 6.7.5 411
Example6.13 Limit Cycle Behavior in a First-Order System 414
Example6.14 Overflow Oscillations in a Second-Order System 416
Example7.1 Determining Specifications for a Discrete-Time Filter 440
Example7.2 Impulse Invariance with a Butterworth Filter 446
Example7.3 Bilinear Transformation of a Butterworth Filter 454
Example7.4 Butterworth Approximation 458
Example7.5 Chebyshev Approximation 460
Example7.6 Elliptic Approximation 463
Example7.7 Linear-Phase Lowpass Filter 472
Example7.8 Kaiser Window Design of a Lowpass Filter 476
Example7.9 Kaiser Window Design of a Hisghpass Filter 479
Example7.10 Kaiser Window Design of a Differentiator 483
Example7.11 Alternation Theorem and Polynomials 490
Example8.1 Discrete Fourier Series of a Periodic Impulse Train 544
Example8.2 Duality in the Discrete Fourier Series 544
Example8.3 The Discrete Fourier Series of a Periodic Rectangular Pulse Train 545
Example8.4 Periodic Convolution 549
Example8.5 The Fourier Transform of a Periodic Impulse Train 552
Example8.6 Relationship Between the Fourier Series Coefficients and the Fourier Transform of One Period 554
Example8.7 The DFT of a Rectangular Pulse 561
Example8.8 Circular Shift of a Sequence 566
Example8.9 The Duality Relationship for the DFT 568
Example8.10 Circular Convolution with a Delayed Impulse Sequence 572
Example8.11 Circular Convolution of Two Rectangular Pulses 573
Example8.12 Circular Convolution as Linear Convolution with Aliasing 579
Example8.13 Energy Compaction in the DCT-2 596
Example9.1 Chirp Transform Parameters 661
Example10.1 Fourier Analysis Using the DFT 697
Example10.2 Relationship Between DFT Values 697
Example10.3 Effcct of Windowing on Fourier Analysis of Sinusoidal Signals 698
Example10.4 Illustration of the Effect of Spectral Sampling 703
Example10.5 Spectral Sampling with Frequencies Matching DFT Frequencies 706
Example10.6 DFT Analysis of Sinusoidal Signals Using a Kaiser Window 708
Example10.7 DFT Analysis with 32-point Kaiser Window and Zero-Padding 711
Example10.8 Oversampling and Linear Interpolation for Frequency Estimation 713
Example10.9 Time-Dependent Fourier Transform of a Linear Chirp Signal 715
Example10.10 Spectrogram Display of the Time-Dependent Fourier Transform of Speech 725
Example11.1 Finite-Length Sequence 779
Example11.2 Exponential Sequence 779
Example11.3 Periodic Sequence 787
Example11.4 Kaiser Window Design of Hilbert Transformers 793
ExampleA.1 Noise Power Output of Ideal Lowpass Filter 820
ExampleA.2 Noise Power Output of a Second-Order IIR Filter 823