2023学年完整公开课版Chapter5

1Chapter5

TheFastFourierTransform2Outline5.1

RelationshipoftheFFTtotheDFT5.2DerivationoftheRadix-2FFTAlgorithm5.3FFTInput/OutputDataIndexBitReversal5.4Radix-2FFTButterflyStructures5.5

DiscreteConvolutionusingFFT5.1RelationshipoftheFFTtotheDFT3

4Theradix-2FFTeliminatestheredundanciesandgreatlyreducesthenumberofnecessaryarithmeticoperations.ToappreciatetheFFT’sefficiency,let’sconsiderthenumberofcomplexmultiplicationsnecessaryforouroldfriend,theexpressionforanN-pointDFTEq5-1Foran8-pointDFT,Eq.(5–1)tellsusthatwe’dhavetoperformN2or64complexmultiplications.5Aswe'llverifyinlatersectionsofthischapter,thenumberofcomplexmultiplications,foranN-pointFFT,isapproximately:Eq5-26Forexample:WhenN=512,theDFTrequires200timesmorecomplexmultiplicationsthanthoseneededbytheFFT.WhenN=8192,theDFTmustcalculate1000complexmultiplicationsforeachcomplexmultiplicationintheFFT!7Figure5-1-1NumberofcomplexmultiplicationsintheDFTandtheradix-2FFTasafunctionofN.5.2DerivationoftheRadix-2FFTAlgorithm8ToseejustexactlyhowtheFFTevolvedfromtheDFT,wereturntotheequationforanN-pointDFT:Eq5-39AstraightforwardderivationoftheFFTproceedswiththeseparationoftheinputdatasequencex(n)intotwoparts.Whenx(n)issegmentedintoitsevenandoddindexedelements,wecan,then,breakEq.(5-3)intotwopartsasEq5-410Pullingtheconstantphaseangleoutsidethesecondsummation:Eq5-4

Eq5-511

Eq5-6There'safurtherbenefitinbreakingtheN-pointDFTintotwopartsbecausetheupperhalfoftheDFToutputiseasytocalculate.ConsidertheX(m+N/2).Eq5-712Itlookslikewe’recomplicatingthings,right?Well,justhanginthereforamoment.Wecannowsimplifythephaseangletermsinsidethesummationsbecauseforanyintegern.Lookingattheso-calledtwiddlefactorinfrontofthesecondsummationinEq.(5-7),wecansimplifyitasEq5-8Eq5-913Now,let’srepeatEqs.(5-6)and(5-9)toseethesimilarity;andEq5-10Eq5-1114Sohereweare.WeneednotperformanysineorcosinemultiplicationstogetX(m+N/2).WejustchangethesignofthetwiddlefactorWmNandusetheresultsofthetwosummationsfromX(m)togetX(m+N/2).Ofcourse,mgoesfrom0to(N/2)–1inEq.(5-9)whichmeans,foranN-pointDFT,weperformanN/2-pointDFTtogetthefirstN/2outputsandusethosetogetthelastN/2outputs.ForN=8,Eqs.(5-9)and(5-10)areimplementedasshowninFigure5-2-1.15Figure5-2-1FFTimplementationofan8-pointDFTusingtwo4-pointDFTs.16IfwesimplifyEqs.(5-9)and(5-10)totheformandEq5-12Eq5-1317Wecangofurtherandthinkaboutbreakingthetwo4-pointDFTsintofour2-pointDFTs.Let’sseehowwecansubdividetheupper4-pointDFTinFig-ure4–2whosefouroutputsareA(m)inEqs.(5-12)and(5-13).Wesegmenttheinputstotheupper4-pointDFTintotheiroddandevencomponentBecause,wecanexpressA(m)intheformoftwoN/4-pointDFTs,asEq5-14Eq5-1518ThiscapabilitytosubdivideanN/2-pointDFTintotwoN/4-pointDFTsgivestheFFTitscapacitytogreatlyreducethenumberofnecessarymultiplicationstoimplementDFTs.FollowingthesamestepsweusedtoobtainedA(m),wecanshowthatEq.(5-13)’sB(m)isEq5-1619TheFFT’swell-knownbutterflypatternofsignalflowsiscertainlyevident,andweseethefurthershufflingoftheinputdatainFigure5-2-2.20Figure5-2-2FFTimplementationofan8-pointDFTastwo4-pointDFTsandfour2-pointDFTs.21Figure5-2-3Single2-pointDFTbutterfly.Figure5-2-4Cyclicredundanciesinthetwiddlefactorsofan8-pointFFT.22

5.3FFTInput/OutputDataIndexBitReversal23Noticethatthe“Fulldecimation-in-timeFFTimplementationofan8-pointDFT.”Thedecimation-in-timephrasereferstohowwebroketheDFTinputsamplesintooddandevenpartsinthederivationofEqs.(5–11),(5–15),and(5–16).Thistimedecimationleadstothescrambledorderoftheinputdata’sindexn.ThepatternofthisshuffledordercanbeunderstoodwiththehelpofTable5–1.Theshufflingoftheinputdataisknownasbitreversalbecausethescrambledorderoftheinputdataindexcanbeobtainedbyreversingthebitsofthebinaryrepresentationofthenormalinputdataindexorder.24Table5-1InputIndexBitReversalforan8-pointFFT5.4Radix-2FFTButterflyStructures

