D C ISCRETE AND ONTINUOUS F T OURIER RANSFORMS ANALYSIS, APPLICATIONS AND FAST ALGORITHMS D C ISCRETE AND ONTINUOUS F T OURIER RANSFORMS ANALYSIS, APPLICATIONS AND FAST ALGORITHMS Eleanor Chu University of Guelph Guelph, Ontario, Canada MATLAB® is a trademark of The MathWorks, Inc. and is used with permission. The MathWorks does not warrant the accuracy of the text or exercises in this book. This book’s use or discussion of MATLAB® software or related products does not constitute endorsement or sponsorship by The MathWorks of a particular pedagogical approach or particular use of the MATLAB® software. Chapman & Hall/CRC Taylor & Francis Group 6000 Broken Sound Parkway NW, Suite 300 Boca Raton, FL 33487-2742 © 2008 by Taylor & Francis Group, LLC Chapman & Hall/CRC is an imprint of Taylor & Francis Group, an Informa business No claim to original U.S. Government works Printed in the United States of America on acid-free paper 10 9 8 7 6 5 4 3 2 1 International Standard Book Number-13: 978-1-4200-6363-9 (Hardcover) This book contains information obtained from authentic and highly regarded sources Reasonable efforts have been made to publish reliable data and information, but the author and publisher cannot assume responsibility for the valid- ity of all materials or the consequences of their use. The Authors and Publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or uti- lized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopy- ing, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers. For permission to photocopy or use material electronically from this work, please access www.copyright.com (http:// www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC) 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For orga- nizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged. Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe. Visit the Taylor & Francis Web site at http://www.taylorandfrancis.com and the CRC Press Web site at http://www.crcpress.com Contents ListofFigures xi ListofTables xv Preface xvii Acknowledgments xxi AbouttheAuthor xxiii I Fundamentals, AnalysisandApplications 1 1 AnalyticalandGraphicalRepresentationofFunctionContents 3 1.1 TimeandFrequencyContentsofaFunction . . . . . . . . . . . . . . . . . . 3 1.2 TheFrequency-DomainPlotsasGraphicalTools . . . . . . . . . . . . . . . 4 1.3 IdentifyingtheCosineandSineModes . . . . . . . . . . . . . . . . . . . . . 6 1.4 UsingComplexExponentialModes . . . . . . . . . . . . . . . . . . . . . . 7 1.5 UsingCosineModeswithPhaseorTimeShifts . . . . . . . . . . . . . . . . 9 1.6 PeriodicityandCommensurateFrequencies . . . . . . . . . . . . . . . . . . 12 1.7 ReviewofResultsandTechniques . . . . . . . . . . . . . . . . . . . . . . . 13 1.7.1 Practicingthetechniques . . . . . . . . . . . . . . . . . . . . . . . . 15 1.8 ExpressingSingleComponentSignals . . . . . . . . . . . . . . . . . . . . . 19 1.9 GeneralFormofaSinusoidinSignalApplication . . . . . . . . . . . . . . . 20 1.9.1 Expressingsequencesofdiscrete-timesamples . . . . . . . . . . . . 21 1.9.2 Periodicityofsinusoidalsequences . . . . . . . . . . . . . . . . . . 22 1.10 FourierSeries:ATopictoCome . . . . . . . . . . . . . . . . . . . . . . . . 23 1.11 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2 SamplingandReconstructionofFunctions–PartI 27 2.1 DFTandBand-LimitedPeriodicSignal . . . . . . . . . . . . . . . . . . . . 27 2.2 FrequenciesAliasedbySampling. . . . . . . . . . . . . . . . . . . . . . . . 32 2.3 Connection:Anti-AliasingFilter . . . . . . . . . . . . . . . . . . . . . . . . 36 2.4 AlternateNotationsandFormulas . . . . . . . . . . . . . . . . . . . . . . . 36 2.5 SamplingPeriodandAlternateFormsofDFT . . . . . . . . . . . . . . . . . 38 2.6 SampleSizeandAlternateFormsofDFT . . . . . . . . . . . . . . . . . . . 41 v vi CONTENTS 3 TheFourierSeries 45 3.1 FormalExpansions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.1.1 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.2 Time-LimitedFunctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.3 EvenandOddFunctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.4 Half-RangeExpansions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.5 FourierSeriesUsingComplexExponentialModes. . . . . . . . . . . . . . . 60 3.6 Complex-ValuedFunctions . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.7 FourierSeriesinOtherVariables . . . . . . . . . . . . . . . . . . . . . . . . 61 3.8 TruncatedFourierSeriesandLeastSquares . . . . . . . . . . . . . . . . . . 61 3.9 OrthogonalProjectionsandFourierSeries . . . . . . . . . . . . . . . . . . . 63 3.9.1 TheCauchy(cid:150)Schw arzinequality . . . . . . . . . . . . . . . . . . . . 68 3.9.2 TheMinkowskiinequality . . . . . . . . . . . . . . . . . . . . . . . 71 3.9.3 Projections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 3.9.4 Least-squaresapproximation . . . . . . . . . . . . . . . . . . . . . . 74 3.9.5 Bessel(cid:146)sinequalityandRiemann(cid:146)slemma . . . . . . . . . . . . . . . 77 3.10 ConvergenceoftheFourierSeries . . . . . . . . . . . . . . . . . . . . . . . 79 3.10.1 Startingwithaconcreteexample . . . . . . . . . . . . . . . . . . . . 79 3.10.2 Pointwiseconvergence(cid:151) alocalproperty . . . . . . . . . . . . . . . 82 3.10.3 Therateofconvergence(cid:151) aglobalproperty . . . . . . . . . . . . . . 87 3.10.4 TheGibbsphenomenon . . . . . . . . . . . . . . . . . . . . . . . . 89 3.10.5 TheDirichletkernelperspective . . . . . . . . . . . . . . . . . . . . 91 3.10.6 EliminatingtheGibbseffectbytheCesarosum . . . . . . . . . . . . 95 3.10.7 ReducingtheGibbseffectbyLanczossmoothing . . . . . . . . . . . 99 3.10.8 Themodi(cid:30) cationofFourierseriescoef(cid:30) cients. . . . . . . . . . . . . 100 3.11 AccountingforAliasedFrequenciesinDFT . . . . . . . . . . . . . . . . . . 102 3.11.1 Samplingfunctionswithjumpdiscontinuities . . . . . . . . . . . . . 104 4 DFTandSampledSignals 109 4.1 DerivingtheDFTandIDFTFormulas . . . . . . . . . . . . . . . . . . . . . 109 4.2 DirectConversionBetweenAlternateForms . . . . . . . . . . . . . . . . . . 114 4.3 DFTofConcatenatedSampleSequences . . . . . . . . . . . . . . . . . . . . 116 4.4 DFTCoefc(cid:30) ientsofaCommensurateSum . . . . . . . . . . . . . . . . . . . 117 4.4.1 DFTcoef(cid:30) cientsofsingle-componentsignals . . . . . . . . . . . . . 117 4.4.2 Makingdirectuseofthedigitalfrequencies . . . . . . . . . . . . . . 121 4.4.3 Commonperiodofsampledcompositesignals . . . . . . . . . . . . 123 4.5 FrequencyDistortionbyLeakage . . . . . . . . . . . . . . . . . . . . . . . . 126 4.5.1 Fourierseriesexpansionofanonharmoniccomponent . . . . . . . . 128 4.5.2 AliasedDFTcoef(cid:30) cientsofanonharmoniccomponent . . . . . . . . 129 4.5.3 Demonstratingleakagebynumericalexperiments . . . . . . . . . . . 131 4.5.4 Mismatchingperiodicextensions. . . . . . . . . . . . . . . . . . . . 131 4.5.5 Minimizingleakageinpractice . . . . . . . . . . . . . . . . . . . . . 134 4.6 TheEffectsofZeroPadding . . . . . . . . . . . . . . . . . . . . . . . . . . 134 4.6.1 Zeropaddingthesignal . . . . . . . . . . . . . . . . . . . . . . . . . 134 CONTENTS vii 4.6.2 ZeropaddingtheDFT . . . . . . . . . . . . . . . . . . . . . . . . . 141 4.7 ComputingDFTDen(cid:30) ingFormulasPerSe. . . . . . . . . . . . . . . . . . . 147 4.7.1 ProgrammingDFTinMATLAB(cid:1)R . . . . . . . . . . . . . . . . . . . 147 5 SamplingandReconstructionofFunctions–PartII 157 5.1 SamplingNonperiodicBand-LimitedFunctions . . . . . . . . . . . . . . . . 158 5.1.1 Fourierseriesoffrequency-limitedX(f) . . . . . . . . . . . . . . . 159 5.1.2 InverseFouriertransformoffrequency-limitedX(f) . . . . . . . . . 159 5.1.3 Recoveringthesignalanalytically . . . . . . . . . . . . . . . . . . . 160 5.1.4 Furtherdiscussionofthesamplingtheorem . . . . . . . . . . . . . . 161 5.2 DerivingtheFourierTransformPair . . . . . . . . . . . . . . . . . . . . . . 162 5.3 TheSineandCosineFrequencyContents . . . . . . . . . . . . . . . . . . . 164 5.4 TabulatingTwoSetsofFundamentalFormulas. . . . . . . . . . . . . . . . . 165 5.5 ConnectionswithTime/FrequencyRestrictions . . . . . . . . . . . . . . . . 165 5.5.1 ExamplesofFouriertransformpair . . . . . . . . . . . . . . . . . . 167 5.6 FourierTransformProperties . . . . . . . . . . . . . . . . . . . . . . . . . . 171 5.6.1 Derivingtheproperties . . . . . . . . . . . . . . . . . . . . . . . . . 172 5.6.2 Utilitiesoftheproperties . . . . . . . . . . . . . . . . . . . . . . . . 175 5.7 AlternateFormoftheFourierTransform . . . . . . . . . . . . . . . . . . . . 177 5.8 ComputingtheFourierTransformfromDiscrete-TimeSamples . . . . . . . . 178 5.8.1 Almosttime-limitedandband-limitedfunctions . . . . . . . . . . . . 179 5.9 ComputingtheFourierCoef(cid:30) cientsfromDiscrete-TimeSamples . . . . . . . 181 5.9.1 Periodicandalmostband-limitedfunction . . . . . . . . . . . . . . . 182 6 SamplingandReconstructionofFunctions–PartIII 185 6.1 ImpulseFunctionsandTheirProperties . . . . . . . . . . . . . . . . . . . . 185 6.2 GeneratingtheFourierTransformPairs . . . . . . . . . . . . . . . . . . . . 188 6.3 ConvolutionandFourierTransform . . . . . . . . . . . . . . . . . . . . . . 189 6.4 PeriodicConvolutionandFourierSeries . . . . . . . . . . . . . . . . . . . . 192 6.5 ConvolutionwiththeImpulseFunction. . . . . . . . . . . . . . . . . . . . . 194 6.6 ImpulseTrainasaGeneralizedFunction . . . . . . . . . . . . . . . . . . . . 195 6.7 ImpulseSamplingofContinuous-TimeSignals . . . . . . . . . . . . . . . . 202 6.8 NyquistSamplingRateRediscovered. . . . . . . . . . . . . . . . . . . . . . 203 6.9 SamplingTheoremforBand-LimitedSignal . . . . . . . . . . . . . . . . . . 207 6.10 SamplingofBand-PassSignals . . . . . . . . . . . . . . . . . . . . . . . . . 209 7 FourierTransformofaSequence 211 7.1 DerivingtheFourierTransformofaSequence . . . . . . . . . . . . . . . . . 211 7.2 PropertiesoftheFourierTransformofaSequence . . . . . . . . . . . . . . . 215 7.3 GeneratingtheFourierTransformPairs . . . . . . . . . . . . . . . . . . . . 217 7.3.1 TheKroneckerdeltasequence . . . . . . . . . . . . . . . . . . . . . 217 7.3.2 RepresentingsignalsbyKroneckerdelta . . . . . . . . . . . . . . . . 218 7.3.3 Fouriertransformpairs . . . . . . . . . . . . . . . . . . . . . . . . . 219 7.4 DualityinConnectionwiththeFourierSeries . . . . . . . . . . . . . . . . . 226 viii CONTENTS 7.4.1 Periodicconvolutionanddiscreteconvolution . . . . . . . . . . . . . 227 7.5 TheFourierTransformofaPeriodicSequence . . . . . . . . . . . . . . . . . 229 7.6 TheDFTInterpretation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 7.6.1 TheinterpretedDFTandtheFouriertransform . . . . . . . . . . . . 234 7.6.2 Time-limitedcase . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235 7.6.3 Band-limitedcase . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 7.6.4 Periodicandband-limitedcase . . . . . . . . . . . . . . . . . . . . . 237 8 TheDiscreteFourierTransformofaWindowedSequence 239 8.1 ARectangularWindowofIn(cid:30) niteWidth . . . . . . . . . . . . . . . . . . . . 239 8.2 ARectangularWindowofAppropriateFiniteWidth . . . . . . . . . . . . . . 241 8.3 FrequencyDistortionbyImproperTruncation . . . . . . . . . . . . . . . . . 243 8.4 WindowingaGeneralNonperiodicSequence . . . . . . . . . . . . . . . . . 244 8.5 Frequency-DomainPropertiesofWindows . . . . . . . . . . . . . . . . . . . 245 8.5.1 Therectangularwindow . . . . . . . . . . . . . . . . . . . . . . . . 246 8.5.2 Thetriangularwindow . . . . . . . . . . . . . . . . . . . . . . . . . 247 8.5.3 ThevonHannwindow . . . . . . . . . . . . . . . . . . . . . . . . . 248 8.5.4 TheHammingwindow . . . . . . . . . . . . . . . . . . . . . . . . . 250 8.5.5 TheBlackmanwindow . . . . . . . . . . . . . . . . . . . . . . . . . 251 8.6 ApplicationsoftheWindowedDFT . . . . . . . . . . . . . . . . . . . . . . 252 8.6.1 Severalscenarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252 8.6.2 SelectingthelengthofDFTinpractice . . . . . . . . . . . . . . . . 263 9 DiscreteConvolutionandtheDFT 267 9.1 LinearDiscreteConvolution . . . . . . . . . . . . . . . . . . . . . . . . . . 267 9.1.1 Linearconvolutionoftwon(cid:30) itesequences. . . . . . . . . . . . . . . 267 9.1.2 Sectioningalongsequenceforlinearconvolution . . . . . . . . . . . 273 9.2 PeriodicDiscreteConvolution . . . . . . . . . . . . . . . . . . . . . . . . . 273 9.2.1 De(cid:30)n itionbasedontwoperiodicsequences . . . . . . . . . . . . . . 273 9.2.2 Convertinglineartoperiodicconvolution . . . . . . . . . . . . . . . 275 9.2.3 De(cid:30) ningtheequivalentcyclicconvolution . . . . . . . . . . . . . . . 275 9.2.4 Thecyclicconvolutioninmatrixform . . . . . . . . . . . . . . . . . 278 9.2.5 Convertinglineartocyclicconvolution . . . . . . . . . . . . . . . . 280 9.2.6 Twocyclicconvolutiontheorems. . . . . . . . . . . . . . . . . . . . 280 9.2.7 Implementingsectionedlinearconvolution . . . . . . . . . . . . . . 283 9.3 TheChirpFourierTransform . . . . . . . . . . . . . . . . . . . . . . . . . . 284 9.3.1 Thescenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284 9.3.2 Theequivalentpartiallinearconvolution. . . . . . . . . . . . . . . . 285 9.3.3 Theequivalentpartialcyclicconvolution . . . . . . . . . . . . . . . 286 10 ApplicationsoftheDFTinDigitalFilteringandFilters 291 10.1 TheBackground. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291 10.2 Application-OrientedTerminology . . . . . . . . . . . . . . . . . . . . . . . 292 10.3 RevisitGibbsPhenomenonfromtheFilteringViewpoint . . . . . . . . . . . 294 CONTENTS ix 10.4 ExperimentingwithDigitalFilteringandFilterDesign . . . . . . . . . . . . 296 II FastAlgorithms 303 11 IndexMappingandMixed-RadixFFTs 305 11.1 AlgebraicDFTversusFFT-ComputedDFT . . . . . . . . . . . . . . . . . . 305 11.2 TheRoleofIndexMapping . . . . . . . . . . . . . . . . . . . . . . . . . . . 306 11.2.1 Thedecouplingprocess(cid:151) StageI . . . . . . . . . . . . . . . . . . . 307 11.2.2 Thedecouplingprocess(cid:151) StageII . . . . . . . . . . . . . . . . . . . 309 11.2.3 Thedecouplingprocess(cid:151) StageIII . . . . . . . . . . . . . . . . . . . 311 11.3 TheRecursiveEquationApproach . . . . . . . . . . . . . . . . . . . . . . . 313 11.3.1 CountingshortDFTorDFT-liketransforms . . . . . . . . . . . . . . 313 11.3.2 TherecursiveequationforarbitrarycompositeN . . . . . . . . . . . 313 11.3.3 Specializationtotheradix-2DITFFTforN =2ν . . . . . . . . . . 315 11.4 OtherFormsbyAlternateIndexSplitting. . . . . . . . . . . . . . . . . . . . 317 11.4.1 TherecursiveequationforarbitrarycompositeN . . . . . . . . . . . 318 11.4.2 Specializationtotheradix-2DIFFFTforN =2ν . . . . . . . . . . . 319 12 KroneckerProductFactorizationandFFTs 321 12.1 ReformulatingtheTwo-FactorMixed-RadixFFT . . . . . . . . . . . . . . . 322 12.2 FromTwo-FactortoMulti-FactorMixed-RadixFFT . . . . . . . . . . . . . . 328 12.2.1 SelectedpropertiesandrulesforKroneckerproducts . . . . . . . . . 329 12.2.2 CompletefactorizationoftheDFTmatrix . . . . . . . . . . . . . . . 331 12.3 OtherFormsbyAlternateIndexSplitting. . . . . . . . . . . . . . . . . . . . 333 12.4 FactorizationResultsbyAlternateExpansion . . . . . . . . . . . . . . . . . 335 12.4.1 Unorderedmixed-radixDITFFT. . . . . . . . . . . . . . . . . . . . 335 12.4.2 Unorderedmixed-radixDIFFFT . . . . . . . . . . . . . . . . . . . . 337 12.5 UnorderedFFTforScrambledInput . . . . . . . . . . . . . . . . . . . . . . 337 12.6 UtilitiesoftheKroneckerProductFactorization . . . . . . . . . . . . . . . . 339 13 TheFamilyofPrimeFactorFFTAlgorithms 341 13.1 ConnectingtheRelevantIdeas . . . . . . . . . . . . . . . . . . . . . . . . . 342 13.2 DerivingtheTwo-FactorPFA . . . . . . . . . . . . . . . . . . . . . . . . . . 343 13.2.1 StageI:Nonstandardindexmappingschemes . . . . . . . . . . . . . 343 13.2.2 StageII:DecouplingtheDFTcomputation . . . . . . . . . . . . . . 345 13.2.3 OrganizingthePFAcomputation(cid:150)P art1 . . . . . . . . . . . . . . . . 346 13.3 MatrixFormulationoftheTwo-FactorPFA . . . . . . . . . . . . . . . . . . 348 13.3.1 StageIII:TheKroneckerproductfactorization . . . . . . . . . . . . 348 13.3.2 StageIV:De(cid:30) ningpermutationmatrices . . . . . . . . . . . . . . . . 348 13.3.3 StageV:Completingthematrixfactorization . . . . . . . . . . . . . 350 13.4 MatrixFormulationoftheMulti-FactorPFA . . . . . . . . . . . . . . . . . . 350 13.4.1 OrganizingthePFAcomputation(cid:151) Part2 . . . . . . . . . . . . . . . 352 13.5 NumberTheoryandIndexMappingbyPermutations . . . . . . . . . . . . . 353