數字信號處理英文版課件：Chap 11 DFT Algorithm Implementation(P449)

11DFTAlgorithmImplementation(P449)★Goertzel’sAlgorithm★Decimation-in-TimeFFTAlgorithmDIT-FFT★Decimation-in-FrequencyFFTAlgorithmDIF-FFT★

InverseDFTComputation★SlidingDiscreteFourierTransform★DFTComputationOveraNarrowFrequencyBand111.1ComputationoftheDiscreteFourierTransformSuppose:x[n]inputsignalwithlengthN

(11.1)(11.2)21.ThenumberofmultiplicationsandadditionsinimplementingtheDFTdirectly.11.1ComputationoftheDiscreteFourierTransformDFT:IDFT:x[n]

maybecomplex,eachX[k](or

x[n])needcomputing:

complexmultiplications:

Ntimes

complexadditions:

N-1times3sothetotalX[k](or

x[n]withnumberN)needcomputing:

complexmultiplications:

N2times

complexadditions:

N(N-1)times.Therefore,eachX[k]:Realmultiplications:4Ntimes,Realadditions:4N-2times.11.1ComputationoftheDiscreteFourierTransform4So

totalX[k]needcomputation:realmultiplications:4N2timesrealadditions:

N(4N-2)times.Ncomplexmultiplicationcomplexaddition16256240102499264409640321281638416256

102410485761047552Ifonetimecomplexmultiplications:100andonetimecomplexadditions:20then,11.1ComputationoftheDiscreteFourierTransform52.ThesymmetryandperiodicitypropertiesofWNkn

:(1)

complexconjugatesymmetry(2)

periodicityinnandkThus,thenumberofmultiplicationcanbereducedby approximatelyafactorof2.11.1ComputationoftheDiscreteFourierTransform611.1.2Cooley-TukeyFFTAlgorithmsThebasicideabehindallfastalgorithmsforcomputingthediscreteFouriertransform(DFT),commonlycalledthefastFouriertransform(FFT)algorithms,istodecomposesuccessivelytheN-pointDFTcomputationintocomputationsofsmaller-sizeDFTandtotakeadvantageoftheperiodicityandsymmetrypropertiesofthecomplexnumber.7Suppose:N=2υeveninteger,1.AlgorithmprincipleDecimation-in-TimeFFTAlgorithm(DITFFT)8whereDecimation-in-TimeFFTAlgorithm(DITFFT)9SupposeN=8X0[0]x1[r]=x[2r+1]N/2-pointDFTN/2-pointDFTX0[1]X0[2]X0[3]X1[0]X1[1]X1[2]X1[3]X[0]X[1]X[2]X[3]X[4]X[5]X[6]X[7]x[0]x[2]x[4]x[6]x[1]x[3]x[5]x[7]x0[r]=x[2r]Figure11.5Decimation-in-TimeFFTAlgorithm(DITFFT)10N/4-pointDFTx[0]x[4]X0[1]X0[2]X0[3]X0[0]WN/20=WN0WN/21=

WN2WN/23=WN6WN/22=

WN4N/4-pointDFTx[2]x[6]Decimation-in-TimeFFTAlgorithm(DITFFT)11X[1]X[2]X[3]X[4]X[5]X[0]X[6]X[7]WN0WN1WN2WN3WN4WN5WN6WN7WN0WN2WN6WN4WN0WN2WN6WN4N/4-pointDFTN/4-pointDFTN/4-pointDFTN/4-pointDFTx[0]x[4]x[2]x[6]x[1]x[5]x[3]x[7]Figure11.7Decimation-in-TimeFFTAlgorithm(DITFFT)12x[0]x[1]W20=WN0=1W21=WNN/2=-1Figure11.8For2-pointDFTDecimation-in-TimeFFTAlgorithm(DITFFT)13X[4]X[5]X[6]X[7]WN4WN5WN6WN7WN0WN2WN6WN4x[0]x[4]x[2]x[6]x[1]x[5]x[3]x[7]WN0WN0WN4WN4X[0]WN0WN2WN6WN4X[1]X[2]X[3]WN0WN1WN2WN3WN0WN0WN4WN4Figure11.9Decimation-in-TimeFFTAlgorithm(DITFFT)14Thetypicalcomputationintheupperfigureisshownasfollowing:Sothesimplificationofthebutterflyisgivenasfollowing,:butterflyflowgraphWNlWN(l+N/2)Figure11.10Figure11.11WN

