Declaration of Rachel J. Watters on Authentication of Publication
`
`1, Rachel J. Watters, am a librarian, and the Head of Resource Sharing forthe
`
`General Library System, Memorial Library, located at 728 State Street, Madison,
`
`Wisconsin, 53706. Part of my job responsibilities include oversight of Wisconsin
`
`TechSearch (“WTS”), an interlibrary loan department at the University of Wisconsin-
`
`Madison.
`I have worked as a librarian at the University of Wisconsin library system
`since 1998, starting as a graduate student employeein the Kurt F. Wendt Engineering
`
`
`
`Library and WTS, then asalibrarian in Interlibrary Loan at Memorial Library. I began
`
`professional employment at WTS in 2002 and became WTSDirector in 2011. In 2019,
`I became of Head ofResource Sharing for UW-Madison’s General Library System.
`I
`
`have a master’s degree in Library and Information Studies from the University of
`Wisconsin-Madison. Through the course of my studies and employment, I have
`
`become well informed aboutthe operations of the University of Wisconsin library
`
`system, which followsstandard library practices.
`
`This Declaration relates to the dates of receipt and availability of the following:
`
`Oppenheim, A.V., Schafer, R.W., and Buck, J.R. (1999).
`Structures for Discrete-Time Systems. Discrete-Time Signal
`Processing. 2"' Ed. Upper Saddle River, NJ: Prentice Hall. pp.
`340-438.
`
`Standard operating procedures for materials at the University of Wisconsin-
`
`
`Madison Libraries. When a book wasreceived by the Library, it would be checkedin,
`
`Page 1 of 118
`
`Amazon v. Jawbone
`U.S. Patent 10,779,080
`Amazon Ex. 1032
`
`Page 1 of 118
`
`Amazon v. Jawbone
`U.S. Patent 10,779,080
`Amazon Ex. 1032
`
`

`

`Declaration of Rachel J. Watters on Authentication of Publication
`
`added to library holdings records, and made available to readersas soon afterits arrival
`as possible. he procedure normally took a few days or at most 2 to 3 weeks.
`
`Exhibit A to this Declaration is true and accurate copy of the front matter of the
`Discrete-Time Signal Processing (1999) publication, which includes stamps on the
`
`inside front cover and verso pages showingthat this bookis the property of the K.F.
`
`Wendt Library at the University of Wisconsin-Madison. Exhibit A also includes an
`
`excerpt of pages 340 to 438 of that book, showing the chapterentitled Structures for
`
`Discrete-Time Systems (1999).
`
`Attached as Exhibit B is the cataloging system record ofthe University of
`
`Wisconsin-Madison Libraries for its copy of the Discrete-Time Signal Processing
`
`(1999) publication. As shownin the “Receiving date” field of this Exhibit, the
`
`University of Wisconsin-Madison Libraries ownedthis bookand hadit cataloged in the
`
`system as of September 9, 2003.
`
`Membersofthe interested public could locate the Discrete-Time Signal
`
`Processing (1999) publication after it was cataloged by searching the public library
`
`catalog or requesting a search through WTS. The search could be done by title, author,
`
`and/or subject key words. Membersofthe interested publiccould access the
`
`publication by locating it on the library’s shelves or requestingit from WTS.
`
`I declare that all statements made herein of my own knowledgeare true and that
`
`all statements made on information andbelief are believed to be true; and further that
`
`Page 2 of 118
`
`Z
`
`Page 2 of 118
`
`

`

`Declaration of Rachel J. Watters on Authentication of Publication
`
`these statements were made with the knowledgethat willful false statements and the like
`
`so made are punishable by fine or imprisonment, or both, under Section 1001 of Title 18
`
`of the United States Code.
`
`Date: May 13, 2022
`el J. Watters
`Head of Resource Sharing
`
`Memorial Library
`728 State Street
`Madison, Wisconsin 53706
`
`Page 3 of 118
`
`Page 3 of 118
`
`

`

`69105b27b53
`
`B89109627653A
`
`DISCRETE-
`
`U2
`ivi
`
`PROCESSING
`
`Oa la
`
`STO al
`
`BUCK
`
`WENDT
`
`apy an)
`02452
`
`SAO]
`
`maT ON
`
`TK
`
`eke
`
`Page 4 of 118
`
`

`

`K.F. WENDT LIBRARY
`UW COLLEGE OF ENGR.
`215 N. RANDALL AVENUE
`MADISON, WI 53706
`
`Genoral Library System
`University of Wisconsin-Madis
`/28 State Street
`Madison, WI 53706-1494
`U.S.A,
`
`e
`
`Page 5 of 118
`
`Page 5 of 118
`
`

