SECOND EDITION
`
`DISCRETE-TIME
`SIGNAL
`PROCESSING
`
`ALAN v. OPPENHEIM
`
`MASSACHUSETTS INSTITUTE OF TECHNOLOGY
`
`RoNALD W. ScHAFER
`
`GEORGIA INSTITUTE OF TECHNOLOGY
`
`WITH
`
`JoHN R. BucK
`
`UNIVERSITY OF MASSACHUSETTS DARTMOUTH
`
`PRENTICE HALL
`UPPER SADDLE RIVER, NEW JERSEY 07458
`
`IPR2016-00704
`SAINT LAWRENCE COMMUNICATIONS LLC
`Exhibit 2005
`
`

`

`Oppenheim, Alan V.
`Discrete-time signal processing I Alan V. Oppenheim, Ronald W.
`Schafer, with John R. Buck.
`2nd ed.
`em.
`p.
`Includes bibliographical references and index.
`ISBN 0-13-754920-2
`l. Signal processing-Mathematics. 2. Discrete-time systems.
`L Schafer, Ronald W.
`II. Buck, John R.
`III. Title.
`TK5102.9.067 1998
`621.382'2---dc21
`
`98-50398
`CIP
`
`Acquisitions editor: Tom Robbins
`Production service: Interactive Composition Corporation
`Editorial/production supervision: Sbaryn Vitrano
`Copy editor: Brian Baker
`Cover design: Vivian Berman
`Art director: Amy Rosen
`Managing editor: Eileen Clark
`Editor-in-Chief: Marda Horton
`Director of production and manufacturing: David W. Riccardi
`Manufacturing buyer: Pat Brown
`Editorial assistant: Dan De Pasquale
`
`© 1999,1989 Alan V. Oppenheim, Ronald W. Schafer
`Published by Prentice-Hall, Inc.
`Upper Saddle River, New Jersey 07458
`
`All rights reserved. No part of this book may be
`reproduced, in any form or by any means,
`without permission in writing from the publisher.
`
`The author and publisher of this book have used their best efforts in preparing this book. These efforts include
`the development, research, and testing of the theories and programs to determine their effectiveness. The
`author and publisher make no warranty of any kind, expressed or implied, with regard to these programs
`or the documentation contained in this book. The author and publisher shall not be liable in any event for
`incidental or consequential damages in connection with, or arising out of, the furnishing, performance, or use
`of these programs.
`
`Printed in the United States of America
`10 9 8 7 6 5 4
`
`ISBN
`
`0-13-754920-2
`
`Prentice-Hall International (UK) Limited, London
`Prentice-Hall of Australia Pty. Limited, Sydney
`Prentice-Hall Canada Inc., Toronto
`Prentice-Hall Hispanoamericana, S.A., Mexico
`Prentice-Hall of India Private Limited, New Delhi
`Prentice-Hall of Japan, Inc., Tokyo
`Simon & Schuster Asia Pte. Ltd., Singapore
`Editora Prentice-Hall do Brasil, Ltda., Rio de Janeiro
`
`

`

`To Phyllis, Justine and Jason
`
`To Dorothy, Bill, Tricia, Ken and Kate
`and in memory of John
`
`To Susan
`
`

`

`.
`
`

`

`CONTENTS
`
`LIST OF EXAMPLES XV
`
`PREFACE XIX
`
`AcKNOWLEDGMENTS xxv
`1 INTRODUCTION
`l
`2 DISCRETE-TIME SIGNALS AND SYSTEMS 8
`
`Introduction 8
`2.0
`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-ThANSFORM 94
`
`3.0
`3.1
`
`Introduction 94
`z. Transform 94
`
`vii
`
`

`

`Contents
`
`lOS
`
`viii
`
`3.4
`
`3.2 Properties of the Region of Convergence for the z-Transform
`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
`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
`
`Introduction 140
`4.0
`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 an Integer Factor 167
`4.6.2
`Increasing the Sampling Rate by an 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 Decompositions 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 AID Conversion with Direct
`Quantization 201
`4.9.2 Oversampled AID Conversion with Noise Shaping 206
`4.9.3 Oversampling and Noise Shaping in D/ A Conversion 210
`
`

`

`Contents
`
`ix
`
`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 3U
`
`6 STRUCTURES FOR DISCRETE-TIME SYSTEMS 340
`
`Introduction 340
`6.0
`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
`
`

`