l-1Decimation-in-TimeFFTAlgorithm(DITFFT)15x[0]x[4]x[2]x[6]x[1]x[5]x[3]x[7]WN0WN0WN0WN0-1-1-1-1WN2WN0WN2-1-1WN0-1-1X[1]X[2]X[3]X[4]X[5]X[0]X[6]X[7]WN0WN1WN2WN3-1-1-1-1Figure11.12Decimation-in-TimeFFTAlgorithm(DITFFT)162.ThenumberofcomplexmultiplicationandcomplexadditionsforFFTstages:butterfliesofeachstage:eachbutterfly:one-timecomplexmultiplicationandtwo-timecomplexadditionsN-pointFFT:timescomplexmultiplicationand

timescomplexadditionsComputingDFTdirectly:timescomplexmultiplicationandtimescomplexadditionsWN

l-1(m-1)ststagemststageDecimation-in-TimeFFTAlgorithm(DITFFT)17FFT:complexmultiplication:times

complexadditions:timesComputingDFTdirectly:complexmultiplications:timescomplexadditions:timesForexample:

Ifonetimecomplexmultiplications:100andonetimecomplexadditions:20then,computingDFTdirectly:FFT:Decimation-in-TimeFFTAlgorithm(DITFFT)183.Iterativeformulas(supplement)0tharrayinputx[n]tharrayoutputX[k]x[0]x[4]x[2]x[6]x[1]x[5]x[3]x[7]WN0WN0WN0WN0-1-1-1-1WN2WN0WN2-1-1WN0-1-1X[1]X[2]X[3]X[4]X[5]X[0]X[6]X[7]WN0WN1WN2WN3-1-1-1-1Decimation-in-TimeFFTAlgorithm(DITFFT)19WNl-1Ψ

m-1[i]Ψ

m-1[i+dm]Ψ

m[i]Ψ

m[i+dm]

ithline(i+dm)thlineΨ

m-1[i]theuppernodeofinputs;Ψ

m-1[i+dm]thelowernodeofinputs;Ψ

m

[i]theuppernodeofoutputs;Ψ

m[i+dm]thelowernodeofoutputs;dmthebutterflydistance;mnumberofarray(i.e.numberofstage)WNltheweightofbutterflyDecimation-in-TimeFFTAlgorithm(DITFFT)20butterflydistanceofmthstage(numberofbutterflyforeachgroup)Where:numberofgroupforeachstageDecimation-in-TimeFFTAlgorithm(DITFFT)21Example1:Decimation-in-TimeFFTAlgorithm(DITFFT)22Example2:Problem:Whenm=4,(1)Howmanybutterflygroups?(2)Howmanybutterfliesineachgroup?(3)Writedownall.(1)(2)(8butterfliesineachgroup)(3)orDecimation-in-TimeFFTAlgorithm(DITFFT)234.In-PlaceComputation(同址計算或原位計算)Advantagesofin-placecomputation：Weneedn’ttoopenanothermemorytostoretheoutputofeachstage,becausetheformerdatawewillnotuseagaininlatercomputation.

savingintheoverallmemoryunitsWN

l-1Decimation-in-TimeFFTAlgorithm(DITFFT)245.Orderofinputsequencex[n]Infigure11.12,orderofinputsequenceis:

