快速傅里葉變換FFT.ppt
《快速傅里葉變換FFT.ppt》由會員分享,可在線閱讀,更多相關(guān)《快速傅里葉變換FFT.ppt(37頁珍藏版)》請在裝配圖網(wǎng)上搜索。
本章主要內(nèi)容引言基2FFT算法進一步減少運算量的措施,第4章快速傅里葉變換(FFT),DFT是信號分析與處理中的一種重要變換。但直接計算DFT的計算量與變換區(qū)間長度N的平方成正比,當(dāng)N較大時,計算量太大,直接用DFT算法進行譜分析和信號的實時處理是不切實際的。1965年發(fā)現(xiàn)了DFT的一種快速算法,使DFT的運算效率提高1-2個數(shù)量級,為數(shù)字信號處理技術(shù)應(yīng)用于各種信號的實時處理創(chuàng)造了條件,推動了數(shù)字處理技術(shù)的發(fā)展。1984年,提出了分裂基快速算法,使運算效率進一步提高;,4.1引言,4.2.1直接計算DFT的特點及減少運算量的基本途徑直接計算DFT長度為N的有限長序列x(n)的DFT為:2、減少運算量的思路和方法思路:N點DFT的復(fù)乘次數(shù)等于N2。把N點DFT分解為幾個較短的DFT,可使乘法次數(shù)大大減少。另外,旋轉(zhuǎn)因子WmN具有周期性和對稱性。,4.2基2FFT算法,考慮x(n)為復(fù)數(shù)序列的一般情況,對某一個k值,直接按上式計算X(k)值需要N次復(fù)數(shù)乘法、(N-1)次復(fù)數(shù)加法。,方法:分解N為較小值:把序列分解為幾個較短的序列,分別計算其DFT值,可使乘法次數(shù)大大減少;利用旋轉(zhuǎn)因子WNk的周期性、對稱性進行合并、歸類處理,以減少DFT的運算次數(shù)。周期性:對稱性:3、FFT算法思想不斷地把長序列的DFT分解成幾個短序列的DFT,并利用旋轉(zhuǎn)因子的周期性和對稱性來減少DFT的運算次數(shù)。,4.2基2FFT算法,4.2.2時域抽取法基2FFT基本原理FFT算法基本上分為兩大類:時域抽取法FFT(簡稱DIT-FFT)和頻域抽取法FFT(簡稱DIF―FFT)。1、時域抽取法FFT的算法思想:將序列x(n)按n為奇、偶數(shù)分為x1(n)、x2(n)兩組序列;用2個N/2點DFT來完成一個N點DFT的計算。設(shè)序列x(n)的長度為N,且滿足:(1)按n的奇偶把x(n)分解為兩個N/2點的子序列,4.2基2FFT算法,為自然數(shù),{,(2)用N/2點X1(k)和X2(k)表示序列x(n)的N點DFTX(k),4.2基2FFT算法,,注意:這里的k的取值范圍為0,1,…,N-1,由于X1(k)和X2(k)均以N/2為周期,且,X(k)又可表示為:對上式的運算用下圖所示的流圖符號來表示,4.2基2FFT算法,這樣將N點DFT分解為兩個N/2點的DFT,完成一個蝶形運算需要一次復(fù)數(shù)乘和兩次復(fù)數(shù)加法運算,經(jīng)過一次分解后,共需要復(fù)數(shù)乘和復(fù)數(shù)加的次數(shù)為2(N/2)2+N/2和N2/2,{,4.2基2FFT算法,{,N=8點的DIT-2FFT(時域抽取圖)一次分解圖,(3)第二次分解:將x1(r)按r取奇、偶可分解成2個長度為N/4的子序列x3(l)=x1(2l)、x4(l)=x1(2l+1),根據(jù)上面推導(dǎo)可得:X1(k)=X3(k)+WN/2k?X4(k),k=0,1,…,N/2-1將x2(r)按r取奇、偶可分解成2個長N/4的子序列x5(l)=x2(2l),l=0,1,…,N/4x6(l)=x2(2l+1);同理得,4.2基2FFT算法,l=0,1,…,N/4-1;,4.2基2FFT算法,N=8點DFT的二次時域抽取分解圖,k=0,1,…,N/4-1;,再次分解,對N=8點,可分解三次。,4.2基2FFT算法,4.2基2FFT算法,4.2.3DIT―FFT算法與直接計算DFT運算量的比較1、直接DFT運算N點運算:復(fù)數(shù)乘次數(shù):NN復(fù)數(shù)加次數(shù):N(N-1)2、用DIT-FFT作N點運算:復(fù)數(shù)乘次數(shù):MN/2=N/2log2N;復(fù)加次數(shù):2N/2M=Nlog2N??梢奆FT大大減少了運算次數(shù),提高了運算速度。,4.2基2FFT算法,整個運算流圖中有M級蝶形,每一級運算流圖中有N/2個蝶形,每個蝶形需一次復(fù)乘和兩次復(fù)數(shù)加運算。,4.2.4DIT―FFT的運算規(guī)律及編程思想1.原位計算序列長為N=2M點的FFT,有M級蝶形,每級有N/2個蝶形運算。同一級中,每個蝶形的兩個輸入數(shù)據(jù)只對本蝶形有用,每個蝶形的輸入、輸出數(shù)據(jù)節(jié)點在用一條水平線上。這樣,當(dāng)計算完一個蝶形后,所得的輸出數(shù)據(jù)可立即存入原輸入數(shù)據(jù)所占用的存儲單元。經(jīng)過M級運算后,原來存放輸入序列數(shù)據(jù)的N個存儲單元中可依次存放X(k)的N個值。原位計算:利用同一存儲單元存儲蝶形計算輸入、輸出數(shù)據(jù)的方法。優(yōu)點:節(jié)約存儲空間、降低設(shè)備成本。,4.2基2FFT算法,2.旋轉(zhuǎn)因子的變化規(guī)律N點DIT―FFT運算流圖中,每個蝶形都要乘以旋轉(zhuǎn)因子WpN,p稱為旋轉(zhuǎn)因子的指數(shù)。N=8=23時各級的旋轉(zhuǎn)因子第一級:L=1,有1個旋轉(zhuǎn)因子:WNp=WN/4J=W2LJJ=0第二級:L=2,有2個旋轉(zhuǎn)因子:WNp=WN/2J=W2LJJ=0,1第三級:L=3,有4個旋轉(zhuǎn)因子:WNp=WNJ=W2LJJ=0,1,2,3對于N=2M的一般情況,第L級共有2L-1個不同的旋轉(zhuǎn)因子:WNp=W2LJJ=0,1,2,…,2L-1-12L=2L?M?2M=N?2L?M故:按照上面兩式可以確定第L級運算的旋轉(zhuǎn)因子。,4.2基2FFT算法,p=J2M-L,J=0,1,2,…,2L-1-1,3、同一級中,同一旋轉(zhuǎn)因子對應(yīng)蝶形數(shù)目第L級FFT運算中,同一旋轉(zhuǎn)因子用在2M-L個蝶形中;4、同一級中,蝶形運算使用相同旋轉(zhuǎn)因子之間相隔的“距離”第L級中,蝶距:D=2L。5、同一蝶形運算兩輸入數(shù)據(jù)的距離在輸入倒序,輸出原序的FFT變換中,第L級的每一個蝶形的2個輸入數(shù)據(jù)相距:B=2L-1。6、碼位顛倒輸入序列x(n)經(jīng)過M級時域奇、偶抽選后,輸出序列X(k)的順序和輸入序列的順序關(guān)系為倒位關(guān)系。,4.2基2FFT算法,7、蝶形運算的規(guī)律序列經(jīng)過時域抽選后,存入數(shù)組中,如果蝶形運算的兩個輸入數(shù)據(jù)相距B個點,應(yīng)用原位計算,蝶形運算可表示成如下形式:,4.2基2FFT算法,8、DIT-FFT程序框圖根據(jù)DIT-FFT原理和過程,DIT-FFT的完整程序框圖包括以下幾部分:(1)倒序:輸入自然順序序列x(n),根據(jù)倒序規(guī)律,進行倒序處理;(2)循環(huán)層1:確定運算的級數(shù),L=1?M(N=2M);確定一蝶形兩輸入數(shù)據(jù)距離B=2L-1(3)循環(huán)層2:確定L級的(B=)2L-1個旋轉(zhuǎn)因子;旋轉(zhuǎn)因子指數(shù)p=2M-LJ,J=0?B-1;(4)循環(huán)層3:對于同一旋轉(zhuǎn)因子,用于同一級2M-L個蝶形運算中:k的取值從J到N-1,步長為2L(使用同一旋轉(zhuǎn)因子的蝶形相距的距離)(5)完成一個蝶形運算。,4.2基2FFT算法,9.序列的倒序N=2M,用M位二進制數(shù)(nM-1nM-2…n1n0)2表示序列的序號n.M次偶奇時域抽選過程為:對最低位按0、1分為偶、奇兩組,次低位也按0、1分組,依此類推,M次分解后形成倒序圖為:,4.2基2FFT算法,二進制數(shù)(N=8)分解倒序圖,可見,只要將順序數(shù)的二進制位倒置可得到對應(yīng)的二進制倒序值。,(n2n1n0)2,思考題:已知N=16點,在DIT-FFT運算中,序數(shù)為2的二進制經(jīng)數(shù)倒序后為多少?,4.2基2FFT算法,順序數(shù)增加1,是在順序數(shù)的二進制數(shù)的最低位加1,向左進位,到序數(shù)是在M位二進制數(shù)的最高位加1,向右進位,(0010->0100),順序和倒序二進制數(shù)對照表,N=2M,用M位二進制數(shù)表示,則從左至?右的十進制權(quán)值為:N/2、N/4、N/8,…、2,1對倒序數(shù)J,其下一個序數(shù)是在該序數(shù)J的二進制首位碼加1,相當(dāng)于十進制運算J+N/2。計算機上倒序數(shù)的實現(xiàn)過程為:,4.2基2FFT算法,倒序數(shù)的十進制運算規(guī)律,倒序程序框圖為了實現(xiàn)原位運算,以節(jié)約存貯空間,提高運算速率。在倒序數(shù)J形成后,需將原存儲器中存放的輸入序列重新排列。下面先分析N=8點的倒序規(guī)律。,4.2基2FFT算法,,,,,,,,,輸入序列,數(shù)組,分析上圖N=8點倒序規(guī)律,順序數(shù)I與倒序數(shù)J存在關(guān)系:I=J時,不交換;IJ時,不交換,直接更新序數(shù)值;,I,J,x(0),x(2),x(5),x(7),計算倒序值,交換數(shù)組中的數(shù)據(jù),不交換數(shù)據(jù),避免再次調(diào)換前面調(diào)換過的一對數(shù)據(jù),計算下一個倒數(shù)值。,4.2.5頻域抽取法FFT(DIF―FFT)在基2快速算法中,頻域抽取法FFT也是一種常用的快速算法。1、算法思想和運算過程設(shè)序列x(n)長度為N=2M,將序列x(n)前后對半分為x1(n)、x2(n)兩組序列,用2個N/2點DFT來完成一個N點DFT的計算。,4.2基2FFT算法,n,4.2基2FFT算法,將X(k)分解成偶數(shù)組與奇數(shù)組,當(dāng)k取偶數(shù)(k=2r,r=0,1,…,N/2-1)時當(dāng)k取奇數(shù)(k=2r+1,r=0,1,…,N/2-1)時:將x1(n)和x2(n)分別代入上式,可得,,x2(n),,,{,表明:X(k)按奇偶k值分為兩組:偶數(shù)組是x1(n)的N/2點DFT奇數(shù)組是x2(n)的N/2點DFT,n=0,1,…,N/2-1,那么對序列x1(n)、x2(n)和x(n)可用蝶形運算符號表示,4.2基2FFT算法,N=8時第1次分解的運算流圖,,,N=2M,N/2仍是偶數(shù),繼續(xù)將N/2點進行分解。將輸入序列x1(n)、x2(n)分別按前、后對半分解成4個長N/4的子序列,其n=0,1,…,N/4-1,4.2基2FFT算法,經(jīng)過三次分解后,DIF―FFT運算流圖(N=8)為:,4.2基2FFT算法,2、DIF-FFT運算規(guī)律DIF-FFT算法也可采用原位計算;N=2M時,共有M級運算,每級共有N/2個蝶形,DIT與DIF算法的運算次數(shù)相同。DIT與DIF不同的是:DIF-FFT算法輸入序列為自然序列,輸出為倒序序列。因此,在M級運算完成后,需對輸出數(shù)據(jù)進行倒序才能得到自然順序的X(k)。蝶形運算符號不同:DIT-FFT蝶形是先相乘,后加/減;而DIF-FFT蝶形是先加/減,后相乘。,4.2基2FFT算法,,3、其它形式的DIT-FFT運算流圖通過改變輸入/輸出節(jié)點,中間節(jié)點的排列順序,可以得到不同變形的FFT運算流圖。因此,前面介紹的DIT-FFT和DIF-FFT運算流圖都不是唯一的。,4.2基2FFT算法,用同樣的方法可得DIT-FFT的另外一種變形運算流圖,輸入和輸出均為順序排列,但不能采用原位計算。,4.2基2FFT算法,DIT―FFT的一種變形運算流圖,4.2.6IDFT的高效算法1.DFT和IDFT的公式比較上述FFT算法流圖也可以用于離散傅里葉逆變換IDFT根據(jù)運算公式可以看出,只需將DFT的系數(shù)WNkn變?yōu)閃N-kn,最后結(jié)果乘以1/N,就是IDFT的運算公式。,第4章快速傅里葉變換(FFT),[X(k)],n,2.用FFT流圖實現(xiàn)IDFT快速算法將DIT-FFT或DIF-FFT蝶形運算流圖中旋轉(zhuǎn)因子WNp改為WN-p在IDFT快速算法的最后結(jié)果輸出前,乘以1/N常數(shù);如要防止溢出,可在每一級運算中,輸出支路分別乘以1/2,實現(xiàn)系數(shù)分級分擔(dān)。在IDFT快速算法中,輸入序列為X(k),而輸出序列為x(n)。節(jié)點對應(yīng)關(guān)系:DIT-FFT對應(yīng)DIF-IFFTDIF-FFT對應(yīng)DIT-IFFT,第4章快速傅里葉變換(FFT),第4章快速傅里葉變換(FFT),DIT―IFFT運算流圖,第4章快速傅里葉變換(FFT),DIT―IFFT運算流圖(防止溢出),3、直接調(diào)用FFT程序?qū)崿F(xiàn)IFFT的計算對FFT流程作一些修改后,調(diào)用FFT程序?qū)崿F(xiàn)IFFT的快速計算。具體實現(xiàn)方法:先將X(k)取共軛,得到X*(k);直接調(diào)用FFT子程序計算出DFT[X*(k)]的值;對輸出序列取共軛,并乘以1/N常數(shù)。雖然2次用了取共軛運算,但可以和FFT共用一個子程序,實現(xiàn)方便。,第4章快速傅里葉變換(FFT),本章作業(yè)本章第一次作業(yè)習(xí)題1習(xí)題2本章第二次作業(yè)習(xí)題3習(xí)題4,- 1.請仔細(xì)閱讀文檔,確保文檔完整性,對于不預(yù)覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔,不會出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請點此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
9.9 積分
下載 |
- 配套講稿:
如PPT文件的首頁顯示word圖標(biāo),表示該PPT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國旗、國徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計者僅對作品中獨創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 快速 傅里葉變換 FFT
鏈接地址:http://www.3dchina-expo.com/p-3405556.html