`x
`
`Contents
`
`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 iu 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 Cascade 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 Cydes 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
`
`Introduction 439
`7.0
`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 Differentiators 482
`7.4 Optimum Approximations of FIR Filters 486
`7.4.1 Optimal'JYpe I Lowpass Filters 491
`7 .4.2 Optimal Type II Lowpass Filters 497
`7.4.3 The Parks-McClellan Algorithm 498
`
`

`

`Contents
`
`7.5
`
`7.6
`
`7.7
`
`501
`7.4.4 Characteristics of Optimum FIR Filters
`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
`Comments on IIR and FIR Discrete-Time Filters
`
`510
`
`Summary
`Problems
`
`511
`511
`
`THE DISCRETE FOURIER TRANSFORM 541
`
`8.0
`
`8.1
`
`8.2
`
`8.3
`
`8.4
`
`8.5
`
`8.6
`
`8.7
`
`8.8
`
`8.9
`
`Introduction 541
`
`Representation of Periodic Sequences: The Discrete Fourier
`Series
`542
`
`Properties of the Discrete Fourier Series
`8.2.1 Linearity 546
`8.2.2
`Shift of a Sequence
`8.2.3 Duality 547
`547
`8.2.4 Symmetry Properties
`8.2.5 Periodic Convolution 548
`
`546
`
`546
`
`8.2.6 Summary of Properties of the DFS Representation of Periodic
`Sequences
`550
`The Fourier 'Ii'ansform of Periodic Signals
`Sampling the Fourier 'Ii'ansform 555
`Fourier Representation of Finite-Duration Sequences: The Discrete
`Fourier 'Ii'ansform 559
`
`551
`
`Properties of the Discrete Fourier 'Ii'ansform 564
`8.6.1 Linearity 564
`8.6.2 Circular Shift of a Sequence
`8.6.3 Duality 567
`8.6.4 Symmetry Properties
`8.6.5 Circular Convolution
`
`568
`571
`
`564
`
`8.6.6 Summary of Properties of the Discrete Fourier Transform 575
`Linear Convolution Using the Discrete Fourier 'Ii'ansform 576
`8.7.1 Linear Convolution of Two Finite-Length Sequences
`577
`8.7.2 Circular Convolution as Linear Convolution with Aliasing
`8.7.3
`Implementing Linear Time-Invariant Systems Using the
`DFT 582
`
`577
`
`The Discrete Cosine 'Ii-ansform (DCT)
`8.8.1 Definitions of the DCT 589
`
`589
`
`8.8.2 Definition of the DCT-1 and DCT-2
`
`590
`
`593
`8.8.3 Relationship between the DFT and the DCT-1
`594
`8.8.4 Relationship between the DFT and the DCT-2
`8.8.5 Energy Compaction Property of the DCT-2
`595
`8.8.6 Applications of the DCT 598
`Summary
`599
`Problems
`600
`
`

`

`xii
`
`Contents
`
`COMPUTATION OF THE DISCRETE FOURIER
`
`TRANSFORM 629
`
`9.0
`
`Introduction 629
`
`Efficient Computation of the Discrete Fourier 'fi'ansfonn 630
`9.1
`The Goertzel Algorithm 633
`9.2
`9.3 Decimation-in-Time FFT Algorithms
`9.3.1
`In-Place Computations
`640
`9.3.2 Alternative Forms
`643
`
`635
`
`9.4 Decimation-in-Frequency FFT Algorithms
`9.4.1
`In—Place Computation 650
`9.4.2 Alternative Forms
`650
`
`646
`
`9.5
`
`Practical Considerations 652
`
`Indexing 652
`9.5.1
`9.5.2 Coefficients
`654
`
`9.6
`
`9.7
`9.8
`
`9.5.3 Algorithms for More General Values of N 655
`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
`Effects of Finite Register Length 661
`Summary 669
`Problems
`669
`
`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 'D'ansform 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
`
`723
`10.5 Fourier Analysis of Nonstationary Signals
`724
`10.5.1 Time-Dependent Fourier Analysis of Speech Signals
`728
`10.5.2 Time-Dependent Fourier Analysis of Radar Signals
`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
`
`

`

