FFT快速傅里葉變換(蝶形算法)詳解.ppt
《FFT快速傅里葉變換(蝶形算法)詳解.ppt》由會(huì)員分享,可在線閱讀,更多相關(guān)《FFT快速傅里葉變換(蝶形算法)詳解.ppt(53頁珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
第五章 快速傅里葉變換,2,本章目錄,直接計(jì)算DFT的問題及改進(jìn)的途徑,按時(shí)間抽取的基2-FFT算法,按頻率抽取的基2-FFT算法,快速傅里葉逆變換(IFFT)算法,Matlab實(shí)現(xiàn),3,5.1 引言,DFT在實(shí)際應(yīng)用中很重要: 可以計(jì)算信號(hào)的頻譜、功率譜和線性卷積等。 直接按DFT變換進(jìn)行計(jì)算,當(dāng)序列長(zhǎng)度N很大時(shí),計(jì)算量非常大,所需時(shí)間會(huì)很長(zhǎng)。 FFT并不是一種與DFT不同的變換,而是DFT的一種快速計(jì)算的算法。,,4,5.2 直接計(jì)算DFT的問題及改進(jìn)的途徑,DFT的運(yùn)算量,,設(shè)復(fù)序列x(n) 長(zhǎng)度為N點(diǎn),其DFT為,k=0,,…,N-1,(1)計(jì)算一個(gè)X(k) 值的運(yùn)算量,復(fù)數(shù)乘法次數(shù):,N,復(fù)數(shù)加法次數(shù):,N-1,5,5.2.1 DFT的運(yùn)算量,(2)計(jì)算全部N個(gè)X(k) 值的運(yùn)算量,復(fù)數(shù)乘法次數(shù):,N2,復(fù)數(shù)加法次數(shù):,N(N-1),(3)對(duì)應(yīng)的實(shí)數(shù)運(yùn)算量,,6,,一次復(fù)數(shù)乘法:,4次實(shí)數(shù)乘法,2次實(shí)數(shù)加法,+,一個(gè)X(k) :,4N次實(shí)數(shù)乘法,+,2N+2(N-1)= 2(2N-1)次實(shí)數(shù)加法,所以,整個(gè)N點(diǎn)DFT運(yùn)算共需要:,N×2(2N-1)= 2N(2N-1),實(shí)數(shù)乘法次數(shù):,4 N2,實(shí)數(shù)加法次數(shù):,,7,DFT運(yùn)算量的結(jié)論,,N點(diǎn)DFT的復(fù)數(shù)乘法次數(shù)舉例,結(jié)論:當(dāng)N很大時(shí),其運(yùn)算量很大,對(duì)實(shí)時(shí)性很強(qiáng)的信號(hào)處理來說,要求計(jì)算速度快,因此需要改進(jìn)DFT的計(jì)算方法,以大大減少運(yùn)算次數(shù)。,,8,,5.2.2 減少運(yùn)算工作量的途徑,主要原理是利用系數(shù) 的以下特性對(duì)DFT進(jìn)行分解:,(1)對(duì)稱性,(2)周期性,(3)可約性,另外,,,9,5.3 按時(shí)間抽取的基2-FFT算法,算法原理 按時(shí)間抽取基-2FFT算法與直接計(jì)算DFT運(yùn)算量的比較 按時(shí)間抽取的FFT算法的特點(diǎn) 按時(shí)間抽取FFT算法的其它形式流程圖,,10,5.3.1 算法原理,設(shè)N=2L,將x(n)按 n 的奇偶分為兩組:,,r =0,1,…,,則,,11,,式中,X1(k)和X2(k)分別是x1(n)和x2(n)的N/2的DFT。,另外,式中k的取值范圍是:0,1, …,N/2-1 。,,12,,,因此, 只能計(jì)算出X(k)的前一半值。,后一半X(k) 值, N/2 , N/2 +1, …,N ?,利用,可得到,同理可得,,13,,考慮到,因此可得后半部分X(k),及前半部分X(k),k=0,1, …,N/2-1,k=0,1, …,N/2-1,,14,蝶形運(yùn)算,,,蝶形運(yùn)算式,蝶形運(yùn)算信號(hào)流圖符號(hào),因此,只要求出2個(gè)N/2點(diǎn)的DFT,即X1(k)和X2(k),再經(jīng)過蝶形運(yùn)算就可求出全部X(k)的值,運(yùn)算量大大減少。,,15,以8點(diǎn)為例第一次按奇偶分解,以N=8為例,分解為2個(gè)4點(diǎn)的DFT,然后做8/2=4次蝶形運(yùn)算即可求出所有8點(diǎn)X(k)的值。,,16,蝶形運(yùn)算量比較,復(fù)數(shù)乘法次數(shù):,N2,復(fù)數(shù)加法次數(shù):,N(N-1),復(fù)數(shù)乘法次數(shù):,2*(N/2)2+N/2=N2/2+N/2,復(fù)數(shù)加法次數(shù):,2*(N/2)(N/2-1)+2*N/2=N2/2,N點(diǎn)DFT的運(yùn)算量,分解一次后所需的運(yùn)算量=2個(gè)N/2的DFT+N/2蝶形:,因此通過一次分解后,運(yùn)算工作量減少了差不多一半。,,17,進(jìn)一步按奇偶分解,由于N=2L,因而N/2仍是偶數(shù) ,可以進(jìn)一步把每個(gè)N/2點(diǎn) 子序列再按其奇偶部分分解為兩個(gè)N/4點(diǎn)的子序列。,以N/2點(diǎn)序列x1(r)為例,則有,,k=0,1,…,,,18,,且,k=0,1,…,,由此可見,一個(gè)N/2點(diǎn)DFT可分解成兩個(gè)N/4點(diǎn)DFT。,同理,也可對(duì)x2(n)進(jìn)行同樣的分解,求出X2(k)。,,19,以8點(diǎn)為例第二次按奇偶分解,,20,算法原理,對(duì)此例N=8,最后剩下的是4個(gè)N/4= 2點(diǎn)的DFT,2點(diǎn)DFT也可以由蝶形運(yùn)算來完成。以X3(k)為例。,k=0, 1,即,這說明,N=2M的DFT可全部由蝶形運(yùn)算來完成。,,21,以8點(diǎn)為例第三次按奇偶分解,N=8按時(shí)間抽取法FFT信號(hào)流圖,,22,5.3.2 按時(shí)間抽取基2-FFT算法與直接計(jì)算DFT運(yùn)算量的比較,由按時(shí)間抽取法FFT的信號(hào)流圖可知,當(dāng)N=2L時(shí),共有 級(jí) 蝶形運(yùn)算;每級(jí)都由 個(gè)蝶形運(yùn)算組成,而每個(gè)蝶形有 次復(fù)乘、 次復(fù)加,因此每級(jí)運(yùn)算都需 次復(fù)乘和 次復(fù)加。,L,N/2,N/2,1,2,N,,23,,這樣 級(jí)運(yùn)算總共需要:,L,復(fù)數(shù)乘法:,復(fù)數(shù)加法:,直接DFT算法運(yùn)算量,復(fù)數(shù)乘法:,復(fù)數(shù)加法:,N2,N(N-1),直接計(jì)算DFT與FFT算法的計(jì)算量之比為M,,24,FFT算法與直接DFT算法運(yùn)算量的比較,,,,,25,5.3.3 按時(shí)間抽取的FFT算法的特點(diǎn),序列的逆序排列 同址運(yùn)算(原位運(yùn)算) 蝶形運(yùn)算兩節(jié)點(diǎn)間的距離 的確定,,26,序列的逆序排列,由于 x(n) 被反復(fù)地按奇、偶分組,所以流圖輸入端的 排列不再是順序的,但仍有規(guī)律可循:,因?yàn)? N=2M ,,對(duì)于任意 n(0≤n ≤N-1),可以用M個(gè)二進(jìn)制碼表示為:,n 反復(fù)按奇、偶分解時(shí),即按二進(jìn)制碼的“0” “1” 分解。,序列的逆序排列,,27,倒位序的樹狀圖(N=8),,28,碼位的倒位序(N=8),,29,倒位序的變址處理(N=8),,30,同址運(yùn)算(原位運(yùn)算),某一列任何兩個(gè)節(jié)點(diǎn)k 和j 的節(jié)點(diǎn)變量進(jìn)行蝶形運(yùn)算后,得到結(jié)果為下一列k、j兩節(jié)點(diǎn)的節(jié)點(diǎn)變量,而和其他節(jié)點(diǎn)變量無關(guān)。這種原位運(yùn)算結(jié)構(gòu)可以節(jié)省存儲(chǔ)單元,降低設(shè)備成本。,運(yùn)算前,運(yùn)算后,例,同址運(yùn)算(原位運(yùn)算),,31,觀察原位運(yùn)算規(guī)律,,32,蝶形運(yùn)算兩節(jié)點(diǎn)間的距離,以N=8為例:,第一級(jí)蝶形,距離為:,第二級(jí)蝶形,距離為:,第三級(jí)蝶形,距離為:,規(guī)律:對(duì)于共L級(jí)的蝶形而言,其m級(jí)蝶形運(yùn)算的節(jié) 點(diǎn)間的距離為,1,2,4,蝶形運(yùn)算兩節(jié)點(diǎn)間的距離,,33,的確定,以N=8為例:,的確定,,34,5.4 按頻率抽取的基2-FFT算法,算法原理,再把輸出X(k)按k的奇偶分組,先把輸入按n的順序分成前后兩半,,設(shè)序列長(zhǎng)度為N=2L,L為整數(shù),前半子序列x(n),后半子序列,,,0≤n≤,0≤n≤,,35,5.4.1 算法原理,由DFT定義得,k=0,1, …,N,,36,,由于,所以,則,k=0,1, …,N,,37,,然后按k的奇偶可將X(k)分為兩部分,r=0,1, …,,則式,可轉(zhuǎn)化為,,,38,,令,n=0,1, …,,代入,r=0,1, …,,可得,為2個(gè)N/2點(diǎn)的DFT,合起來正好是N點(diǎn)X(k)的值。,,39,蝶形運(yùn)算,將,稱為蝶形運(yùn)算,與時(shí)間抽選基2FFT算法中的蝶形運(yùn)算符號(hào)略有不同。,,40,例 按頻率抽取(N=8),例 按頻率抽取,將N點(diǎn)DFT分解為兩個(gè)N/2點(diǎn)DFT的組合(N=8),,41,,與時(shí)間抽取法的推導(dǎo)過程一樣,由于 N=2L,N/2仍然是 一個(gè)偶數(shù),因而可以將每個(gè)N/2點(diǎn)DFT的輸出再分解為偶數(shù)組 與奇數(shù)組,這就將N/2點(diǎn)DFT進(jìn)一步分解為兩個(gè)N/4點(diǎn)DFT。,N=8,,42,5.4.2 頻率抽取法與時(shí)間抽取法的異同,頻率抽取法輸入是自然順序,輸出是倒位序的;時(shí)間抽取法正好相反。 頻率抽取法的基本蝶形與時(shí)間抽取法的基本蝶形有所不同。 頻率抽取法運(yùn)算量與時(shí)間抽取法相同。 頻率抽取法與時(shí)間抽取法的基本蝶形是互為轉(zhuǎn)置的。,,43,5.5 快速傅里葉逆變換(IFFT)算法,IDFT公式,DFT公式,比較可以看出,,,,IDFT多出,,M個(gè)1/2可分解到M級(jí)蝶形運(yùn)算中。,,44,例 頻率抽取IFFT流圖(N=8),,45,快速傅里葉逆變換另一種算法,,46,5.8 Matlab實(shí)現(xiàn),用FFT進(jìn)行譜分析的Matlab實(shí)現(xiàn) 用CZT進(jìn)行譜分析的Matlab實(shí)現(xiàn),在Matlab中使用的線性調(diào)頻z變換函數(shù)為czt,其調(diào)用格式為 X= czt(x, M, W, A) 其中,x是待變換的時(shí)域信號(hào)x(n),其長(zhǎng)度為N,M是變換的長(zhǎng)度,W確定變換的步長(zhǎng),A確定變換的起點(diǎn)。若M= N,A= 1,則CZT變成DFT。,,47,5.8.1 用FFT進(jìn)行譜分析的Matlab實(shí)現(xiàn),例5.1 設(shè)模擬信號(hào) ,以 t= 0.01n (n=0: N-1) 進(jìn)行取樣,試用fft函數(shù)對(duì)其做頻譜分析。N分別為:(1) N=45;(2) N=50;(3) N=55;(2) N=60。,程序清單如下,%計(jì)算N=45的FFT并繪出其幅頻曲線 N=45;n=0:N-1;t=0.01*n; q=n*2*pi/N; x=2*sin(4*pi*t)+5*cos(8*pi*t); y=fft(x,N); figure(1) subplot(2,2,1) plot(q,abs(y)) title('FFT N=45'),,48,例5.1程序清單,%計(jì)算N=50的FFT并繪出其幅頻曲線 N=50;n=0:N-1;t=0.01*n; q=n*2*pi/N; x=2*sin(4*pi*t)+5*cos(8*pi*t); y=fft(x,N); figure(1) subplot(2,2,2) plot(q,abs(y)) title('FFT N=50'),,49,,%計(jì)算N=55的FFT并繪出其幅頻曲線 N=55;n=0:N-1;t=0.01*n; q=n*2*pi/N; x=2*sin(4*pi*t)+5*cos(8*pi*t); y=fft(x,N); figure(1) subplot(2,2,3) plot(q,abs(y)) title('FFT N=55'),,50,,%計(jì)算N=60的FFT并繪出其幅頻曲線 N=60;n=0:N-1;t=0.01*n; q=n*2*pi/N; x=2*sin(4*pi*t)+5*cos(8*pi*t); y=fft(x,N); figure(1) subplot(2,2,4) plot(q,abs(y)) title('FFT N=60'),,51,例5.1程序運(yùn)行結(jié)果,從圖中可以看出,這幾種情況下均有較好的精度。,,52,例5.1程序運(yùn)行結(jié)果分析,分析:由t=0.01n進(jìn)行取樣可得,采樣頻率fs=100Hz。而連續(xù)信號(hào)的最高模擬角頻率為Ω=8 π ,由Ω=2 πf可得,最高頻率為8 π /2 π=4Hz。因此,滿足采樣定理的要求。 采樣序列為,即,為周期序列,周期N=50。,將程序中plot改為stem函數(shù),則可以更清楚地看出頻譜。,,53,例5.1修改程序運(yùn)行結(jié)果,,- 1.請(qǐng)仔細(xì)閱讀文檔,確保文檔完整性,對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔,不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請(qǐng)點(diǎn)此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
14.9 積分
下載 |
- 配套講稿:
如PPT文件的首頁顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- FFT 快速 傅里葉變換 蝶形 算法 詳解
鏈接地址:http://www.hcyjhs8.com/p-1841000.html