`

`DISCRETE-TIME
`SIGNAL
`PROCESSING
`
`Page 6 of 118
`
`Page 6 of 118
`
`

`

`
`
`PRENTICE HALL SIGNAL PROCESSING SERIES
`
`Alan V. Oppenheim, Series Editor
`
`ANDREWS AND Hunt_Digital Image Restoration
`BraceweELL
`Two Dimensional Imaging
`BricHAM The Fast Fourier Transform and Its Applications
`Buck, DANIEL, SINGER Computer Explorationsin Signals and Systems Using MATLAB
`Burpic Underwater Acoustic System Analysis, 2/E
`CastLemMan Digital Image Processing
`Conen Time-Frequency Analysis
`CROCHIERE AND RaBINER Multirate Digital Signal Processing
`DuDGEON AND MgErRSEREAU Multidimensional Digital Signal Processing
`Haykin Advances in Spectrum Analysis and Array Processing. Vol. I, II and III
`Haykin, ep. Array Signal Processing
`JOHNSON AND DupGEon Array Signal Processing
`Kay Fundamentals ofStatistical Signal Processing. Vol. I and II
`Kay Modern Spectral Estimation
`Kino Acoustic Waves: Devices, Imaging, and Analog Signal Processing
`Lim Two-Dimensional Signal and Image Processing
`Lim, ED.
`Speech Enhancement
`LIM AND OppENHEIM, EDS. Advanced Topics in Signal Processing
`Marpte Digital Spectral Analysis with Applications
`McCLELLAN AND RADER Number Theory in Digital Signal Processing
`Menvet
`Lessonsin Digital Estimation Theory for Signal Processing Communications and
`Control, 2/E
`NIKIAS AND Petroputu Higher Order Spectra Analysis
`OPPENHEIM AND Nawas_
`Symbolic and Knowledge-Based Signal Processing
`OPPENHEIM, WILLSKy, witH NAwaB__ Signals and Systems, 2/E
`OPPENHEIM AND SCHAFER Digital Signal Processing
`OPPENHEIM AND SCHAFER, WITH Buck Discrete-Time Signal Processing, 2/E
`Orranipis Signal Processing
`Poor AND WorNnELL. Wireless Communications: Signal Processing
`Puitiips AND Nace Digital Control Systems Analysis and Design, 3/E
`Picinsono Random Signals and Systems
`RABINER AND Go_p Theory and Applications of Digital Signal Processing
`RABINER AND SCHAFER Digital Processing of Speech Signals
`RABINER AND JuANG Fundamentals of Speech Recognition
`ROBINSON AND TREITEL Geophysical Signal Analysis
`STEARNS AND Davip__ Signal Processing Algorithms in Fortran and C
`STEARNS AND Dayip_ Signal Processing Algorithms in MATLAB
`TeKALp Digital Video Processing
`THERRIEN Discrete Random Signals andStatistical Signal Processing
`TripoLet Seismic Applications of Homomorphic Signal Processing
`VETTERLI AND Kovacevic Wavelets and Subband Coding
`VIADYANATHAN Multirate Systems and Filter Banks
`Wiprow AND STEARNS Adaptive Signal Processing
`
`Page 7 of 118
`
`Page 7 of 118
`
`

`

`SECOND EDITION
`
`DISCRETE-TIME
`SIGNAL
`PROCESSING
`
`ALAN V. OPPENHEIM
`
`MASSACHUSETTS INSTITUTE OF TECHNOLOGY
`
`RONALD W. SCHAFER
`
`GEORGIA INSTITUTE OF TECHNOLOGY
`
`WITH
`
`Joun R. Buck
`UNIVERSITY OF Ma
`:
`DARTMOUTH
`
`Page 8 of 118
`
`PRENTICE HALL
`Upper SADDLE River, NEw JERSEY 07458
`
`
`
`Page 8 of 118
`
`

