FFT快速傅里葉變換(蝶形算法)詳解.ppt

《FFT快速傅里葉變換(蝶形算法)詳解.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《FFT快速傅里葉變換(蝶形算法)詳解.ppt（53頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

第五章 快速傅里葉變換,2,本章目錄,直接計(jì)算DFT的問(wèn)題及改進(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的問(wèn)題及改進(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)處理來(lái)說(shuō)，要求計(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)過(guò)蝶形運(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蝶形：,因此通過(guò)一次分解后，運(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,…,,由此可見(jiàn)，一個(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)算來(lái)完成。以X3(k)為例。,k=0, 1,即,這說(shuō)明，N=2M的DFT可全部由蝶形運(yùn)算來(lái)完成。,,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,倒位序的樹(shù)狀圖（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)變量無(wú)關(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，合起來(lái)正好是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)過(guò)程一樣，由于 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é)果,,