版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
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(同址計(jì)算或原位計(jì)算)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
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 水果供應(yīng)商購(gòu)銷(xiāo)合同示例
- 解除合同協(xié)議書(shū)模板
- 導(dǎo)師抄襲學(xué)生研究報(bào)告
- 對(duì)自己大學(xué)評(píng)價(jià)研究報(bào)告
- 對(duì)稱y型岔管課程設(shè)計(jì)
- 對(duì)外漢語(yǔ)的課程設(shè)計(jì)
- 對(duì)農(nóng)村產(chǎn)業(yè)發(fā)展研究報(bào)告
- 對(duì)于網(wǎng)課的研究報(bào)告
- 對(duì)于幼兒心理研究報(bào)告
- 賓館行業(yè)培訓(xùn)方案
- 少兒美術(shù)課件-《帶著月亮去散步》
- 《狼和鴨子》課件小學(xué)幼兒園兒童故事表演幻燈片背景有音樂(lè)
- 高二生物 選擇性必修 2特異性免疫(第1課時(shí)) 體液免疫(學(xué)案)
- 房地產(chǎn)項(xiàng)目現(xiàn)金流量及投資收益測(cè)算表
- 建筑垃圾消納臺(tái)賬
- 放射工作人員申請(qǐng)表及基本情況一覽表
- DB33-1092-2021《綠色建筑設(shè)計(jì)標(biāo)準(zhǔn)》
- 《伯牙善鼓琴》說(shuō)課稿完整版課件
- T-CCES 29-2022 槽式預(yù)埋件系統(tǒng)設(shè)計(jì)標(biāo)準(zhǔn)
- 四年級(jí)數(shù)學(xué)上冊(cè)課件-4 解決問(wèn)題-價(jià)格問(wèn)題29-人教版(共20張PPT)
- 建筑工程計(jì)量與計(jì)價(jià)全套課件
評(píng)論
0/150
提交評(píng)論