版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
第4章快速傅立葉變換(FFT)4.1概述4.2時(shí)間抽取基2算法-DIT4.3頻率抽取基2算法-DIF4.1概述
解決耗時(shí)的乘法問題是將數(shù)字信號處理理論用于實(shí)際的關(guān)鍵問題。特別是30年前,計(jì)算機(jī)的速度相當(dāng)慢。因此,很多學(xué)者對解決DFT的快速計(jì)算問題產(chǎn)生了極大的興趣。CooleyJW,TukeyJW.AnalgorithmforthemachinecomputationofcomplexFourierseries.MathematicsofComputation,1965,pp297~301DSP的正式開端!FFT的思路:如何充分利用這些關(guān)系?四點(diǎn)DFT幾個(gè)乘法?4.2時(shí)間抽取基2FFT的算法——DIT(DecimationInTime)FFT的核心思想是:N點(diǎn)DFTN/2點(diǎn)
DFTN/4點(diǎn)
DFT2點(diǎn)
DFT
1個(gè)2個(gè)4個(gè)N/2個(gè)問題是如何分最有效?可以對時(shí)間變量分(DIT),也可對頻率變量分(DIF)令:分解后的運(yùn)算量:復(fù)數(shù)乘法復(fù)數(shù)加法一個(gè)N/2點(diǎn)DFT(N/2)2N/2(N/2–1)兩個(gè)N/2點(diǎn)DFTN2/2N(N/2–1)一個(gè)蝶形12N/2個(gè)蝶形N/2N總計(jì)運(yùn)算量減少了近一半
都是N/2點(diǎn)的DFT,它們各自又可分成N/4點(diǎn)的DFT,如此繼續(xù)分下去,直至兩點(diǎn)DFT。兩點(diǎn)DFT不需要乘法運(yùn)算:每一級有N/2個(gè)如下的“蝶形”單元:即:每一個(gè)蝶形單元僅需一個(gè)復(fù)數(shù)乘法,兩個(gè)復(fù)數(shù)加法。兩點(diǎn)構(gòu)成一個(gè)蝶形單元,并且這兩點(diǎn)不再參與別的蝶形單元的運(yùn)算。同址運(yùn)算。
所需運(yùn)算量:注意:因子的位置;輸入序列的順序--碼位倒置。碼位倒置倒位序自然序0000000010041001010220101106301100114100101551010113611011177111n0n1n2000110110011010000000010000110100102110011300110041011015011110671111117運(yùn)算量比較當(dāng)N=2M時(shí),共有M級蝶形,每級N/2個(gè)蝶形,每個(gè)蝶形有1次復(fù)數(shù)乘法2次復(fù)數(shù)加法。復(fù)數(shù)乘法:復(fù)數(shù)加法:比較DFT4.3頻率抽取基2FFT的算法——DIF(DecimationInFrequency)令:各是N/2點(diǎn)的
DFT則X(2r)和X(2r+1)分別是x1(n)和x2(n)的N/2點(diǎn)DFT,記為X1(k)和X2(k)x1(0)x1(1)-1x1(2)x1(3)-1x2(0)x2(1)-1x2(2)x2(3)-1N/2點(diǎn)DFTN/2點(diǎn)DFTx(0)x(7)x(1)x(2)x(3)x(4)x(5)x(6)X1(0)=X(0)X2(0)=X(1)X1(1)=X(2)X1(2)=X(4)X1(3)=X(6)X2(1)=X(3)X2(2)=X(5)X2(3)=X(7)N/2仍為偶數(shù),進(jìn)一步分解:N/2N/4x3(0)x3(1)-1-1x4(0)x4(1)N/4點(diǎn)DFTN/4點(diǎn)DFTx1(0)x1(1)x1(2)x1(3)X3(0)=X1(0)=X(0)X4(0)=X1(1)=X(2)X3(1)=X
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 應(yīng)急預(yù)案的應(yīng)對社會(huì)安全事件
- 現(xiàn)代農(nóng)業(yè)產(chǎn)業(yè)園資金籌措與投資方案
- 農(nóng)業(yè)行業(yè)市場拓展總結(jié)
- 物流行業(yè)客服實(shí)踐總結(jié)
- 二零二五版機(jī)場停車場租賃與旅客交通服務(wù)合同3篇
- 二零二五年度房地產(chǎn)企業(yè)委托招聘項(xiàng)目管理人員合同范本3篇
- 二零二五年度頁巖磚裝配式建筑材料購銷協(xié)議4篇
- 二零二五版室內(nèi)木門定制加工與安裝服務(wù)協(xié)議3篇
- 二零二五年度車輛抵押債務(wù)重組及還款安排合同3篇
- 二零二五年度鋼材電商平臺(tái)合作合同2篇
- 2025年方大萍安鋼鐵招聘筆試參考題庫含答案解析
- 2025年電力工程施工企業(yè)發(fā)展戰(zhàn)略和經(jīng)營計(jì)劃
- 2024東莞市勞動(dòng)局制定的勞動(dòng)合同范本
- 2024年大學(xué)本科課程教育心理學(xué)教案(全冊完整版)
- 中國血管通路專家共識解讀
- 《裝配式蒸壓加氣混凝土外墻板保溫系統(tǒng)構(gòu)造》中
- 2019版新人教版高中英語必修+選擇性必修共7冊詞匯表匯總(帶音標(biāo))
- 中層領(lǐng)導(dǎo)的高績效管理
- 閱讀理解特訓(xùn)卷-英語四年級上冊譯林版三起含答案
- 屋面及防水工程施工(第二版)PPT完整全套教學(xué)課件
- 2023年高一物理期末考試卷(人教版)
評論
0/150
提交評論