(ObtainthediagramfromFFT-DiagramCollectioninthischapter)

25

26Figure5-4-4showsanFFTsignal-flowstructurethatavoidsthebitreversalproblemaltogether,andthegracefulweaveofthetraditionalFFTbutterfliesisreplacedwithatangled,buteffective,configuration.27Figure5-4-1Fulldecimation-in-timeFFTimplementationofan8-pointDFT.FFT-DiagramCollection-128FFT-DiagramCollection-2Figure5-4-28-pointdecimation-in-timeFFTwithbit-reversedinputs.29FFT-DiagramCollection-3Figure5-4-38-pointdecimation-in-timeFFTwithbit-reversedoutputs.30FFT-DiagramCollection-4Figure5-4-48-pointdecimation-in-timeFFTwithinputsandoutputsinnormalorder.31FFT-DiagramCollection-5Figure5-4-58-pointdecimation-in-frequencyFFTwithbit-reversedinputs.32FFT-DiagramCollection-6Figure5-4-68-pointdecimation-in-frequencyFFTwithbit-reversedoutputs.33FFT-DiagramCollection-7Figure5-4-78-pointdecimation-in-frequencyFFTwithinputsandoutputsinnormalorder.34FFT-DiagramCollection-8Figure5-4-8Decimation-in-timeanddecimation-in-frequencybutterflystructures:(a)originalform;(b)simplifiedform;(c)optimizedform.35FFT-DiagramCollection-9Figure5-4-9AlternateFFTbutterflynotation:(a)decimation-in-time;(b)decimation-in-frequency36Figure5-4-4showsanFFTsignal-flowstructurethatavoidsthebitreversalproblemaltogether,andthegracefulweaveofthetraditionalFFTbutterfliesisreplacedwithatangled,buteffective,configuration.37Anequivalentdecimation-in-frequencyFFTstructureexistsforeachdecimation-in-timeFFTstructure.It’simportanttonotethatthenumberofnecessarymultiplicationstoimplementthedecimation-in-frequencyFFTalgorithmsisthesameasthenumbernecessaryforthedecimation-in-timeFFTalgorithms.38TheFFTbutterflystructuresinFigures5-4-1,5-4-2,5-4-4,5-4-5,and5-4-6arethedirectresultofthederivationsofthedecimation-in-timeanddecimation-in-frequencyalgorithms.Althoughit’snotveryobviousatfirst,thetwiddlefactorexponentsshowninthesestructuresdohaveaconsistentpattern.39Considerthedecimation-in-timebutterflyinFigure5-4-8(a).Ifthetopinputisxandthebottominputisy,thetopbutterflyoutputwouldbeEq5-17Eq5-18andthebottombutterflyoutputwouldbe40TheoperationsinEqs.(5-17)and(5-18)canbesimplifiedbecausethetwotwiddlefactorsarerelatedbyEq5-1941TheFFTbutterflystructurespreviouslydiscussedtypicallyfallintooneoftwocategories:in-placeFFTalgorithmsanddouble-memoryFFTalgorithms.42There’sanotherclassofFFTstructures,knownasconstant-geometryalgorithms,thatmaketheaddressingofmemorybothsimpleandconstantforeachstageoftheFFT.Thesestructuresareofinteresttothosefolkswhobuildspecial-purposeFFThardwaredevices.Fortwo-dimensionalFFTapplications,suchasprocessingphotographicimages,thedecimation-in-frequencyalgorithmsappeartobetheoptimumchoice.5.5DiscreteConvolutionusingFFT43WenextconsidertheDFT-basedimplementationofwhereh[n]isafinite-lengthsequenceoflengthMandx[n]isaninfinitelength(orafinitelengthsequenceoflengthmuchgreaterthanM).

44Wefirstsegmentx[n],assumedtobeacausalsequenceherewithoutanylossofgenerality,intoasetofcontiguousfinite-lengthsubsequencesxm[n]oflengthNeach:where

Overlap-AddMethod45Thuswecanwrite

where

46

EachoftheseshortconvolutionscanbeimplementedusingtheDFT-basedmethoddiscussedearlier,wherenowtheDFTs(andtheIDFT)arecomputedonthebasisof(N+M-1)points.47Thereisonemoresubtletytotakecareofbeforewecanimplement

usingtheDFT-basedapproach

48

Sothat,thereisanoverlapofM-1samplesbetweenthesetwoshortlinearconvolutions.

49

ThisprocessisillustratedinthefigureonthenextslideforM=5andN=7.505152Therefore,y[n]obtainedbyalinearconvolutionofx[n]andh[n]isgivenby:

Theaboveprocedureiscalledtheoverlap-addmethodsincetheresultsoftheshortlinearconvolutionsoverlapandtheoverlappedportionsareaddedtogetthecorrectfinalresult.53Overlap-SavedMethodInimplementingtheoverlap-addmethodusingtheDFT,weneedtocomputetwo(N+M-1)-pointDFTsandone(N+M-1)-pointIDFTsincetheoveralllinearconvolutionwasexpressedasasumofshort-lengthlinearconvolutionsoflength(N+M-1)each.Itispossibletoimplementtheoveralllinearconvolutionbyperforminginsteadcircularconv