`Contents
`
`xiii
`
`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
`Summary 754
`Problems
`755
`
`10.8
`
`DISCRETE HILBERT TRANSFORMS 775
`
`Introduction 775
`
`11.0
`
`11.1
`
`11.2
`
`11.3
`
`11.4
`
`11.5
`
`Real- and Imaginary-Part Sufficiency of the Fourier Transform for
`Causal Sequences
`777
`Sufficiency Theorems for Finite-Length Sequences
`Relationships Between Magnitude and Phase
`788
`Hilbert Transform Relations for Complex Sequences
`11.4.1 Design of Hilbert Transformers
`792
`11.4.2 Representation of Bandpass Signals
`11.4.3 Bandpass Sampling 799
`Summary 801
`Problems
`802
`
`782
`
`789
`
`796
`
`APPENDIX A RANDOM SIGNALS
`
`811
`
`A.1
`
`A.2
`
`A.3
`
`A.4
`
`A.5
`
`Discrete-Time Random Processes
`
`811
`
`813
`Averages
`A21 Definitions
`
`813
`
`815
`A22 Time Averages
`Properties of Correlation and Covariance Sequences
`Fourier Transform Representation of Random Signals
`Use of the z-Transform in Average Power Computations
`
`817
`818
`820
`
`APPENDIX B CONTINUOUS—TIME FILTERS
`
`824
`
`B.1
`
`B.2
`
`B.3
`
`Butterworth Lowpass Filters
`Chebyshev Filters
`826
`Elliptic Filters
`828
`
`824
`
`APPENDIX C ANSWERS T0 SELECTED BASIC
`
`PROBLEMS
`
`830
`
`BIBLIOGRAPHY 851
`
`INDEX 859
`
`

`

`.
`
`

`

`LIST OF EXAMPLES
`
`Example 2.1
`Example 2.2
`Example 2.3
`Example 2.4
`Example 2.5
`Example 2.6
`Example 2.7
`Example 2.8
`Example 2.9
`Example 2.10
`Example 2.11
`Example 2.12
`Example 2.13
`Example 2.14
`Example 2.15
`
`Example 2.16
`Example 2.17
`Example 2.18
`Example 2.19
`Example 2.20
`Example 2.21
`Example 2.22
`Example 2.23
`Example 2.24
`Example 2.25
`Example 2.26
`Example 2.27
`
`Example 2.28
`
`Example 2.29
`
`Example 2.30
`Example 3.1
`Example 3.2
`Example 3.3
`Example 3.4
`Example 3.5
`Example 3.6
`Example 3.7
`
`Combining Basic Sequences ........................................ 13
`Periodic and Aperiodic Discrete—Time Sinusoids .................. 15
`The Ideal Delay System ............................................ 17
`Moving Average .................................................... 17
`A Memoryless System .............................................. 18
`The Accumulator System ........................................... 19
`A Nonlinear System ................................................ 19
`The Accumulator as a Time-Invariant System ..................... 20
`The Compressor System ............................................ 20
`The Forward and Backward Difference Systems ................... 21
`Testing for Stability or Instability ................................... 22
`Computation of the Convolution Sum ...................... . ...... 25
`Analytical Evaluation of the Convolution Sum .................... 26
`Difference Equation Representation of the Accumulator ......... 34
`Difference Equation Representation of the
`Moving-Average System ............................................ 35
`Recursive Computation of Difference Equations .................. 37
`Frequency Response of the Ideal Delay System ................... 41
`Sinusoidal Response of LTI Systems ............................... 42
`Ideal Frequency-Selective Filters ................................... 43
`Frequency Response of the Moving-Average System .............. 44
`Absolute Summability for a Suddenly-Applied Exponential ...... 51
`Square-Summability for the Ideal Lowpass Filter .................. 52
`Fourier Transform of a Constant ................................... 53
`
`Fourier Transform of Complex Exponential Sequences ........... 54
`Illustration of Symmetry Properties ................................ 57
`Determining a Fourier Transform Using Tables 2.2 and 2.3 ....... 63
`Determining an Inverse Fourier Transform Using
`Tables 2.2 and 2.3 ................................................... 63
`
`Determining the Impulse Response from the Frequency
`Response ............................................................ 64
`Determining the Impulse Response for a Difference
`Equation ............................................................ 64
`White Noise ......................................................... 69
`
`Right—Sided Exponential Sequence ................................ 98
`Left—Sided Exponential Sequence .................................. 99
`Sum of Two Exponential Sequences ............................... 100
`Sum of Two Exponentials (Again) ................................ 101
`Two-Sided Exponential Sequence ................................. 102
`Finite-Length Sequence ..................... -...................... 103
`Stability, Causality, and the ROC .................................. 110
`XV
`
`

`