mn000(0)000(0)001(1)100(4)010(2)010(2)011(3)110(6)100(4)001(1)101(5)101(5)110(6)011(3)111(7)111(7)Decimation-in-TimeFFTAlgorithm(DITFFT)25Decimation-in-TimeFFTAlgorithm(DITFFT)26DIT-FFTflowgraphforinputinbit-reversedandoutputinnormalorder.x[0]x[4]x[2]x[6]x[1]x[5]x[3]x[7]WN0WN0WN0WN0-1-1-1-1WN2WN0WN2-1-1WN0-1-1X[1]X[2]X[3]X[4]X[5]X[0]X[6]X[7]WN0WN1WN2WN3-1-1-1-1Decimation-in-TimeFFTAlgorithm(DITFFT)276.Alternativeform

DIT-FFTflowgraphforinputinnormalorderandoutputinbit-reversedorder（順入倒出）in-placecomputationWN0WN0WN0WN0WN0WN2WN2WN0WN2WN1WN3x[0]x[1]x[2]x[3]x[4]x[5]x[6]x[7]X[0]X[4]X[2]X[6]X[1]X[5]X[3]X[7]-1-1-1WN0-1-1-1-1-1-1-1-1-1Decimation-in-TimeFFTAlgorithm(DITFFT)28Decimation-in-FrequencyFFTAlgorithm(DIFFFT)1.AlgorithmprincipleSuppose:N=2υeveninteger29Decimation-in-FrequencyFFTAlgorithm(DIFFFT)30Letx0[n]=x[n]+x[n+N/2],x1[n]=(x[n]-x[n+N/2])Decimation-in-FrequencyFFTAlgorithm(DIFFFT)31Theflowgraphisshownbelow(Fig.11.15):N/2-pointDFTN/2-pointDFTX[2]X[4]X[6]X[1]X[3]X[0]WN0WN1WN2WN3X[7]X[5]x[0]x[1]x[2]x[3]x[4]x[5]x[6]x[7]x0[0]-1-1-1-1Fig.11.15(N=8)x0[1]x0[2]x0[3]x1[0]x1[1]x1[2]x1[3]Decimation-in-FrequencyFFTAlgorithm(DIFFFT)32x[4]x[1]x[2]x[3]x[5]x[0]x[6]x[7]-1-1-1-1N/4-pointDFTX[0]X[4]N/4-pointDFTX[2]X[6]N/4-pointDFTX[1]X[5]N/4-pointDFTX[3]X[7]WN0WN0WN2WN2WN1WN2WN3WN0-1-1-1-1Decimation-in-FrequencyFFTAlgorithm(DIFFFT)33The2-pointDFT:-1Xr-1[p]Xr-1[q]Xr[p]Xr[q]WN0=1x[0]x[1]X[1]X[0]Nowwegivethewholeflowgraph,seeFig.11.16Decimation-in-FrequencyFFTAlgorithm(DIFFFT)34WN0WN0WN0WN0WN0WN2WN2X[0]X[4]X[2]X[6]X[1]X[5]X[3]X[7]-1-1-1WN0-1WN0WN1WN2WN3-1-1-1-1x[0]x[1]x[2]x[3]x[4]x[5]x[6]x[7]-1-1-1-1Figure11.16DIF-FFTflowgraphforinputinnormalorderandoutputinbit-reversedorder.in-placecomputation

Decimation-in-FrequencyFFTAlgorithm(DIFFFT)35complexmultiplication:times

complexadditions:timesCompareFig.11.16toFig.11.12,wemayobtainthefollowingconclusion:Twoflowgraphsarejusttransposedeachother.2.IterativeformulasXv[i]=Xv-1[i]+Xv-1[i+dm]Xv[i+dm]=(Xv-1[i]-Xv-1[i+dm])WNl-1Xv-1[i]Xv-1[i+dm]Xv[i]Xv[i+dm]numberofgroupforeachstageDecimation-in-FrequencyFFTAlgorithm(DIFFFT)363.AlternativeformWN0WN0WN0WN0WN0WN2WN2WN0WN2WN1WN3X[0]X[1]X[2]X[3]X[4]X[5]X[6]X[7]x[0]x[4]x[2]x[6]x[1]x[5]x[3]x[7]-1-1-1WN0-1-1-1-1-1-1-1-1-1Figure9.22DIF-FFTflowgraphforinputinbit-reversedorderandoutputinnormalorder.

