版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
第四章
快速傅里葉變換
(FFT)主要內(nèi)容4.1引言4.2DFT的問(wèn)題及改進(jìn)途徑4.3時(shí)間抽?。―IT)的FFT算法4.4頻率抽取(DIF)的FFT算法4.5IDFT的FFT算法(FFT應(yīng)用一)§4.1引言FFT:
FastFourierTransform1965年,Cooley-Turky發(fā)表文章《機(jī)器計(jì)算傅里葉級(jí)數(shù)的一種算法》,提出FFT算法,解決DFT運(yùn)算量太大,在實(shí)際使用中受限制的問(wèn)題。FFT的應(yīng)用。頻譜分析、濾波器實(shí)現(xiàn)、實(shí)時(shí)信號(hào)處理等。典型應(yīng)用:信號(hào)頻譜計(jì)算、系統(tǒng)分析等
系統(tǒng)分析
頻譜分析與功率譜計(jì)算§4.2直接計(jì)算DFT的問(wèn)題及改進(jìn)途徑1、DFT與IDFT2、DFT與IDFT運(yùn)算特點(diǎn)復(fù)數(shù)乘法復(fù)數(shù)加法一個(gè)X(k)NN–
1N個(gè)X(k)(N點(diǎn)DFT)N2N(N–
1)同理:IDFT運(yùn)算量與DFT相同。實(shí)數(shù)乘法實(shí)數(shù)加法一次復(fù)乘42一次復(fù)加2一個(gè)X(k)4N2N+2(N–
1)=2(2N–
1)N個(gè)X(k)(N點(diǎn)DFT)4N22N(2N–
1)3、降低DFT運(yùn)算量的考慮FFT算法分類:時(shí)間抽選法
DIT:Decimation-In-Time頻率抽選法
DIF:Decimation-In-Frequency§4.3按時(shí)間抽?。―IT)的FFT算法(DecimationInTime)1、算法原理 設(shè)序列點(diǎn)數(shù)N=2L,L
為整數(shù)。若不滿足,則補(bǔ)零將序列x(n)按n的奇偶分成兩組:N為2的整數(shù)冪的FFT算法稱基-2FFT算法。
將N點(diǎn)DFT定義式分解為兩個(gè)長(zhǎng)度為N/2的DFT記:………(1)(這一步利用:)再利用周期性求X(k)的后半部分將上式表達(dá)的運(yùn)算用一個(gè)專用“蝶形”信流圖表示。用“蝶形結(jié)”表示上面運(yùn)算的分解: 分解后的運(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)算量減少了近一半進(jìn)一步分解由于,仍為偶數(shù),因此,兩個(gè)點(diǎn)DFT又可同樣進(jìn)一步分解為4個(gè)點(diǎn)的DFT。“蝶形”信流圖表示
N點(diǎn)DFT分解為四個(gè)N/4點(diǎn)的DFT這樣逐級(jí)分解,直到2點(diǎn)DFT當(dāng)N=8時(shí),即分解到X3(k),X4(k),X5(k),X6(k),k=0,1FFT運(yùn)算量與運(yùn)算特點(diǎn)
1.N=2L時(shí),共有L=log2N級(jí)運(yùn)算;每一級(jí)有N/2個(gè)蝶形結(jié)。2.計(jì)算量:每級(jí)N/2次復(fù)乘法,N次復(fù)加。(每蝶形只乘一次,加減各一次)。共有L*N/2=N/2log2N次復(fù)乘法;復(fù)加法L*N=Nlog2N次。與直接DFT定義式運(yùn)算量相比(倍數(shù))N2/(Nlog2N)
。當(dāng)N大時(shí),此倍數(shù)很大。比較DFT可以直觀看出,當(dāng)點(diǎn)數(shù)N越大時(shí),F(xiàn)FT的優(yōu)點(diǎn)更突出。按時(shí)間抽取FFT蝶形運(yùn)算特點(diǎn)
1、關(guān)于FFT運(yùn)算的混序與順序處理(位倒序處理)由于輸入序列按時(shí)間序位的奇偶抽取,故輸入序列是混序的,為此需要先進(jìn)行混序處理?;煨蛞?guī)律:
x(n)按n位置進(jìn)行碼位(二進(jìn)制)倒置規(guī)律輸入,而非自然排序,即得到混序排列。所以稱為位倒序處理。倒位序自然序0000000010041001010220101106301100114100101551010113611011177111倒位序例 計(jì)算,。計(jì)算 點(diǎn)FFT。用時(shí)間抽取輸入倒序算法,問(wèn)倒序前寄存器的數(shù)和倒序后的數(shù)據(jù)值?解:倒序前倒序 倒序?yàn)榈剐蚝驞ITFFT中最主要的蝶形運(yùn)算實(shí)現(xiàn)(1)參與蝶形運(yùn)算的兩類結(jié)點(diǎn)(信號(hào))間“距離”(碼地址)與其所處的第幾級(jí)蝶形有關(guān);第m級(jí)的“結(jié)距離”為
(即原位計(jì)算迭代)(2)每級(jí)迭形結(jié)構(gòu)為DIT算法的其他形式流圖只要保持各節(jié)點(diǎn)所連的支路及其傳輸系數(shù)不變,則不論節(jié)點(diǎn)位置怎樣排列所得流圖總是等效的。DIT算法的其他形式流圖輸入倒位序輸出自然序輸入自然序輸出倒位序輸入輸出均自然序相同幾何形狀輸入倒位序輸出自然序輸入自然序輸出倒位序參考P154-155時(shí)間抽取、輸入自然順序、輸出倒位序的FFT流圖
例用FFT算法處理一幅N×N點(diǎn)的二維圖像,如用每秒可做10萬(wàn)次復(fù)數(shù)乘法的計(jì)算機(jī),當(dāng)N=1024時(shí),問(wèn)需要多少時(shí)間(不考慮加法運(yùn)算時(shí)間)?解當(dāng)N=1024點(diǎn)時(shí),F(xiàn)FT算法處理一幅二維圖像所需復(fù)數(shù)乘法約為 次,僅為直接計(jì)算DFT所需時(shí)間的10萬(wàn)分之一。即原需要3000小時(shí),現(xiàn)在只需要2分鐘。
§4.4按頻率抽取(DIF)的FFT算法與DIT-FFT算法類似分解,但是抽取的是X(k)。即分解X(k)成奇數(shù)與偶數(shù)序號(hào)的兩個(gè)序列。設(shè):N=2L,L為整數(shù)。將X(k)按k的奇偶分組前,先將輸入x(n)按n的順序分成前后兩半:(DecimationInFrequency)一、算法原理下面討論按k的奇偶將X(k)分成兩部分:顯然:令:用蝶型結(jié)構(gòu)圖表示為: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/2→N/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)=X1(2)=X(4)X4(1)=X1(3)=X(6)按照以上思路繼續(xù)分解,即一個(gè)N/2的DFT分解成兩個(gè)N/4點(diǎn)DFT,直到只計(jì)算2點(diǎn)的DFT,這就是DIF-FFT算法。二、按頻率抽取FFT蝶形運(yùn)算特點(diǎn)1)原位計(jì)算-1L級(jí)蝶形運(yùn)算,每級(jí)N/2個(gè)蝶形,每個(gè)蝶形結(jié)構(gòu):
m表示第m級(jí)迭代,k,j表示數(shù)據(jù)所在的行數(shù)2)蝶形運(yùn)算對(duì)N=2L點(diǎn)FFT,輸入自然序,輸出倒位序,兩節(jié)點(diǎn)距離:2L-m=N/2m第m級(jí)運(yùn)算:三、DIT與DIF的異同基本蝶形不同DIT:先復(fù)乘后加減DIF:先加減后復(fù)乘運(yùn)算量相同DIT和DIF的基本蝶形互為轉(zhuǎn)置§4.5IDFT的FFT算法
(FFT應(yīng)用一)
溫馨提示
- 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ì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 胎盤(pán)EVs的基因編輯與治療策略-洞察分析
- 細(xì)胞療法在膝關(guān)節(jié)退變中的應(yīng)用研究-洞察分析
- 藝術(shù)品市場(chǎng)風(fēng)險(xiǎn)預(yù)警系統(tǒng)-洞察分析
- 因果推斷跨學(xué)科研究-洞察分析
- 網(wǎng)絡(luò)安全法規(guī)-洞察分析
- 醫(yī)藥泡沫包裝對(duì)藥品保護(hù)效果研究-洞察分析
- 水利工程智能化發(fā)展-洞察分析
- 穴位療法對(duì)更年期潮熱療效評(píng)估-洞察分析
- 休閑馬術(shù)運(yùn)動(dòng)市場(chǎng)潛力-洞察分析
- 天然成分飲料創(chuàng)新-洞察分析
- 地震和防震知識(shí)課件
- 冗余系統(tǒng)設(shè)計(jì)策略
- 國(guó)家住宅裝飾裝修工程施工規(guī)范
- 種子檢測(cè)報(bào)告
- 兗州煤田東灘煤礦240萬(wàn)ta新井設(shè)計(jì)
- 天津市部分區(qū)2023-2024學(xué)年九年級(jí)上學(xué)期化學(xué)期末試題
- 醫(yī)學(xué)外科的教學(xué)設(shè)計(jì)
- 濟(jì)南 公司章程范本
- AR技術(shù)在教育領(lǐng)域的應(yīng)用與課程設(shè)計(jì)
- 2019疏浚工程預(yù)算定額
- 笙的演奏技術(shù)與教學(xué)
評(píng)論
0/150
提交評(píng)論