`

`Oppenheim, Alan V.
`Discrete-time signal processing / Alan V. Oppenheim, Ronald W.
`Schafer, with John R. Buck. — 2nd ed.
`p-
`cm.
`Includes bibliographical references and index.
`ISBN 0-13-754920-2
`2. Discrete-time systems.
`1. Signal processing—Mathematics.
`I. Schafer, Ronald W.
`II. Buck, John R.
`III. Title.
`TKS5102.9.067
`1998
`621.382/2—de21
`
`98-50398
`CIP
`
`Acquisitions editor: Tom Robbins
`Productionservice: Interactive Composition Corporation
`Editorial/production supervision: Sharyn Vitrano
`Copyeditor: Brian Baker
`Coverdesign: Vivian Berman
`Art director: Amy Rosen
`Managingeditor: Eileen Clark
`Editor-in-Chief: Marcia 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.
`UpperSaddle River, New Jersey 07458
`
`All rights reserved. Nopart of this book may be
`reproduced,in any form or by any means,
`without permission in writing from the publisher.
`
`The authorand publisherof this book have used their best efforts in preparingthis book. These efforts include
`the development, research, and testing of the theories and programsto determinetheir 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 notbe liable in any event for
`incidental or consequential damagesin connection with,or arising outof, the furnishing, performance,or use
`of these programs.
`
`Printed in the United States of America
`10
`9
`8
`7
`6
`
`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
`
`Page9 OfibABrentice-Hall do Brasil, Ltda., Rio deJaneiro
`
`(
`
`Page 9 of 118
`
`

`

`To Phyllis, Justine and Jason
`
`To Dorothy, Bill, Tricia, Ken and Kate
`and in memoryofJohn
`
`To Susan
`
`Page 10 of 118
`
`5S
`
`Page 10 of 118
`
`

`

`
`
`CONTENTS
`
`List oF EXAMPLES
`
`XV
`
`PREFACE
`
`XIX
`
`ACKNOWLEDGMENTS
`
`XXV
`
`INTRODUCTION 1
`
`11
`
`18
`
`20
`
`2.3
`2.4
`2.5
`2.6
`
`DISCRETE-TIME SIGNALS AND SYSTEMS 8
`2.0
`Introduction 8
`9
`2.1 Discrete-Time Signals: Sequences
`2.1.1 Basic Sequences and Sequence Operations
`2.2 Discrete-Time Systems
`16
`2.2.1 Memoryless Systems
`2.2.2 Linear Systems
`18
`2.2.3 Time-Invariant Systems
`2.2.4 Causality
`21
`2.2.5 Stability
`21
`22
`Linear Time-Invariant Systems
`28
`Properties of Linear Time-Invariant Systems
`34
`Linear Constant-Coefficient Difference Equations
`Frequency-Domain Representation of Discrete-Time Signals and
`Systems
`40
`2.6.1 Eigenfunctions for Linear Time-Invariant Systems
`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
`2.9.3. Time Reversal
`60
`2.9.4 Differentiation in Frequency
`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
`
`40
`
`59
`
`60
`
`3
`
`THE Z-TRANSFORM 94
`
`3.0
`Introduction 94
`3.1
`z-Transform 94
`Vii
`Page 11 of 118
`
`
`Page 11 of 118
`
`

`

`Contents’
`
`viii
`
`3.2
`3.3
`
`3.4
`
`3.5
`
`Properties of the Region of Convergence for the z-Transform 105
`The Inverse z-Transform 111
`3.3.1.
`Inspection Method
`111
`112
`3.3.2 Partial Fraction Expansion
`3.3.3. Power Series Expansion
`116
`z-Transform Properties
`119
`3.4.1 Linearity
`119
`120
`3.4.2. Time Shifting
`3.4.3. Multiplication by an Exponential Sequence
`3.4.4 Differentiation of X(z)
`122
`3.4.5 Conjugation of a Complex Sequence
`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
`Summary
`126
`Problems
`127
`
`121
`
`123
`
`126
`
`4 SAMPLING OF CONTINUOUS-TIME SIGNALS 140
`
`167
`
`172
`176
`
`179
`
`182
`183 -
`
`4.0
`4.1
`4.2
`4.3
`4.4
`
`4.5
`4.6
`
`4.7
`
`4.8
`
`4.9
`
`Introduction 140
`140
`Periodic Sampling
`Frequency-Domain Representation of Sampling 142
`150
`Reconstruction of a Bandlimited Signal from Its Samples
`Discrete-Time Processing of Continuous-Time Signals
`153
`4.4.1 Linear Time-Invariant Discrete-Time Systems
`154
`4.4.2
`Impulse Invariance
`160
`163
`Continuous-Time Processing of Discrete-Time Signals
`Changing the Sampling Rate Using Discrete-Time Processing
`4.6.1
`Sampling Rate Reduction by an Integer Factor
`167
`4.6.2
`Increasing the Sampling Rate by an Integer Factor
`4.6.3 Changing the Sampling Rate by a Noninteger Factor
`Multirate Signal Processing 179
`4.7.1
`Interchange of Filtering and Downsampling/Upsampling
`4.7.2 Polyphase Decompositions
`180
`4.7.3 Polyphase Implementation of Decimation Filters
`4.7.4 Polyphase Impleméntation of Interpolation Filters
`_ Digital Processing of Analog Signals
`185
`4.8.1
` Prefiltering to Avoid Aliasing
`185
`4.8.2 Analog-to-Digital (A/D) Conversion
`4.8.3 Analysis of Quantization Errors
`193
`4.8.4 D/A Conversion
`197
`Oversampling and Noise Shaping in A/D and D/A Conversion
`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
`Page 12 of 118
`
`187
`
`201
`
`Page 12 of 118
`
`

`