in-placecomputationDecimation-in-FrequencyFFTAlgorithm(DIFFFT)37Comparisonoffourflowgraphs:1.Fourflowgraphshavesamenumberofcomplexmultiplicationsandcomplexadditions.2.Fplexmultiplications:complexadditions:3.DIT-FFTandDIF-FFTaretransposedeachother.4.Fourflowgraphsneedallsortingorder.5.DIT-FFTandDIF-FFThavedifferentiterativeformulas.Decimation-in-FrequencyFFTAlgorithm(DIFFFT)3811.1.3InverseDFTComputationAnFFTalgorithmforcomputingtheDFTsamplescanalsebeusedtocalculateefficientlytheinverseDFT(IDFT)(11.29)(11.30)(11.31)39InverseDFTcomputationisshownbelow:(11.31)11.1.3InverseDFTComputation4011.4SlidingDiscreteFourierTransformIfNisthelengthofthesubset,wecomputetheN-pointDFTofthefinite-lengthsegment,{x[n],x[n-1],…,x[n-N+1]},insidealength-Nslidingwindow.TheDFTcomputationisrepeatedforeachincreasingvalueofnbyadvancingthewindowonesampleforeachcomputation.slidingdiscreteFouriertransformorrunningdiscreteFouriertransform

ToindicatethetimedependencyoftheDFTsamples,wedenotethek-thDFTsampleattimeinstantnasSk[n].(11.58)41(11.58)11.4SlidingDiscreteFourierTransform42Thesystemfunctionis(11.60)Figure11.2111.4SlidingDiscreteFourierTransform4311.5DFTComputationOveraNarrowFrequencyBandInapplicationsrequiringthecomputationoftheDFTsamplesoveraspecifiedrange.Forverylargelength,thecostofcomputingallDFTsamplesmaybeprohibitivelyhigh.11.5.1ZoomFFTThezoomFFTcanbeusedtocomputethesamplesofanN-pointDFTX[k]ofalength-Nsequencex[n]inasmallrangeofvaluesofthefrequencyindexk,,whereAssume:N=KRLet4411.5.1ZoomFFT

isbasicallyther-thsub-sequenceoflength-kobtainedbydown-samplingx[n]byafactorR.(11.61)where(11.62)Let

then

(11.63)45(11.63)where(11.64)11.5.1ZoomFFT4611.5.2ChirpFourierTransform(CFT)1.Algorithmprinciple:Letx[n]N-pointsequence,X(e

jω)Fouriertransformofx[n].ConsidertheevaluationofK

samplesofX(e

jω)thatareequallyspacedinangleontheunitcircle.Re(z)jIm(z)unitcircleω0(K-1)ΔωFigure11.22Δω1ωk=ω0+kΔω,

k=0,1,…,K-1(11.69)where:

ω0thestartfrequency

Δωthefrequencyincrement(canbechosenarbitrarily)47Re(z)jIm(z)unitcircleω0(K-1)ΔωFigure11.22Δω1ωk=ω0+k(Δω),

k=0,1,…,K-1(11.69)Ifweletω0=0,andM=NandΔω=2π/N,wecangetDFT.then11.5.2ChirpFourierTransform(CFT)48Letnandkreplacedbyeachother,wegetaveryfamiliarform:11.5.2ChirpFourierTransform(CFT)49

×

×

X(e

jωn)x[n]u[n]Figure11.2311.5.2ChirpFourierTransform(CFT)502.StepstorealizeCFT:Accordingtoω0and(Δω),toobtainthesequence:(2)Toobtaintheoutputofthefilterwithimpulseresponse(3)ToobtaintheoutputofsystemFig.(11.23)bymultiplication