`xvi
`
`Example 3.8
`Example 3.9
`Example 3.10
`Example 3.11
`Example 3.12
`Example 3.13
`Example 3.14
`Example 3.15
`Example 3.16
`Example 3.17
`Example 3.18
`Example 3.19
`Example 4.1
`Example 4.2
`
`Example 4.3
`Example 4.4
`
`Example 4.5
`
`Example 4.6
`Example 4.7
`
`Example 4.8
`
`Example 4.9
`Example 4.10
`Example 4.11
`Example 4.12
`Example 5.1
`Example 5.2
`Example 5.3
`Example 5.4
`Example 5.5
`Example 5.6
`Example 5.7
`Example 5.8
`Example 5.9
`Example 5.10
`Example 5.11
`Example 5.13
`Example 5.14
`Example 5.15
`Example 5.16
`Example 5.17
`Example 5.18
`Example 5.19
`
`List of Examples
`
`Second-Order z—Transform ................................ . ....... 113
`
`Inverse by Partial Fractions ........................................ 115
`Finite-Length Sequence ........................................... 117
`Inverse Transform by Power Series Expansion ................... 117
`Power Series Expansion by Long Division ........................ 118
`Power Series Expansion for a Left-Sided Sequence .............. 118
`Shifted Exponential Sequence ................................ .. . .. 120
`Exponential Multiplication ........................................ 121
`Inverse of Non-Rational z-Transform ............................. 122
`
`Second-Order Pole ................................................. 123
`
`Time—Reversed Exponential Sequence ............................ 124
`Evaluating a Convolution Using the z-Transform ................ 125
`Sampling and Reconstruction of a Sinusoidal Signal ............. 147
`Aliasing in the Reconstruction of an Undersampled
`Sinusoidal Signal ................................................... 148
`A Second Example of Aliasing .................................... 149
`Ideal Continuous-Time Lowpass Filtering Using a
`Discrete-Time Lowpass Filter ..................................... 155
`Discrete—Time Implementation of an Ideal
`Continuous-Time Bandlimited Differentiator .................... 158
`
`Illustration of Example 4.5 with a Sinusoidal Input ..... . ......... 159
`A Discrete-Time LOWpaSS Filter Obtained By Impulse
`Invariance .......................................................... 162
`
`Impulse Invariance Applied to Continuous-Time Systems
`with Rational System Functions ................................... 162
`Noninteger Delay .................................................. 164
`Moving-Average System with Noninteger Delay ................. 165
`Sampling Rate Conversion by a Noninteger Rational Factor ..... 177
`Quantization Error For a Sinusoidal Signal ....................... 194
`Effects of Attenuation and Group Delay ......................... 243
`Second-Order System .............................................. 246
`Determining the ROC ............................................. 247
`Inverse System for First-Order System ............................ 249
`Inverse for System with a Zero in the ROC ....................... 250
`A First—Order IIR System ......................................... 251
`A Simple FIR System ................ . ............................. 252
`Second-Order IIR System ......................................... 265
`Second-Order FIR System ......................................... 268
`Third-Order IIR System ........................................... 268
`Systems with the Same C(z) ....................................... 271
`First- and Second-Order All-Pass Systems ........................ 275
`Minimum—Phase /All-Pass Decomposition ........................ 281
`Compensation of an FIR System .................................. 283
`Ideal Lowpass with Linear Phase .................................. 293
`Type I Linear—Phase System ....................................... 300
`Type II Linear-Phase System ...................................... 302
`Type III Linear-Phase System ..................................... 302
`
`