`Contents
`
`4.10 Summary 213
`Problems
`214
`
`ix
`
`5 TRANSFORM ANALYSIS OF LINEAR TIME-INVARIANT
`SYSTEMS 240
`5.0
`5.1
`
`241
`241
`
`Introduction 240
`The Frequency Response of LTI Systems
`5.1.1
`Ideal Frequency-Selective Filters
`5.1.2 Phase Distortion and Delay 242
`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
`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
`Relationship between Magnitude and Phase
`270
`All-Pass Systems
`274
`280
`Minimum-Phase Systems
`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
`Linear Systems with Generalized Linear Phase
`291
`5.7.1
`Systems with Linear Phase
`292
`5.7.2 Generalized Linear Phase
`295
`297
`5.7.3 Causal Generalized Linear-Phase Systems
`5.7.4 Relation of FIR Linear-Phase Systems to Minimum-Phase
`Systems
`308
`Summary 311 |
`Problems
`312
`
`250
`
`5.2
`
`5.3
`
`5.4
`5.5
`5.6
`
`5.7
`
`5.8
`
`6 STRUCTURES FOR DISCRETE-TIME SYSTEMS 340
`
`6.0
`6.1
`
`6.2
`
`6.3
`
`6.4
`6.5
`Page 13
`
`Introduction 340
`Block Diagram Representation of Linear Constant-Coefficient
`Difference Equations
`341
`Signal Flow Graph Representation of Linear Constant-Coefficient
`Difference Equations
`348
`Basic Structures for IIR Systems
`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
`Transposed Forms
`363
`Basic Network Structures for FIR Systems
`of 118
`
`354
`
`361
`
`366
`
`aaartreerenceencesaenccecen
`
`Page 13 of 118
`
`

`

`xX
`
`Contents
`
`368
`370
`
`374
`
`379
`
`384
`386
`
`399
`
`6.5.1 Direct Form 367
`6.5.2 Cascade Form 367
`6.5.3. Structures for Linear-Phase FIR Systems
`6.6 Overview of Finite-Precision Numerical Effects
`6.6.1 Number Representations
`371
`6.6.2 Quantization in Implementing Systems
`The Effects of Coefficient Quantization 377
`377
`6.7.1 Effects of Coefficient Quantization in IIR Systems
`6.7.2 Example of Coefficient Quantization in an Elliptic Filter
`6.7.3.
`Poles of Quantized Second-OrderSections
`382
`6.7.4 Effects of Coefficient Quantization in FIR Systems
`6.7.5 Example of Quantization of an Optimum FIR Filter
`6.7.6 Maintaining Linear Phase . 390
`391
`Effects of Round-off Noise in Digital Filters
`391
`6.8.1 Analysis of the Direct-Form IIR Structures
`6.8.2 Scaling in Fixed-Point Implementations of IIR Systems
`6.8.3. Example of Analysis of a Cascade IIR Structure
`403
`6.8.4 Analysis of Direct-Form FIR Systems
`410
`412
`6.8.5 Floating-Point Realizations of Discrete-Time Systems
`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
`
`6.7
`
`6.8
`
`6.9
`
`7 /FILTER DESIGN TECHNIQUES 439
`
`:
`
`a
`
`443
`
`454
`
`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
`7.1.2. Bilinear Transformation 450
`7.1.3 Examples of Bilinear Transformation Design
`7.2 Design of FIR Filters by Windowing
`465
`467
`7.2.1 Properties of Commonly Used Windows
`7.2.2
`Incorporation of Generalized Linear Phase
`469
`7.2.3. The Kaiser Window Filter Design Method 474
`478
`7.2.4 Relationship of the Kaiser Window to Other Windows
`Examples of FIR Filter Design by the Kaiser Window Method 478
`7.3.1 Highpass Filter
`479
`482
`7.3.2 Discrete-Time Differentiators
`486
`7.4 Optimum Approximations of FIR Filters
`491
`7.4.1 Optimal Type I Lowpass Filters
`497
`7.4.2. Optimal Type Il Lowpass Filters
`-7.4.3 The Parks—McClellan Algorithm 498
`Page 14 of 118
`
`7.3
`
`Page 14 of 118
`
`

`

