THIRD EDITION Discrete-Time Signal Processing Alan V. Oppenheim Massachusetts Institute of Technology Ronald W. Schafer Hewlett-Packard Laboratories Upper Saddle River · Boston · Columbus · San Francisco · New York Indianapolis · London · Toronto · Sydney · Singapore · Tokyo · Montreal Dubai·Madrid·HongKong·MexicoCity·Munich·Paris·Amsterdam·CapeTown VicePresidentandEditorialDirector,ECS:MarciaJ.Horton AcquisitionEditor:AndrewGilfillan EditorialAssistant:WilliamOpaluch DirectorofTeam-BasedProjectManagement:VinceO’Brien SeniorMarketingManager:TimGalligan MarketingAssistant:MackPatterson SeniorManagingEditor:ScottDisanno ProductionProjectManager:ClareRomeo SeniorOperationsSpecialist:AlanFischer OperationsSpecialist:LisaMcDowell ArtDirector:KristineCarney CoverDesigner:KristineCarney CoverPhoto:LibradoRomero/NewYorkTimes—MapsandGraphics Manager,CoverPhotoPermissions:KarenSanatar Composition:PreTeXInc.:PaulMailhot Printer/Binder:CourierWestford Typeface:10/12TimesTen Creditsandacknowledgmentsborrowedfromothersourcesandreproduced,withpermission,inthistextbookappearonthe appropriatepagewithinthetext. LabVIEWisaregisteredtrademarkofNationalInstruments,11500NMopacExpwy,Austin,TX78759-3504. MathematicaisaregisteredtrademarkofWolframResearch,Inc.,100TradeCenterDrive,Champaign,IL61820-7237. MATLABandSimulinkareregisteredtrademarksofTheMathWorks,3AppleHillDrive,Natick,MA01760-2098. ©2010,1999,1989byPearsonHigherEducation,Inc.,UpperSaddleRiver,NJ07458.Allrightsreserved.Manufacturedinthe UnitedStatesofAmerica.ThispublicationisprotectedbyCopyrightandpermissionsshouldbeobtainedfromthepublisherprior toanyprohibitedreproduction,storageinaretrievalsystem,ortransmissioninanyformorbyanymeans,electronic,mechanical, photocopying,recording,orlikewise.Toobtainpermission(s)tousematerialsfromthiswork,pleasesubmitawrittenrequestto PearsonHigherEducation,PermissionsDepartment,OneLakeStreet,UpperSaddleRiver,NJ07458. Manyofthedesignationsbymanufacturersandsellertodistinguishtheirproductsareclaimedastrademarks.Wherethose designationsappearinthisbook,andthepublisherwasawareofatrademarkclaim,thedesignationshavebeenprintedininitial capsorallcaps. Theauthorandpublisherofthisbookhaveusedtheirbesteffortsinpreparingthisbook.Theseeffortsincludethedevelopment, research,andtestingoftheoriesandprogramstodeterminetheireffectiveness.Theauthorandpublishermakenowarrantyofany kind,expressedorimplied,withregardtotheseprogramsorthedocumentationcontainedinthisbook.Theauthorandpublisher shallnotbeliableinanyeventforincidentalorconsequentialdamageswith,orarisingoutof,thefurnishing,performance,oruseof theseprograms. PearsonEducationLtd.,London PearsonEducationSingapore,Pte.Ltd. PearsonEducationCanada,Inc.,Toronto PearsonEducation–Japan,Tokyo PearsonEducationAustraliaPty.Ltd.,Sydney PearsonEducationNorthAsiaLtd.,HongKong PearsonEducationdeMexico,S.A.deC.V. PearsonEducationMalaysia,Pte.Ltd. PearsonEducation,Inc.,UpperSaddleRiver,NewJersey 10 9 8 7 6 5 4 3 2 1 ISBN-13: 978-0-13-198842-2 ISBN-10: 0-13-198842-5 ToPhyllis,Justine,andJason ToDorothy,Bill,Tricia,Ken,andKate andinmemoryofJohn This page intentionally left blank Contents Preface xv TheCompanionWebsite xxii TheCover xxv Acknowledgments xxvi 1 Introduction 1 2 Discrete-TimeSignalsandSystems 9 2.0 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.1 Discrete-TimeSignals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2 Discrete-TimeSystems . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2.1 MemorylessSystems . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2.2 LinearSystems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.2.3 Time-InvariantSystems . . . . . . . . . . . . . . . . . . . . . . . 20 2.2.4 Causality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.2.5 Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.3 LTISystems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.4 PropertiesofLinearTime-InvariantSystems . . . . . . . . . . . . . . . 30 2.5 LinearConstant-CoefficientDifferenceEquations . . . . . . . . . . . . 35 2.6 Frequency-DomainRepresentationofDiscrete-TimeSignalsandSystems 40 2.6.1 EigenfunctionsforLinearTime-InvariantSystems . . . . . . . 40 2.6.2 SuddenlyAppliedComplexExponentialInputs . . . . . . . . . 46 2.7 RepresentationofSequencesbyFourierTransforms . . . . . . . . . . . 48 2.8 SymmetryPropertiesoftheFourierTransform . . . . . . . . . . . . . . 54 2.9 FourierTransformTheorems . . . . . . . . . . . . . . . . . . . . . . . . 58 2.9.1 LinearityoftheFourierTransform . . . . . . . . . . . . . . . . 59 2.9.2 TimeShiftingandFrequencyShiftingTheorem . . . . . . . . . 59 2.9.3 TimeReversalTheorem . . . . . . . . . . . . . . . . . . . . . . 59 v vi Contents 2.9.4 DifferentiationinFrequencyTheorem . . . . . . . . . . . . . . 59 2.9.5 Parseval’sTheorem . . . . . . . . . . . . . . . . . . . . . . . . . 60 2.9.6 TheConvolutionTheorem . . . . . . . . . . . . . . . . . . . . . 60 2.9.7 TheModulationorWindowingTheorem . . . . . . . . . . . . . 61 2.10 Discrete-TimeRandomSignals . . . . . . . . . . . . . . . . . . . . . . . 64 2.11 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 3 Thez-Transform 99 3.0 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 3.1 z-Transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 3.2 PropertiesoftheROCforthez-Transform . . . . . . . . . . . . . . . . 110 3.3 TheInversez-Transform. . . . . . . . . . . . . . . . . . . . . . . . . . . 115 3.3.1 InspectionMethod . . . . . . . . . . . . . . . . . . . . . . . . . 116 3.3.2 PartialFractionExpansion . . . . . . . . . . . . . . . . . . . . . 116 3.3.3 PowerSeriesExpansion. . . . . . . . . . . . . . . . . . . . . . . 122 3.4 z-TransformProperties . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 3.4.1 Linearity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 3.4.2 TimeShifting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 3.4.3 MultiplicationbyanExponentialSequence . . . . . . . . . . . 126 3.4.4 DifferentiationofX(z) . . . . . . . . . . . . . . . . . . . . . . . 127 3.4.5 ConjugationofaComplexSequence . . . . . . . . . . . . . . . 129 3.4.6 TimeReversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 3.4.7 ConvolutionofSequences . . . . . . . . . . . . . . . . . . . . . 130 3.4.8 SummaryofSomez-TransformProperties . . . . . . . . . . . . 131 3.5 z-TransformsandLTISystems . . . . . . . . . . . . . . . . . . . . . . . 131 3.6 TheUnilateralz-Transform . . . . . . . . . . . . . . . . . . . . . . . . . 135 3.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 4 SamplingofContinuous-TimeSignals 153 4.0 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 4.1 PeriodicSampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 4.2 Frequency-DomainRepresentationofSampling . . . . . . . . . . . . . 156 4.3 ReconstructionofaBandlimitedSignalfromItsSamples . . . . . . . . 163 4.4 Discrete-TimeProcessingofContinuous-TimeSignals. . . . . . . . . . 167 4.4.1 Discrete-TimeLTIProcessingofContinuous-TimeSignals . . . 168 4.4.2 ImpulseInvariance . . . . . . . . . . . . . . . . . . . . . . . . . 173 4.5 Continuous-TimeProcessingofDiscrete-TimeSignals. . . . . . . . . . 175 4.6 ChangingtheSamplingRateUsingDiscrete-TimeProcessing . . . . . 179 4.6.1 SamplingRateReductionbyanIntegerFactor . . . . . . . . . 180 4.6.2 IncreasingtheSamplingRatebyanIntegerFactor . . . . . . . 184 4.6.3 SimpleandPracticalInterpolationFilters . . . . . . . . . . . . . 187 4.6.4 ChangingtheSamplingRatebyaNonintegerFactor . . . . . . 190 4.7 MultirateSignalProcessing . . . . . . . . . . . . . . . . . . . . . . . . . 194 4.7.1 InterchangeofFilteringwithCompressor/Expander . . . . . . 194 4.7.2 MultistageDecimationandInterpolation . . . . . . . . . . . . . 195 Contents vii 4.7.3 PolyphaseDecompositions . . . . . . . . . . . . . . . . . . . . . 197 4.7.4 PolyphaseImplementationofDecimationFilters . . . . . . . . 199 4.7.5 PolyphaseImplementationofInterpolationFilters . . . . . . . 200 4.7.6 MultirateFilterBanks . . . . . . . . . . . . . . . . . . . . . . . . 201 4.8 DigitalProcessingofAnalogSignals . . . . . . . . . . . . . . . . . . . . 205 4.8.1 PrefilteringtoAvoidAliasing . . . . . . . . . . . . . . . . . . . 206 4.8.2 A/DConversion . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 4.8.3 AnalysisofQuantizationErrors . . . . . . . . . . . . . . . . . . 214 4.8.4 D/AConversion . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 4.9 OversamplingandNoiseShapinginA/DandD/AConversion . . . . . 224 4.9.1 OversampledA/DConversionwithDirectQuantization . . . . 225 4.9.2 OversampledA/DConversionwithNoiseShaping . . . . . . . 229 4.9.3 OversamplingandNoiseShapinginD/AConversion . . . . . . 234 4.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 5 TransformAnalysisofLinearTime-InvariantSystems 274 5.0 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274 5.1 TheFrequencyResponseofLTISystems . . . . . . . . . . . . . . . . . 275 5.1.1 FrequencyResponsePhaseandGroupDelay . . . . . . . . . . 275 5.1.2 IllustrationofEffectsofGroupDelayandAttenuation . . . . . 278 5.2 SystemFunctions—LinearConstant-CoefficientDifferenceEquations 283 5.2.1 StabilityandCausality . . . . . . . . . . . . . . . . . . . . . . . 285 5.2.2 InverseSystems . . . . . . . . . . . . . . . . . . . . . . . . . . . 286 5.2.3 ImpulseResponseforRationalSystemFunctions . . . . . . . . 288 5.3 FrequencyResponseforRationalSystemFunctions . . . . . . . . . . . 290 5.3.1 FrequencyResponseof1st-OrderSystems . . . . . . . . . . . . 292 5.3.2 ExampleswithMultiplePolesandZeros . . . . . . . . . . . . . 296 5.4 RelationshipbetweenMagnitudeandPhase . . . . . . . . . . . . . . . 301 5.5 All-PassSystems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305 5.6 Minimum-PhaseSystems . . . . . . . . . . . . . . . . . . . . . . . . . . 311 5.6.1 Minimum-PhaseandAll-PassDecomposition . . . . . . . . . . 311 5.6.2 Frequency-ResponseCompensationofNon-Minimum-Phase Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313 5.6.3 PropertiesofMinimum-PhaseSystems . . . . . . . . . . . . . . 318 5.7 LinearSystemswithGeneralizedLinearPhase . . . . . . . . . . . . . . 322 5.7.1 SystemswithLinearPhase . . . . . . . . . . . . . . . . . . . . . 322 5.7.2 GeneralizedLinearPhase . . . . . . . . . . . . . . . . . . . . . 326 5.7.3 CausalGeneralizedLinear-PhaseSystems . . . . . . . . . . . . 328 5.7.4 RelationofFIRLinear-PhaseSystemstoMinimum-Phase Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338 5.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341 viii Contents 6 StructuresforDiscrete-TimeSystems 374 6.0 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374 6.1 BlockDiagramRepresentationofLinearConstant-Coefficient DifferenceEquations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375 6.2 SignalFlowGraphRepresentation . . . . . . . . . . . . . . . . . . . . . 382 6.3 BasicStructuresforIIRSystems . . . . . . . . . . . . . . . . . . . . . . 388 6.3.1 DirectForms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388 6.3.2 CascadeForm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390 6.3.3 ParallelForm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393 6.3.4 FeedbackinIIRSystems . . . . . . . . . . . . . . . . . . . . . . 395 6.4 TransposedForms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397 6.5 BasicNetworkStructuresforFIRSystems . . . . . . . . . . . . . . . . 401 6.5.1 DirectForm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401 6.5.2 CascadeForm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402 6.5.3 StructuresforLinear-PhaseFIRSystems . . . . . . . . . . . . . 403 6.6 LatticeFilters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405 6.6.1 FIRLatticeFilters . . . . . . . . . . . . . . . . . . . . . . . . . . 406 6.6.2 All-PoleLatticeStructure. . . . . . . . . . . . . . . . . . . . . . 412 6.6.3 GeneralizationofLatticeSystems . . . . . . . . . . . . . . . . . 415 6.7 OverviewofFinite-PrecisionNumericalEffects . . . . . . . . . . . . . 415 6.7.1 NumberRepresentations . . . . . . . . . . . . . . . . . . . . . . 415 6.7.2 QuantizationinImplementingSystems . . . . . . . . . . . . . . 419 6.8 TheEffectsofCoefficientQuantization . . . . . . . . . . . . . . . . . . 421 6.8.1 EffectsofCoefficientQuantizationinIIRSystems . . . . . . . 422 6.8.2 ExampleofCoefficientQuantizationinanEllipticFilter . . . . 423 6.8.3 PolesofQuantized2nd-OrderSections . . . . . . . . . . . . . . 427 6.8.4 EffectsofCoefficientQuantizationinFIRSystems . . . . . . . 429 6.8.5 ExampleofQuantizationofanOptimumFIRFilter . . . . . . 431 6.8.6 MaintainingLinearPhase. . . . . . . . . . . . . . . . . . . . . . 434 6.9 EffectsofRound-offNoiseinDigitalFilters . . . . . . . . . . . . . . . 436 6.9.1 AnalysisoftheDirectFormIIRStructures . . . . . . . . . . . . 436 6.9.2 ScalinginFixed-PointImplementationsofIIRSystems . . . . . 445 6.9.3 ExampleofAnalysisofaCascadeIIRStructure . . . . . . . . . 448 6.9.4 AnalysisofDirect-FormFIRSystems . . . . . . . . . . . . . . . 453 6.9.5 Floating-PointRealizationsofDiscrete-TimeSystems. . . . . . 458 6.10 Zero-InputLimitCyclesinFixed-PointRealizationsofIIR DigitalFilters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459 6.10.1 LimitCyclesOwingtoRound-offandTruncation . . . . . . . . 459 6.10.2 LimitCyclesOwingtoOverflow . . . . . . . . . . . . . . . . . . 462 6.10.3 AvoidingLimitCycles. . . . . . . . . . . . . . . . . . . . . . . . 463 6.11 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464 7 FilterDesignTechniques 493 7.0 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493 7.1 FilterSpecifications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494 Contents ix 7.2 DesignofDiscrete-TimeIIRFiltersfromContinuous-TimeFilters. . . 496 7.2.1 FilterDesignbyImpulseInvariance . . . . . . . . . . . . . . . . 497 7.2.2 BilinearTransformation. . . . . . . . . . . . . . . . . . . . . . . 504 7.3 Discrete-TimeButterworth,ChebyshevandEllipticFilters . . . . . . . 508 7.3.1 ExamplesofIIRFilterDesign . . . . . . . . . . . . . . . . . . . 509 7.4 FrequencyTransformationsofLowpassIIRFilters . . . . . . . . . . . . 526 7.5 DesignofFIRFiltersbyWindowing . . . . . . . . . . . . . . . . . . . . 533 7.5.1 PropertiesofCommonlyUsedWindows . . . . . . . . . . . . . 535 7.5.2 IncorporationofGeneralizedLinearPhase. . . . . . . . . . . . 538 7.5.3 TheKaiserWindowFilterDesignMethod . . . . . . . . . . . . 541 7.6 ExamplesofFIRFilterDesignbytheKaiserWindowMethod . . . . . 545 7.6.1 LowpassFilter . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545 7.6.2 HighpassFilter . . . . . . . . . . . . . . . . . . . . . . . . . . . . 547 7.6.3 Discrete-TimeDifferentiators . . . . . . . . . . . . . . . . . . . 550 7.7 OptimumApproximationsofFIRFilters . . . . . . . . . . . . . . . . . 554 7.7.1 OptimalTypeILowpassFilters . . . . . . . . . . . . . . . . . . 559 7.7.2 OptimalTypeIILowpassFilters . . . . . . . . . . . . . . . . . . 565 7.7.3 TheParks–McClellanAlgorithm . . . . . . . . . . . . . . . . . . 566 7.7.4 CharacteristicsofOptimumFIRFilters . . . . . . . . . . . . . . 568 7.8 ExamplesofFIREquirippleApproximation . . . . . . . . . . . . . . . 570 7.8.1 LowpassFilter . . . . . . . . . . . . . . . . . . . . . . . . . . . . 570 7.8.2 CompensationforZero-OrderHold . . . . . . . . . . . . . . . 571 7.8.3 BandpassFilter . . . . . . . . . . . . . . . . . . . . . . . . . . . 576 7.9 CommentsonIIRandFIRDiscrete-TimeFilters . . . . . . . . . . . . 578 7.10 DesignofanUpsamplingFilter . . . . . . . . . . . . . . . . . . . . . . . 579 7.11 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 582 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 582 8 TheDiscreteFourierTransform 623 8.0 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 623 8.1 RepresentationofPeriodicSequences:TheDiscreteFourierSeries . . 624 8.2 PropertiesoftheDFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . 628 8.2.1 Linearity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 629 8.2.2 ShiftofaSequence . . . . . . . . . . . . . . . . . . . . . . . . . 629 8.2.3 Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 629 8.2.4 SymmetryProperties . . . . . . . . . . . . . . . . . . . . . . . . 630 8.2.5 PeriodicConvolution . . . . . . . . . . . . . . . . . . . . . . . . 630 8.2.6 SummaryofPropertiesoftheDFSRepresentationofPeriodic Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633 8.3 TheFourierTransformofPeriodicSignals . . . . . . . . . . . . . . . . 633 8.4 SamplingtheFourierTransform . . . . . . . . . . . . . . . . . . . . . . 638 8.5 FourierRepresentationofFinite-DurationSequences . . . . . . . . . . 642 8.6 PropertiesoftheDFT . . . . . . . . . . . . . . . . . . . . . . . . . . . . 647 8.6.1 Linearity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 647 8.6.2 CircularShiftofaSequence . . . . . . . . . . . . . . . . . . . . 648 8.6.3 Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 650 8.6.4 SymmetryProperties . . . . . . . . . . . . . . . . . . . . . . . . 653