`

`List of Examples
`
`Example 5.20
`Example 5.21
`Example 6.1
`Example 6.2
`
`Example 6.3
`Example 6.4
`Example 6.5
`Example 6.6
`Example 6.7
`Example 6.8
`Example 6.9
`Example 6.10
`Example 6.11
`Example 6.12
`Example 6.13
`Example 6.14
`Example 7.1
`Example 7.2
`Example 7.3
`Example 7.4
`Example 7.5
`Example 7.6
`Example 7.7
`Example 7.8
`Example 7.9
`Example 7.10
`Example 7.11
`Example 8.1
`Example 8.2
`Example 8.3
`
`Example 8.4
`Example 8.5
`Example 8.6
`
`Example 8.7
`Example 8.8
`Example 8.9
`Example 8.10
`Example 8.11
`Example 8.12
`Example 8.13
`Example 9.1
`Example 10.1
`Example 10.2
`
`xvii
`
`Type IV Linear-Phase System ..................................... 302
`Decomposition of a Linear-Phase System ......................... 308
`Block Diagram Representation of a Difference Equation ........ 342
`Direct Form I and Direct Form II Implementation of an LTI
`System .............................................................. 347
`Determination of the System Function from a Flow Graph ...... 352
`Illustration of Direct Form I and Direct Form II Structures ...... 355
`
`Illustration of Cascade Structures ................................. 358
`
`Illustration of Parallel-Form Structures ........................... 360
`
`Transposed Form for a First-Order System with No Zeroes ...... 363
`Transposed Form for a Basic Second-Order Section .............. 364
`Round-off Noise in a First-Order System ......................... 396
`Round-off Noise in a Second—Order System ...................... 397
`Interaction Between Scaling and Round-off Noise ............... 402
`Scaling Considerations for the FIR System in Section 6.7.5 ...... 411
`Limit Cycle Behavior in a First-Order System .................... 414
`Overflow Oscillations in a Second-Order System ................. 416
`Determining Specifications for a Discrete-Time Filter ............ 440
`Impulse Invariance with a Butterworth Filter ..................... 446
`Bilinear Transformation of a Butterworth Filter .................. 454
`
`Butterworth Approximation ....................................... 458
`Chebyshev Approximation ........................................ 460
`Elliptic Approximation ............................................ 463
`Linear—Phase Lowpass Filter ...................................... 472
`Kaiser Window Design of a Lowpass Filter ....................... 476
`Kaiser Window Design of a Highpass Filter ....................... 479
`Kaiser Window Design of a Differentiator ........................ 483
`Alternation Theorem and Polynomials ............................ 490
`Discrete Fourier Series of a Periodic Impulse Train .............. 544
`Duality in the Discrete Fourier Series ............................. 544
`The Discrete Fourier Series of a Periodic Rectangular Pulse
`Train ................................................................ 545
`
`Periodic Convolution .............................................. 549
`
`The Fourier Transform of a Periodic Impulse Train ............... 552
`Relationship Between the Fourier Series Coefficients and
`the Fourier Transform of One Period ............................. 554
`
`The DFT of a Rectangular Pulse .................................. 561
`Circular Shift of a Sequence ....................................... 566
`The Duality Relationship for the DFT ............................ 568
`Circular Convolution with a Delayed Impulse Sequence ......... 572
`Circular Convolution of Two Rectangular Pulses ................. 573
`Circular Convolution as Linear Convolution with Aliasing ...... 579
`Energy Compaction in the DCT-2 ................................. 596
`Chirp Transform Parameters ...... . ............................... 661
`Fourier Analysis Using the DFT .................................. 697
`Relationship Between DFT Values ............................... 697
`
`

`

`xviii
`
`Example 10.3
`
`Example 10.4
`Example 10.5
`
`Example 10.6
`Example 10.7
`
`Example 10.8
`
`Example 10.9
`Example 10.10
`
`Example 11.1
`Example 11.2
`Example 11.3
`Example 11.4
`Example A.1
`Example A.2
`
`List of Examples
`
`Effect of Windowing on Fourier Analysis of Sinusoidal
`Signals .............................................................. 698
`Illustration of the Effect of Spectral Sampling .................... 703
`Spectral Sampling with Frequencies Matching DFT
`Frequencies ....................................................... 706
`DFT Analysis of Sinusoidal Signals Using a Kaiser Window ..... 708
`DFT Analysis with 32-p—oint Kaiser Window and
`Zero-Padding ...................................................... 711
`Oversampling and Linear Interpolation for Frequency
`Estimation ......................................................... 713
`
`.
`
`. 715
`
`Time-Dependent Fourier Transform of a Linear Chirp Signal .
`Spectrogram Display of the Time-Dependent Fourier
`Transform of Speech ............................................... 725
`Finite«Length Sequence ........................................... 779
`Exponential Sequence ............................................. 779
`Periodic Sequence ................................................. 787
`Kaiser Window Design of Hilbert Transformers .................. 793
`Noise Power Output of Ideal Lowpass Filter ...................... 820
`Noise Power Output of a Second-Order IIR Filter ............... 823
`
`