`Contents
`
`xi
`
`7.5
`
`7.6
`Tol
`
`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
`Summary 511
`Problems
`511
`
`510
`
`8 THE DiscRETE FOURIER TRANSFORM 541
`
`546
`
`546
`
`551
`
`8.0
`8.1
`
`8.2
`
`8.3
`
`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 ShiftofaSequence
`8.2.3. Duality 547
`547
`8.2.4 Symmetry Properties
`548
`8.2.5 Periodic Convolution
`8.2.6 Summary of Properties of the DFS Representation of Periodic
`Sequences
`550
`The Fourier Transform of Periodic Signals
`Sampling the Fourier Transform 555
`Fourier Representation of Finite-Duration Sequences: The Discrete
`Fourier Transform 559
`Properties of the Discrete Fourier Transform 564
`8.6.1 Linearity
`564
`8.6.2 Circular Shift of aSequence
`8.6.3 Duality 567
`568
`8.6.4 Symmetry Properties
`8.6.5 Circular Convolution 571
`8.6.6 Summary of Properties of the Discrete Fourier Transform 575
`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
`8.7.3
`Implementing Linear Time-Invariant Systems Using the
`DFT 582
`The Discrete Cosine Transform (DCT)
`8.8.1 Definitions of the DCT 589
`590
`° 8.8.2 Definition of the DCT-1 and DCT-2
`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
`Page 15 of 118
`
`564
`
`589
`
`577
`
`Page 15 of 118
`
`

`

`xii
`
`Contents
`
`9 COMPUTATION OF THE DISCRETE FOURIER
`TRANSFORM 629
`
`9.0
`9.1
`9.2
`9.3
`
`9.4
`
`9.5
`
`9.6
`
`9.7
`9.8
`
`635
`
`646
`
`Introduction 629
`Efficient Computation of the Discrete Fourier Transform 630
`The Goertzel Algorithm 633
`Decimation-in-Time FFT Algorithms
`9.3.1
`In-Place Computations
`640
`9.3.2 Alternative Forms
`643
`Decimation-in-Frequency FFT Algorithms
`9.4.1
`In-Place Computation 650
`9.4.2 Alternative Forms
`650
`Practical Considerations
`652
`9.5.1
`Indexing
`652
`9.5.2 Coefficients
`654
`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
`
`1 0 FOURIER ANALYSIS OF SIGNALS USING THE
`DISCRETE FOURIER TRANSFORM 693
`
`10.0
`10.1
`10.2
`
`10.3
`
`10.4
`
`10.5
`
`10.6
`
`Introduction 693
`Fourier Analysis of Signals Using the DFT 694
`DFTAnalysis of Sinusoidal Signals
`697
`10.2.1 The Effect of Windowing
`698
`10.2.2 The Effect of Spectral Sampling 703
`The Time-Dependent Fourier Transform 714
`10.3.1 The Effect of the Window 717
`10.3.2. Sampling in Time and Frequency 718
`Block Convolution Using the Time-DependentFourier
`Transform 722
`723
`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
`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
`
`Page 16 of 118
`
`Page 16 of 118
`
`

`

`Contents
`
`xiii
`
`10.7 Spectrum Analysis of RandomSignals 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
`
`DISCRETE HILBERT TRANSFORMS 775
`
`11
`
`Introduction 775
`11.0
`11.1 Real- and Imaginary-Part Sufficiency of the Fourier Transform for
`Causal Sequences
`777
`11.2 Sufficiency Theoremsfor Finite-Length Sequences
`11.3 Relationships Between Magnitude and Phase
`788
`11.4 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
`11.5 Summary
`801
`Problems
`802
`
`782
`
`789
`
`796
`
`APPENDIX A.
`
`RANDOM SIGNALS
`
`811
`
`811
`
`A.1_ Discrete-Time Random Processes
`A.2 Averages
`813
`813
`A.2.1 Definitions
`815
`A.2.2. Time Averages
`Properties of Correlation and Covariance Sequences
`A.3
`Fourier Transform Representation of Random Signals
`A.4
`A.5 Use of the z-Transform in Average Power Computations
`APPENDIX B ContTINUOUS-TIME FILTERS
`
`817
`818
`820
`824.
`
`824
`
`B.1 Butterworth LowpassFilters
`B.2 Chebyshev Filters
`826
`B.3
`Elliptic Filters
`828
`APPENDIX G
`ANSWERS TO SELECTED BASIC
`PROBLEMS
`830
`
`BIBLIOGRAPHY 851
`
`INDEX 859
`
`Page 17 of 118
`
`Page 17 of 118
`
`

`

`STRUCTURES FOR
`DISCRETE-TIME SYSTEMS
`
`
`
`6.0 INTRODUCTION
`
`As we saw in Chapter5, a linear time-invariantsystem with a rational system function has
`the property that the input and output sequencessatisfy a linear constant-coefficient dif-
`ference equation. Since the system functionis the z-transform of the impulse response,
`and since the difference equation satisfied by the input and output can be determined
`by inspection of the system function,it follows that the difference equation, the impulse
`response, and the system function are equivalent characterizationsof the input-output
`relation of a linear time-invariant discrete-time system. When such systems are imple-
`mentedwith discrete-time analogor digital hardware,the difference equationorthe sys-
`tem function representation mustbe converted to an algorithm orstructure that can be
`realized in the desired technology. Aswewill see in this chapter, systemsdescribedbylin-
`ear constant-coefficient difference equations can be representedby structuresconsisting
`of an interconnection of the basic operations of addition, multiplication by a constant,
`and delay, the exact implementation of which is dictated by the technologyto be used.
`Asanillustration of the computation associated with a difference equation, con-
`sider the system described by the system function
`
`bo t+ biz
`H(z) = Tear’
`
`|z| > Jal.
`
`The impulse responseofthis system is
`
`Page 18 of 118
`
`340
`
`h{n] = boa"uln] + bia"ufn — 1],
`
`(6.1)
`
`(6.2)
`
`Page 18 of 118
`
`

`

`Sec. 6.1
`
`Block Diagram Representation of Linear Constant-Coefficient Difference Equations
`
`341
`
`andthefirst-order difference equation thatis satisfied by the input and output sequences
`is
`
`y[n] — ay[n — 1] = box[n] + bix[n — 1].
`
`(6.3)
`
`Since the system has an infinite-duration impulse response, it is not possible to
`implementthe system by discrete convolution. However, rewriting Eq. (6.3) in the form
`
`y[n] = ay[n — 1] + box[n] + b1x[n — 1]
`
`(6.4)
`
`providesthe basis for an algorithm for recursive computation of the output at any time
`nin termsof the previous output y[n — 1], the current input sample x[n], andthe previ-
`ous input sample x[n — 1]. As discussed in Section 2.5,if we further assumeinitial-rest
`conditions(i.e., if x[n] = Oforn < 0, then y[n] = Oforn < 0), andif we use Eq. (6.4) asa
`recurrence formula for computing the output from past values of the output and present
`and past values of the input, the system will be linear and time invariant. A similar pro-
`cedure can be applied to the more general case of an Nth-order difference equation.
`However,the algorithm suggested by Eq. (6.4) andits generalization for higher order
`difference equationsis not the only computational algorithm for implementinga partic-
`ular system, and oftenit is not the most preferable. As we will see, an unlimited variety
`of computationalstructuresresult in the same relation between the input sequence x[n]
`and the output sequence y[m].
`In the remainderof this chapter, we consider the importantissues in the imple-
`mentation of linear time-invariant discrete-time systems. We first present the block
`. diagram andsignal flow graph descriptions of computational structures or networks
`for linear constant-coefficient difference equations representing linear time-invariant
`causal systems. Using a combination of algebraic manipulations and manipulations of
`block diagram representations, we derive a numberof basic equivalent structures for
`implementing a causal linear time-invariant system. Although two structures may be
`equivalentwith regardto their input-output characteristics for infinite-precision repre-
`sentations of coefficients and variables, they may have vastly different behavior when
`the numerical precisionis limited. This is the major reasonthatit is of interest to study
`different implementation structures. The effects of finite-precision representation of
`the system coefficients and the effects of truncation or rounding of intermediate com-
`putations are consideredin the latter sections of the chapter.
`
`6.1 BLOCK DIAGRAM REPRESENTATION OF LINEAR
`
`CONSTANT-COEFFICIENT DIFFERENCE EQUATIONS
`
`The implementationofa linear time-invariant discrete-time system byiteratively eval-
`uating a recurrence formula obtained from a difference equation requires that delayed
`values of the output, input, and intermediate sequences be available. The delay of se-
`quence values implies the need for storage of past sequence values. Also, we must
`provide means for multiplication of the delayed sequence values by the coefficients,
`Pagé18)othiRiplementationofalineartime-invariantdiscrete-timesystemare adders,
`a
`la
`s for adding the resulting products. Therefore, the basic elements re-
`
`Page 19 of 118
`
`