`

`PREFACE
`
`This text is a second generation descendent of our text, Digital Signal Processing, which
`was published in 1975. At that time, the technical field of digital signal processing was
`in its infancy, but certain basic principles had emerged and could be organized into
`a coherent presentation. Although courses existed at a few schools, they were almost
`exclusively at the graduate level. The original text was designed for such courses.
`By 1985, the pace of research and integrated circuit technology made it clear
`that digital signal processing would realize the potential that had been evident in the
`1970s The burgeoning importance of DSP clearly justified a revision and updating of the
`original text. However, in organizing that revision, it was clear that so many changes had
`occurred that it was most appropriate to develop a new textbook, strongly based on our
`original text, while keeping the original text in print. We titled the new book Discrete-
`Time Signal Processing to emphasize that most of the theory and design techniques
`discussed in the text apply to discrete-time systems in general.
`By the time Discrete-Time Signal Processing was published in 1989, the basic
`principles of DSP were commonly taught at the undergraduate level, sometimes even
`as part of a first course on linear systems, or at a somewhat more advanced level in
`third—year, fourth-year, or beginning graduate subjects. Therefore, it was appropriate to
`expand considerably the treatment of such topics as linear systems, sampling, multirate
`signal processing, applications, and spectral analysis. In addition, more examples were
`included to emphasize and illustrate important concepts. We also removed and con-
`densed some topics that time had shown were not fundamental to the understanding of
`discrete-time signal processing. Consistent with the importance that we placed on well
`constructed examples and homework problems, the new text contained more than 400
`problems.
`In the decade or so since Discrete-Time Signal Processing was published, some
`important new concepts have been developed, the capability of digital integrated cir-
`cuits has grown exponentially, and an increasing number of applications have emerged.
`However, the underlying basics and fundamentals remain largely the same albeit with
`a refinement of emphasis, understanding and pedagogy. Consequently when we looked
`at what was needed to keep Discrete- Time Signal Processing up-to-date as a textbook
`emphasizing the fundamentals of DSP, we found that the changes needed were far less
`drastic than before. In planning this current revision we were guided by the princi-
`ple that the main objective of a fundamental textbook is to uncover a subject rather
`than to cover it. Consequently, our goal in this current revision is to make the sub-
`ject of discrete-time signal processing even more accessible to students and practicing
`engineers, without compromising on coverage of what we consider to be the essential
`concepts that define the field. Toward this end we have considerably expanded our cov-
`erage of multi-rate signal processing due to its importance in oversampled A-to-D and
`D-to-A conversion and digital filter implementation. We have added a discussion of the
`cosine transform, which plays a central role in data compression standards. We have
`also removed some material that we judged to be of lesser importance in the present
`xix
`
`

`

`xx
`
`Preface
`
`context, or more appropriate for advanced textbooks and upper level graduate courses.
`Many of the concepts that were removed from the text (such as basic results on the
`cepstrum) have reappeared in some of the new homework problems.
`A major part of our emphasis in this revision has been directed toward the home—
`work problems and examples. We have significantly increased the number of examples
`which are important in illustrating and understanding the basic concepts, and we have
`increased the number of homework problems. Furthermore, the homework problems
`have been reorganized according to their level of difficulty and sophistication, and an—
`swers are provided to a selected set of problems. The instructor’s manual available from
`the publisher contains updated solutions for all of the problems in the book. These so-
`lutions were prepared by Li Lee and Maya Said of MIT and Jordan Rosenthal and
`Greg Slabaugh of Georgia Tech. This manual also contains some suggested exam prob-
`lems based on our courses at MIT, Georgia Tech and the University of Massachusetts
`Dartmouth.
`
`As in the earlier texts, it is assumed that the reader has a background of advanced
`calculus, along with a good understanding of the elements of complex numbers and vari-
`ables. In this edition, we have refrained from the use of complex contour integration
`in order to make the discussion accessible to a wider audience. An exposure to linear
`system theory for continuous-time signals, including Laplace and Fourier transforms,
`as taught in most undergraduate electrical and mechanical engineering curricula is still
`a basic prerequisite. With this background, the book is self—contained. In particular, no
`prior experience with discrete-time signals, z—transforms, discrete Fourier transforms,
`and the like is assumed. In later sections of some chapters, some topics such as quanti—
`zation noise are included that assume a basic background in stochastic signals. A brief
`review of the background for these sections is included in Chapter 2 and in Appendix A.
`It has become common in many signal processing courses to include exercises to be
`done on a computer, and many of the homework problems in this book are easily turned
`into problems to be solved with the aid of a computer. As in the first edition, we have
`purposely avoided providing special software to implement algorithms described in this
`book, for a variety of reasons. Foremost among them is that there are a variety of in-
`expensive signal processing software packages readily available for demonstrating and
`implementing signal processing on any of the popular personal computers and work-
`stations. These packages are well documented and have excellent technical su