`

`342
`
`Structures for Discrete-Time Systems
`
`Chap. 6
`
` x1[n]
`
`X;[n] + x,[n]
`
`:
`
`(a)
`a
`
`x{n]
`
`x(n]
`
`ax[n]
`
`x[n—1]
`
`(b)
`
`4
`
`z
`(c)
`
`Figure 6.1 Block diagram symbois.
`(a) Addition of two sequences.
`(b) Multiplication of a sequence by a
`constant. (c) Unit delay.
`
`multipliers, and memory for storing delayed sequence values. The interconnection of
`these basic elementsis conveniently depicted by block diagrams composed ofthe ba-
`sic pictorial symbols shown in Figure 6.1. Figure 6.1(a) represents the addition of two
`sequences. In general block diagram notation, an adder may have any numberofin-
`puts. However, in almost all practical implementations, adders have only two inputs.
`In all the diagrams of this chapter, we indicate this explicitly by limiting the num-
`ber of inputs as in Figure 6.1(a). Figure 6.1(b) depicts multiplication of a sequence
`by a constant, and Figure 6.1(c) depicts delaying a sequence by one sample.In digi-
`tal implementations, the delay operation can be implemented by providing a storage
`register for each unit delay that is required. In analog discrete-time implementations,
`such as switched-capacitorfilters, the delays are implemented by charge storage de-
`vices. The unit delay system is represented in Figure 6.1(c) by its system function, z~!.
`Delays of more than one sample can be denoted asin Figure 6.1(c), with a system
`function of z~™, where M is the numberof samples of delay; however, the actual im-
`plementation of M samples of delay would generally be done by cascading M unit
`delays. In an integrated-circuit implementation, these unit delays might formashift
`register that is clocked at the sampling rate of the input signal. In a software imple-
`mentation, M cascaded unit delays would be implemented as M consecutive memory
`registers.
`
`Example 6.1 Block Diagram Representation
`of a Difference Equation
`
`*
`
`*
`
`Page 2OLof
`
`+ Asan exampleofthe representation of a difference equation in terms of the elements
`_
`in Figure 6.1, consider the second-orderdifference equation
`
`y[n] = aiy[n — 1] + aay[n — 2} + box[n).
`* The corresponding system functionis
`(6.6)
`bo
`HQ) =;
`Theblock diagram representationof the system realization based on Eq.(6.5) is
`sh48b in Figure 6.2. Such diagramsgive a pictorial representation ofa computational
`
`= a4271 — agz-2"
`
`(6.5)
`
`Page 20 of 118
`
`

`

`Sec. 6.1
`
`Block Diagram Representation of Linear Constant-Coefficient Difference Equations
`
`343
`
`or
`
`bo yln~2]
`
`Figure 6.2 Example of a block diagram representation of a difference equation.
`
`eoRaaeablaete
`
`algorithm for implementing the system. When the system is implemented on either a
`general-purpose computerora digital signal processing (DSP) chip, network structures
`such as the one shownin Figure 6.2 serve as the basis for a program that implements
`the system.If the system is implemented with discrete components or as a complete
`system with VLSI technology, the block diagram is the basis for determining a hardware
`architecture for the system. In both cases, diagrams such as Figure 6.2 show explicitly
`that we must provide storage for the delayed variables (in this case, y[n — 1] and
`,
`: yn — 2]) and also the coefficients of the difference equation (in this case, a, a2,
`* and bo). Furthermore, we see from Figure 6.2 that an output sequence value y[7]
`is computed byfirst forming the products a,y[n — 1] and azy[n — 2], then adding
`them,and,finally, adding the result to box[n]. Thus, Figure 6.2 conveniently depicts
`the complexity of the associated computational algorithm,the steps of the algorithm,
`and the amountof hardware required to realize the system.
`
`Ste
`
`ereCoemeeeMeeroe
`
`.
`
`Example 6.1can be generalized to higher order difference equationsof the form!
`
`N
`M
`
`k=1
`k=0
`
`y[n] -S> axyl[n —k)= > byx[n — k], (6.7) .
`
`with the corresponding system function
`
`M
`
`byz*
`H(z) = ——_.
`1- > agz*
`k=l
`
`(6.8)
`
`1The form used in previous chapters for a general Nth-orderdifference equation was
`N
`ayin —kj= > byx{n — kj.
`k=0
`k=0
`
`M>S
`
`In the remainderof the book,it will be more convenient to use the form in Eq. (6.7), where the coefficient
`
`Pagé‘2't!6
`Sign after they
`
`ized to unity and the coefficients associated with the delayed output appearwith a positive
`bave been movedto the right-handside of the equation. (See Eq.(6.9).)
`
`Page 21 of 118
`
`

`

`344
`
`Structures for Discrete-Time Systems
`
`Chap. 6
`
`difference equation.
`
`Figure 6.3 Block diagram
`representation for a general Nth-order
`
`yin-N]
`
`Rewriting Eq. (6.7) as a recurrence formula for y[7] in termsof a linear combination of
`past values of the output sequence andcurrent andpastvalues of the input sequence
`leads to the relation
`
`N
`M
`yn] = So agy[n — kK] + S~ byx[n — X1.
`k=1
`k=0
`
`(6.9)
`
`v[n] =S> byx[n — K1, (6.10a)
`
`The block diagram of Figure 6.3 is an explicit pictorial representation of Eq.(6.9).
`Moreprecisely, it represents the pair of difference equations
`M
`
`k=0
`N
`yn] = S> agy[n — k] + v[n.
`k=1
`
`(6.10b)
`
`The assumptionof a two-input adderimplies that the additions are donein a specified
`order. That is, Figure 6.3 shows that the products ayy[n — N] and ay_iy[n — N+ 1]
`must be computed, then added,and the resulting sum addedto ay_2y[n — N +2], and
`so on. After y[n] has been computed,the delay variables must be updated by moving
`y|n — N + 1] into the register holding y[n — NJ], and so on.
`A block diagram canbe rearranged or modified in a variety of ways without chang-
`ing the overall system function. Each appropriate rearrangementrepresentsa different
`
`computational algorithm for implementing the same system.Forexample,theblock
`diagram of Figure 6.3 can be viewedas a cascadeof two systems,thefirst representing
`
`
`
`from v[n]. Since each of the two systems is a lineartime-invariantSystem(assuming
`initial-rest conditions for the delay registers), the order in which the two systems are
`cascaded can be reversed, as shownin Figure 6.4, withoutaffecting the overall system
`Page 22 of 118
`
`Page 22 of 118
`
`

`

`Sec. 6.1
`
`Block Diagram Representation of Linear Constant-Coefficient Difference Equations
`
`345
`
`w[n]
`
`by Figure 6.4 Rearrangement of block
`
`diagram of Figure 6.3. We assumefor
`convenience that V = M. If N 4 M,
`someof the coefficients will be zero.
`
`function. In Figure 6.4, for convenience, we have assumed that M = N.Clearly, there
`is no loss of generality, since if M # N, someofthe coefficients a, or bg in the figure
`would be zero, and the diagram could be simplified accordingly.
`In termsof the system function H(z) in Eq. (6.8), Figure 6.3 can be viewed as an
`implementation of H(z) through the decomposition
`~
`
`1- S> az*|\*°
`k=1
`
`H(z) = H2(2)H(z) = — (>.nc)
`
`M
`
`(6.11)
`
`or, equivalently, through the pair of equations
`M
`
`V(z) = A(z)X(z) = (>.ne) X(2),
`
`k=0
`
`«
`
`(6.12a)
`
`Y(2) = Ab(z)V(z) =
`
`1
`N
`1- Ss; a,z*
`k=1
`
`V(2).
`
`(6.12b)
`
`Page 23 of 118
`
`Page 23 of 118
`
`

`

`346
`
`Structures for Discrete-Time Systems
`
`Chap. 6
`
`Figure 6.4, on the other hand, represents H(z) as
`
`H(z) = Hi(z)H2(z) = (>:he) — (6.13)
`
`1— > ayz*
`k=1
`
`M
`
`ko
`
`or, equivalently, through the equations
`
`W(z) = Aa(z)X(z) =
`
`1
`W
`1- S az*
`k=l
`
`X(z),
`
`(6.14a)
`
`Y(z) = Ai(z)W(z) = (>:be) W(z).
`
`k=0
`
`M