第4章快速傅里葉變換（FFT）

1、 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 4.1 引引 言言DFT是數(shù)字信號(hào)分析與處理中的一種重要變換。但是數(shù)字信號(hào)分析與處理中的一種重要變換。但直接計(jì)算直接計(jì)算DFT，當(dāng)，當(dāng)N較大時(shí)，計(jì)算量太大，所以在快速較大時(shí)，計(jì)算量太大，所以在快速傅里葉變換傅里葉變換FFT(Fast Fourier Transform)出現(xiàn)以前，直出現(xiàn)以前，直接用接用DFT算法進(jìn)行譜分析和信號(hào)的實(shí)時(shí)處理是不切實(shí)際算法進(jìn)行譜分析和信號(hào)的實(shí)時(shí)處理是不切實(shí)際的。直到的。直到1965年提出年提出DFT的一種快速算法以后，情況才的一種快速算法以后，情況才發(fā)生了根本的變化。發(fā)生了根本的變化。 自從自從1965年庫(kù)利和圖

2、基在年庫(kù)利和圖基在計(jì)算數(shù)學(xué)計(jì)算數(shù)學(xué)雜志上發(fā)雜志上發(fā)表了著名的表了著名的機(jī)器計(jì)算傅里葉級(jí)數(shù)的一種算法機(jī)器計(jì)算傅里葉級(jí)數(shù)的一種算法論文論文后，桑德后，桑德圖基等快速算法相繼出現(xiàn)，又經(jīng)人們進(jìn)行圖基等快速算法相繼出現(xiàn)，又經(jīng)人們進(jìn)行改進(jìn)，很快形成一套高效計(jì)算方法，這就是現(xiàn)在的改進(jìn)，很快形成一套高效計(jì)算方法，這就是現(xiàn)在的快快速傅里葉變換（速傅里葉變換（FFT）。）。這種算法使這種算法使DFT的運(yùn)算效率提高了的運(yùn)算效率提高了1 2個(gè)數(shù)量級(jí)，個(gè)數(shù)量級(jí)，為數(shù)字信號(hào)處理技術(shù)應(yīng)用于各種信號(hào)的實(shí)時(shí)處理創(chuàng)造為數(shù)字信號(hào)處理技術(shù)應(yīng)用于各種信號(hào)的實(shí)時(shí)處理創(chuàng)造了條件，大大推動(dòng)了數(shù)字信號(hào)處理技術(shù)的發(fā)展。了條件，大大推動(dòng)了數(shù)字信號(hào)

3、處理技術(shù)的發(fā)展。 人類的求知欲和科學(xué)的發(fā)展是永無(wú)止境的。多年來(lái)，人類的求知欲和科學(xué)的發(fā)展是永無(wú)止境的。多年來(lái)，人們繼續(xù)尋求更快、更靈活的好算法。人們繼續(xù)尋求更快、更靈活的好算法。1984年，法國(guó)的年，法國(guó)的杜哈梅爾杜哈梅爾(P. Dohamel)和霍爾曼和霍爾曼(H. Hollmann)提出的提出的分分裂基快速算法裂基快速算法，使運(yùn)算效率進(jìn)一步提高。，使運(yùn)算效率進(jìn)一步提高。本章主要討論本章主要討論基基2FFT算法。算法。 4.2 基基2FFT算法算法4.2.1 直接計(jì)算直接計(jì)算DFT的特點(diǎn)及減少運(yùn)算量的基本的特點(diǎn)及減少運(yùn)算量的基本 途徑途徑 有限長(zhǎng)序列有限長(zhǎng)序列x(n)的的N點(diǎn)點(diǎn)DFT為為考慮

4、考慮x(n)為復(fù)數(shù)序列的一般情況，對(duì)某一個(gè)為復(fù)數(shù)序列的一般情況，對(duì)某一個(gè)k值，直接按值，直接按(4.2.1)式計(jì)算式計(jì)算X(k)的的1個(gè)值需要個(gè)值需要N次復(fù)數(shù)乘法和次復(fù)數(shù)乘法和(N1)次復(fù)數(shù)加法。因此，次復(fù)數(shù)加法。因此，計(jì)算計(jì)算X(k)的所有的所有N個(gè)值，共需個(gè)值，共需N2次次復(fù)數(shù)乘法和復(fù)數(shù)乘法和N(N1)次復(fù)數(shù)加法運(yùn)算。次復(fù)數(shù)加法運(yùn)算。10110 )()(NnknNNkWnxkX，（4.2.1） 當(dāng)當(dāng)時(shí)，時(shí)，N(N1)N2。由上述可見(jiàn)，。由上述可見(jiàn)，N點(diǎn)點(diǎn)DFT的乘法和加法運(yùn)算次數(shù)均為的乘法和加法運(yùn)算次數(shù)均為N2。當(dāng)。當(dāng)N較大時(shí)，運(yùn)算較大時(shí)，運(yùn)算量相當(dāng)可觀。例如量相當(dāng)可觀。例如N=1024時(shí)

5、，時(shí)，N2=1 048 576。這對(duì)于。這對(duì)于實(shí)時(shí)信號(hào)處理來(lái)說(shuō)，必將對(duì)處理設(shè)備的計(jì)算速度提出實(shí)時(shí)信號(hào)處理來(lái)說(shuō)，必將對(duì)處理設(shè)備的計(jì)算速度提出難以實(shí)現(xiàn)的要求。所以，必須減少其運(yùn)算量，才能使難以實(shí)現(xiàn)的要求。所以，必須減少其運(yùn)算量，才能使DFT在各種科學(xué)和工程計(jì)算中得到應(yīng)用。在各種科學(xué)和工程計(jì)算中得到應(yīng)用。如前所述，如前所述，N點(diǎn)點(diǎn)DFT的復(fù)乘法次數(shù)等于的復(fù)乘法次數(shù)等于N2。顯然，。顯然，把把N點(diǎn)點(diǎn)DFT分解為幾個(gè)較短的分解為幾個(gè)較短的DFT，可使乘法次數(shù)大大，可使乘法次數(shù)大大減少。減少。 1N FFT算法就是不斷地把長(zhǎng)序列的算法就是不斷地把長(zhǎng)序列的DFT分解成幾個(gè)短序分解成幾個(gè)短序列的列的DFT，并

6、利用，并利用 的周期性和對(duì)稱性來(lái)減少的周期性和對(duì)稱性來(lái)減少DFT的運(yùn)算次數(shù)。算法最簡(jiǎn)單最常用的是基的運(yùn)算次數(shù)。算法最簡(jiǎn)單最常用的是基2FFT。 其對(duì)稱性表現(xiàn)為其對(duì)稱性表現(xiàn)為 (4.2.3a) mNNmNWW或者或者 mNmNNWW*(4.2.3b) mNNmNWW2knNW另外，旋轉(zhuǎn)因子具有明顯的周期性和對(duì)稱性。其周期性表現(xiàn)為另外，旋轉(zhuǎn)因子具有明顯的周期性和對(duì)稱性。其周期性表現(xiàn)為mNmNlNmNlNmNWW2j)(2jee 4.2.2 時(shí)域抽取法基時(shí)域抽取法基2FFT基本原理基本原理基基2FFT算法分為兩類：算法分為兩類：時(shí)域抽取法時(shí)域抽取法FFT(DecimationIn Time FFT，

7、簡(jiǎn)稱，簡(jiǎn)稱DITFFT )； 頻域抽取法頻域抽取法FFT (Decimation In Frequency FFT，簡(jiǎn)稱，簡(jiǎn)稱DIFFFT)。本節(jié)。本節(jié)介紹介紹DITFFT算法。算法。設(shè)序列設(shè)序列x(n)的長(zhǎng)度為的長(zhǎng)度為N，且滿足，且滿足N=2M，M為自然數(shù)。為自然數(shù)。按按n的奇偶的奇偶把把x(n)分解為兩個(gè)分解為兩個(gè)N/2點(diǎn)的子序列點(diǎn)的子序列12( )(2 )0112( )(21)0112Nx rxrrNx rxrr， ， ， 則則x(n)的的DFT為為/2 1/2 12(21)00/2 1/2 1221200( )( )( )(2 )(21)( )( )knknNNnnNNkrkrNNrr

8、NNkrkkrNNNrrX kx n Wx n Wxr WxrWx r WWx r W偶數(shù)奇數(shù)因?yàn)橐驗(yàn)?2jj222/2eekrkrkrkrNNNNWW所以所以/2 1/2 11/22/20012( )( )( ) ( )( ) 0,1,2,-1NNkrkkrNNNrrkNX kx r WWxr WXkW XkkN 其中其中1(k)和和X2(k)分別為分別為x1(r)和和x2(r)的的N/2點(diǎn)點(diǎn)DFT, 即即由于由于X1(k)和和X2(k)均以均以N/2為周期，且為周期，且 ，因此，因此X(k)又可表示為又可表示為(4.2.5) /2 111/2120( )( )DFT( )NkrNNrX k

9、x r Wx r(4.2.6) /2 122/2220( )( )DFT( )NkrNNrXkx r Wx rkNNkNWW212( )( )( ) 0,1,2,-1kNX kX kW XkkN 這樣，就將這樣，就將N點(diǎn)點(diǎn)DFT分解為兩個(gè)分解為兩個(gè)N/2點(diǎn)點(diǎn)DFT和和(4.2.7)式以及式以及(4.2.8)式的運(yùn)算。式的運(yùn)算。(4.2.7)和和(4.2.8)式的運(yùn)算可用圖式的運(yùn)算可用圖4.2.1所示所示的流圖符號(hào)表示，稱為的流圖符號(hào)表示，稱為蝶形運(yùn)算符號(hào)蝶形運(yùn)算符號(hào)。采用這種圖示法，。采用這種圖示法，經(jīng)過(guò)一次奇偶抽取分解后，經(jīng)過(guò)一次奇偶抽取分解后，N點(diǎn)點(diǎn)DFT運(yùn)算圖可以用圖運(yùn)算圖可以用圖4.2

10、.2表示。圖中，表示。圖中，N=23=8， X(0)X(3)由由(4.2.7)式給出，而式給出，而X(4) X(7)則由則由(4.2.8)式給出。式給出。 (4.2.7) 1210)()()(21NkkXWkXkXkN，(4.2.8) 1210)()()2(21NkkXWkXNkXkN， 圖圖4.2.1 蝶形運(yùn)算符號(hào)蝶形運(yùn)算符號(hào)偶數(shù)點(diǎn)的偶數(shù)點(diǎn)的N/2 DFT奇數(shù)點(diǎn)的奇數(shù)點(diǎn)的N/2 DFTkNW序列序列DFT的的N/2個(gè)點(diǎn)個(gè)點(diǎn)序列序列DFT的后的后N/2個(gè)個(gè)點(diǎn)點(diǎn) 圖圖4.2.2 8點(diǎn)點(diǎn)DFT一次時(shí)域抽取分解運(yùn)算流圖一次時(shí)域抽取分解運(yùn)算流圖 由圖由圖4.2.1可見(jiàn)，要完成可見(jiàn)，要完成一個(gè)蝶形運(yùn)算一

11、個(gè)蝶形運(yùn)算，需要，需要一次復(fù)一次復(fù)數(shù)乘法數(shù)乘法和和兩次復(fù)數(shù)加法兩次復(fù)數(shù)加法運(yùn)算。由圖運(yùn)算。由圖4.2.2容易看出，經(jīng)過(guò)容易看出，經(jīng)過(guò)一次分解后，計(jì)算一次分解后，計(jì)算1個(gè)個(gè)N點(diǎn)點(diǎn)DFT共需要計(jì)算共需要計(jì)算兩個(gè)兩個(gè)N/2點(diǎn)點(diǎn)DFT和和N/2個(gè)蝶形運(yùn)算個(gè)蝶形運(yùn)算。而計(jì)算一個(gè)。而計(jì)算一個(gè)N/2點(diǎn)點(diǎn)DFT需要需要(N/2)2次復(fù)次復(fù)數(shù)乘法和數(shù)乘法和N/2(N/21)次復(fù)數(shù)加法。所以，按圖次復(fù)數(shù)加法。所以，按圖4.2.2計(jì)算計(jì)算N點(diǎn)點(diǎn)DFT時(shí)，總共需要的復(fù)數(shù)乘法次數(shù)為時(shí)，總共需要的復(fù)數(shù)乘法次數(shù)為 221(1)22222NNNN NN復(fù)數(shù)加法次數(shù)為復(fù)數(shù)加法次數(shù)為22122222NNNN 由此可見(jiàn)，僅僅經(jīng)過(guò)一

12、次分解，就使運(yùn)算量減少近由此可見(jiàn)，僅僅經(jīng)過(guò)一次分解，就使運(yùn)算量減少近一半。既然這樣分解對(duì)減少一半。既然這樣分解對(duì)減少DFT的運(yùn)算量是有效的，且的運(yùn)算量是有效的，且N=2M, N/2仍然是偶數(shù)，故可以對(duì)仍然是偶數(shù)，故可以對(duì)N/2點(diǎn)點(diǎn)DFT再作進(jìn)一步再作進(jìn)一步分解。分解。與第一次分解相同，將與第一次分解相同，將x1(r)按奇偶分解成兩個(gè)按奇偶分解成兩個(gè)N/4點(diǎn)的子序列點(diǎn)的子序列x3(l)和和x4(l)，即，即3141( )(2 )011( )(21)4x lxlNlx lxl， ， X1(k)又可表示為又可表示為(4.2.9) /4 1/4 12(21)11/21/200/4 1/4 12(21)

13、3/24/200/4 1/4 13/4/24/4003/24( )(2 )(21)( )( )( )( )( )( )0112NNklklNNllNNklklNNllNNklkklNNNllkNX kxl WxlWx l Wx l Wx l WWx l WNXkWXkk， ， 式中式中同理，由同理，由X3(k)和和X4(k)的周期性和的對(duì)稱性的周期性和的對(duì)稱性最后得到：最后得到：/4 133/4340( )( )DFT( )NklNNlXkx l Wx l/4 144/4440( )( )DFT( )NklNNlXkx l Wx lmNW2/kNNkNWW2/4/2/ (4.2.10) 14/

14、10)()() 4/()()()(42/3142/31NkkXWkXNkXkXWkXkXkNkN， 用同樣的方法可計(jì)算出用同樣的方法可計(jì)算出/4 155/4540/4 166/46405262( )( )DFT( )( )( )DFT( )( )(2 )01/4 1( )(21)NklNNlNklNNlXkx l Wx lXkx l Wx lx lxllNx lxl， ，1410 )()(4)()()(62/5262/52NkkXWkXNkXkXWkXkXkNkN，(4.2.11)其中：其中： 這樣，經(jīng)過(guò)第二次分解，又將這樣，經(jīng)過(guò)第二次分解，又將N/2點(diǎn)點(diǎn)DFT分解為分解為2個(gè)個(gè)N/4點(diǎn)點(diǎn)DF

15、T和和(4.2.10)式或式或(4.2.11)式所示的式所示的N/4個(gè)蝶形運(yùn)算，個(gè)蝶形運(yùn)算，如圖如圖4.2.3所示。所示。 依次類推，依次類推，經(jīng)過(guò)經(jīng)過(guò)M次分解，最后將次分解，最后將N點(diǎn)點(diǎn)DFT分解成分解成N個(gè)個(gè)1點(diǎn)點(diǎn)DFT和和M級(jí)蝶形運(yùn)算，而級(jí)蝶形運(yùn)算，而1點(diǎn)點(diǎn)DFT就是時(shí)域序列本就是時(shí)域序列本身。身。一個(gè)完整的一個(gè)完整的8點(diǎn)點(diǎn)DITFFT運(yùn)算流圖如圖運(yùn)算流圖如圖4.2.4所示。所示。圖中用到關(guān)系式。圖中圖中用到關(guān)系式。圖中輸入序列不是順序排輸入序列不是順序排列列，但后面會(huì)看到，但后面會(huì)看到，其排列是有規(guī)律的其排列是有規(guī)律的。圖中的數(shù)組。圖中的數(shù)組A用于存放輸入序列和每級(jí)運(yùn)算結(jié)果。用于存放輸

16、入序列和每級(jí)運(yùn)算結(jié)果。mkNkmNWW/ 圖圖4.2.3 8點(diǎn)點(diǎn)DFT二次時(shí)域抽取分解運(yùn)算流圖二次時(shí)域抽取分解運(yùn)算流圖 圖圖4.2.4 8點(diǎn)點(diǎn)DIT-FFT運(yùn)算流圖運(yùn)算流圖 4.2.3 DIT-FFT算法與直接計(jì)算算法與直接計(jì)算DFT運(yùn)算量的比較運(yùn)算量的比較由由DIT-FFT算法的分解過(guò)程及圖算法的分解過(guò)程及圖4.2.4可見(jiàn)，當(dāng)可見(jiàn)，當(dāng)N=2M 時(shí)，時(shí)，其運(yùn)算流圖應(yīng)有其運(yùn)算流圖應(yīng)有M級(jí)蝶形級(jí)蝶形，每一級(jí)都由，每一級(jí)都由N/2個(gè)蝶形運(yùn)算個(gè)蝶形運(yùn)算構(gòu)成。構(gòu)成。因此，每一級(jí)運(yùn)算都需要因此，每一級(jí)運(yùn)算都需要N/2次復(fù)數(shù)乘和次復(fù)數(shù)乘和N次復(fù)數(shù)加次復(fù)數(shù)加(每個(gè)每個(gè)蝶形需要兩次復(fù)數(shù)加法蝶形需要兩次復(fù)數(shù)加法)

17、。所以，。所以，M級(jí)運(yùn)算總共需要的復(fù)數(shù)級(jí)運(yùn)算總共需要的復(fù)數(shù)乘次數(shù)為乘次數(shù)為復(fù)數(shù)加次數(shù)為復(fù)數(shù)加次數(shù)為2log22MNNCMN2logACN MNN 而直接計(jì)算而直接計(jì)算DFT的復(fù)數(shù)乘為的復(fù)數(shù)乘為N2次，復(fù)數(shù)加為次，復(fù)數(shù)加為N(N1)次。次。當(dāng)當(dāng)N1時(shí)，時(shí)，N2 (N/2) log2N，所以，所以，DIT-FFT算法比直算法比直接計(jì)算接計(jì)算DFT的運(yùn)算次數(shù)大大減少。的運(yùn)算次數(shù)大大減少。例如，例如，N=210=1024時(shí)，時(shí)，這樣，就使運(yùn)算效率提高這樣，就使運(yùn)算效率提高200多倍。圖多倍。圖4.2.5為為FFT算法算法和直接計(jì)算和直接計(jì)算DFT所需復(fù)數(shù)乘法次數(shù)所需復(fù)數(shù)乘法次數(shù)CM與變換點(diǎn)數(shù)與變換點(diǎn)數(shù)

18、N的關(guān)的關(guān)系曲線。由此圖更加直觀地看出系曲線。由此圖更加直觀地看出FFT算法的優(yōu)越性，顯算法的優(yōu)越性，顯然，然，N越大時(shí)，優(yōu)越性就越明顯。越大時(shí)，優(yōu)越性就越明顯。221 048 576204.85120log2NNN 圖圖4.2.5 DIT-FFT算法與直接計(jì)算算法與直接計(jì)算DFT所需復(fù)數(shù)乘法次數(shù)的比較曲線所需復(fù)數(shù)乘法次數(shù)的比較曲線 4.2.4 DIT-FFT的運(yùn)算規(guī)律及蝶形畫(huà)法的運(yùn)算規(guī)律及蝶形畫(huà)法1 原位計(jì)算原位計(jì)算由圖由圖4.2.4可以看出，可以看出，DIT-FFT的運(yùn)算過(guò)程很有規(guī)律。的運(yùn)算過(guò)程很有規(guī)律。 N=2M點(diǎn)的點(diǎn)的FFT共進(jìn)行共進(jìn)行M級(jí)運(yùn)算，每級(jí)由級(jí)運(yùn)算，每級(jí)由N/2個(gè)蝶形運(yùn)算個(gè)蝶

19、形運(yùn)算 組成。組成。同一級(jí)中，每個(gè)蝶形的兩個(gè)輸入數(shù)據(jù)只對(duì)計(jì)算本蝶形有同一級(jí)中，每個(gè)蝶形的兩個(gè)輸入數(shù)據(jù)只對(duì)計(jì)算本蝶形有 用，而且每個(gè)蝶形的輸入、輸出數(shù)據(jù)結(jié)點(diǎn)又同在一條水用，而且每個(gè)蝶形的輸入、輸出數(shù)據(jù)結(jié)點(diǎn)又同在一條水 平線上，這就意味著計(jì)算完一個(gè)蝶形后，所得輸出數(shù)據(jù)平線上，這就意味著計(jì)算完一個(gè)蝶形后，所得輸出數(shù)據(jù) 可立即存入原輸入數(shù)據(jù)所占用的存儲(chǔ)單元可立即存入原輸入數(shù)據(jù)所占用的存儲(chǔ)單元(數(shù)組元素?cái)?shù)組元素)。這樣，這樣，經(jīng)過(guò)經(jīng)過(guò)M級(jí)運(yùn)算后，原來(lái)存放輸入序列數(shù)據(jù)的級(jí)運(yùn)算后，原來(lái)存放輸入序列數(shù)據(jù)的N個(gè)個(gè) 存儲(chǔ)單元存儲(chǔ)單元(數(shù)組數(shù)組A)中便依次存放中便依次存放X(k)的的N個(gè)值。個(gè)值。 8點(diǎn)點(diǎn)DIT-F

20、FT運(yùn)算流圖的畫(huà)法運(yùn)算流圖的畫(huà)法 2 旋轉(zhuǎn)因子的變化規(guī)律旋轉(zhuǎn)因子的變化規(guī)律如上所述，如上所述，N點(diǎn)點(diǎn)DIT-FFT運(yùn)算流圖中，每級(jí)都有運(yùn)算流圖中，每級(jí)都有N/2個(gè)蝶形。每個(gè)蝶形都要乘以因子，稱其為個(gè)蝶形。每個(gè)蝶形都要乘以因子，稱其為旋轉(zhuǎn)因子旋轉(zhuǎn)因子，p為旋轉(zhuǎn)因子的指數(shù)。但各級(jí)的旋轉(zhuǎn)因子都有所不同。為旋轉(zhuǎn)因子的指數(shù)。但各級(jí)的旋轉(zhuǎn)因子都有所不同。 為了畫(huà)出蝶形圖，應(yīng)先找出旋轉(zhuǎn)因子為了畫(huà)出蝶形圖，應(yīng)先找出旋轉(zhuǎn)因子 與運(yùn)算級(jí)數(shù)與運(yùn)算級(jí)數(shù)的關(guān)系。用的關(guān)系。用L表示從左到右的運(yùn)算級(jí)數(shù)表示從左到右的運(yùn)算級(jí)數(shù)(L=1，2，M)。觀察圖觀察圖4.2.4不難發(fā)現(xiàn)，第不難發(fā)現(xiàn)，第L級(jí)共有級(jí)共有2L1個(gè)不同的旋轉(zhuǎn)因個(gè)

21、不同的旋轉(zhuǎn)因子。子。N=23=8時(shí)的各級(jí)旋轉(zhuǎn)因子表示如下：時(shí)的各級(jí)旋轉(zhuǎn)因子表示如下：pNWpNW 對(duì)對(duì)N=2M的一般情況，第的一般情況，第L級(jí)的旋轉(zhuǎn)因子為：級(jí)的旋轉(zhuǎn)因子為：3, 2, 1, 0 31, 0 20 1222/24/JWWWLJWWWLJWWWLJJNpNJJNpNJJNpNLLL時(shí)時(shí)時(shí)L-12,0,1,2,21LpJNWWJ 因?yàn)橐驗(yàn)樗运訫LMLMLN222212, 2, 1, 0122LJNJNpNJWWWLMML（4.2.12）LMJp2（4.2.13）這樣，就可按這樣，就可按(4.2.12)和和(4.2.13)式式確定第確定第L級(jí)運(yùn)算的旋轉(zhuǎn)級(jí)運(yùn)算的旋轉(zhuǎn)因子因子。 3 序

22、列的倒序序列的倒序DIT-FFT算法的輸入序列的排序看起來(lái)似乎很亂，但仔算法的輸入序列的排序看起來(lái)似乎很亂，但仔 細(xì)分析就會(huì)發(fā)現(xiàn)這種倒序是很有規(guī)律的。由于細(xì)分析就會(huì)發(fā)現(xiàn)這種倒序是很有規(guī)律的。由于N=2M， 因此順序數(shù)可用因此順序數(shù)可用M位二進(jìn)制數(shù)位二進(jìn)制數(shù)(nM1 nM2n1n0)表示。表示。表表4.2.1列出了列出了N=8時(shí)以二進(jìn)制數(shù)表示的順序數(shù)和倒序時(shí)以二進(jìn)制數(shù)表示的順序數(shù)和倒序 數(shù)，由表顯而易見(jiàn)，數(shù)，由表顯而易見(jiàn)，只要將順序數(shù)只要將順序數(shù)(n2n1n0)的二進(jìn)制位的二進(jìn)制位 倒置，則得對(duì)應(yīng)的二進(jìn)制倒序值倒置，則得對(duì)應(yīng)的二進(jìn)制倒序值(n0n1n2) 4.2.5 頻域抽取法頻域抽取法FFT(

23、DIF-FFT)在基在基2FFT算法中，頻域抽取法算法中，頻域抽取法FFT也是一種常用也是一種常用的快速算法，簡(jiǎn)稱的快速算法，簡(jiǎn)稱DTF- FFT。設(shè)序列設(shè)序列x(n)長(zhǎng)度為長(zhǎng)度為N=2M，首先將，首先將x(n)前后對(duì)半分前后對(duì)半分開(kāi)開(kāi)，得到兩個(gè)子序列，其，得到兩個(gè)子序列，其DFT可表示為如下形式：可表示為如下形式：10/2 110/2/2 1/2 1(/2)00/2 1/20( )DFT ( )( )( )( )( )2( )2NknNnNNknknNNnn NNNknk n NNNnnNkNknNNnX kx nx n Wx n Wx n WNx n Wx nWNx nWx nW 式中式中

24、將將X(k)分解成偶數(shù)組與奇數(shù)組，當(dāng)分解成偶數(shù)組與奇數(shù)組，當(dāng)k取取偶數(shù)偶數(shù)(k=2m, m=0, 1, , N/21)時(shí)時(shí)/21( 1)1kNkNkWk 偶數(shù)奇數(shù)，/2 120/2 1/20(2 )( )2( )2NmnNnNmnNnNXmx nx nWNx nx nW（4.2.14） 當(dāng)當(dāng)k取奇數(shù)取奇數(shù)(k=2m+1, m=0, 1, , N/21)時(shí)，時(shí)，令令122102)()(2)()(21NnWNnxnxnxNnxnxnxnN，/2 1(21)0/2 1/20(21)( )2( )2NnmNnNnnmNNnNXmx nx nWNx nx nWW(4.2.15) 將將x1(n)和和x2(

25、n)分別代入分別代入(4.2.14)和和(4.2.15)式，可得式，可得(4.2.16)式表明，式表明，X(k)按奇偶按奇偶k值分為兩組，其偶數(shù)組是值分為兩組，其偶數(shù)組是x1(n)的的N/2點(diǎn)點(diǎn)DFT，奇數(shù)組則是，奇數(shù)組則是x2(n)的的N/2點(diǎn)點(diǎn)DFT。x1(n)、x2(n)和和x(n)之間的關(guān)系也可用圖之間的關(guān)系也可用圖4.2.10所示的蝶所示的蝶形運(yùn)算流圖符號(hào)表示。圖形運(yùn)算流圖符號(hào)表示。圖4.2.11表示表示N=8時(shí)第一次分解時(shí)第一次分解的運(yùn)算流圖。的運(yùn)算流圖。/2 11/20/2 12/20(2 )( )(21)( )NmnNnNmnNnXmx n WXmx n W 圖圖4.2.10

26、DTFFFT蝶形運(yùn)算流圖符號(hào)蝶形運(yùn)算流圖符號(hào)序列的序列的前半部前半部分分序列的后序列的后半部分半部分 圖圖4.2.11 DIF-FFT第一次分解運(yùn)算流圖（第一次分解運(yùn)算流圖（N=8） 由于由于N=2M，N/2仍然是偶數(shù)，繼續(xù)將仍然是偶數(shù)，繼續(xù)將N/2點(diǎn)點(diǎn)DFT分成分成 偶數(shù)組和奇數(shù)組，這樣每個(gè)偶數(shù)組和奇數(shù)組，這樣每個(gè)N/2點(diǎn)點(diǎn)DFT又可由兩個(gè)又可由兩個(gè)N/4 點(diǎn)點(diǎn)DFT形成，其輸入序列分別是形成，其輸入序列分別是x1(n)和和x2(n)按上下對(duì)按上下對(duì) 半分開(kāi)形成的四個(gè)子序列。半分開(kāi)形成的四個(gè)子序列。圖圖4.2.12示出了示出了N=8時(shí)第二次分解運(yùn)算流圖。以這種方時(shí)第二次分解運(yùn)算流圖。以這種方

27、 式分解下去，經(jīng)過(guò)式分解下去，經(jīng)過(guò)M1次分解，最后分解為次分解，最后分解為2M1個(gè)個(gè) 兩點(diǎn)兩點(diǎn)DFT，兩點(diǎn)兩點(diǎn)DFT就是一個(gè)基本蝶形運(yùn)算流圖就是一個(gè)基本蝶形運(yùn)算流圖。當(dāng)當(dāng)N=8，經(jīng)兩次分解，便分解為四個(gè)兩點(diǎn)，經(jīng)兩次分解，便分解為四個(gè)兩點(diǎn)DFT。N = 8 的完整的完整DIF-FFT運(yùn)算流圖如圖運(yùn)算流圖如圖4.2.13所示。所示。 圖圖4.2.12 DIF-FFT第二次分解運(yùn)算流圖（第二次分解運(yùn)算流圖（N = 8） 圖圖4.2.13 DIF-FFT運(yùn)算流圖（運(yùn)算流圖（N =8） 這種算法是對(duì)這種算法是對(duì)X(k)進(jìn)行奇偶抽取分解的結(jié)果，所以稱之為進(jìn)行奇偶抽取分解的結(jié)果，所以稱之為 頻域抽取法頻域抽

28、取法FFT。觀察圖觀察圖4.2.13可知，可知，DIF-FFT算法與算法與DIT-TTF算法類似，算法類似， 共有共有M級(jí)運(yùn)算，每級(jí)共有級(jí)運(yùn)算，每級(jí)共有N/2個(gè)蝶形運(yùn)算，所以兩種算法個(gè)蝶形運(yùn)算，所以兩種算法 的運(yùn)算次數(shù)亦相同。的運(yùn)算次數(shù)亦相同。不同的是不同的是DIF-FFT算法輸入序列為自然順序，而輸出為倒算法輸入序列為自然順序，而輸出為倒 序排列。因此，序排列。因此，M級(jí)運(yùn)算完后，要對(duì)輸出數(shù)據(jù)進(jìn)行排序才級(jí)運(yùn)算完后，要對(duì)輸出數(shù)據(jù)進(jìn)行排序才 能得到自然順序的能得到自然順序的X(k)。另外，蝶形運(yùn)算略有不同，另外，蝶形運(yùn)算略有不同，DIT-FFT蝶形先乘后加蝶形先乘后加(減減)， 而而DIF-FF

29、T蝶形先加蝶形先加(減減)后相乘。后相乘。 4.2.6 IDFT的高效算法的高效算法上述上述FFT算法流圖也可以用于計(jì)算算法流圖也可以用于計(jì)算IDFT。比較。比較DFT和和IDFT的運(yùn)算公式：的運(yùn)算公式：1010( )DFT ( )( )1( )IDFT ( )( ) NknNnNknNkX kx nx n Wx nX kX k WN 只要將只要將DFT運(yùn)算式中的系數(shù)運(yùn)算式中的系數(shù)改為，最后乘以改為，最后乘以 1/N，就是，就是IDFT運(yùn)算公式。運(yùn)算公式。所以，只要將上述的所以，只要將上述的DIT-FFT與與DIF-FFT算法中的旋算法中的旋 轉(zhuǎn)因子轉(zhuǎn)因子 改為，最后的輸出再乘以改為，最后的輸

30、出再乘以1/N就可以用就可以用 來(lái)計(jì)算來(lái)計(jì)算IDFT。只是現(xiàn)在流圖的輸入是。只是現(xiàn)在流圖的輸入是X(k)，輸出就，輸出就 是是x(n)。因此，原來(lái)的因此，原來(lái)的DIT-FFT改為改為IFFT后，稱為后，稱為DIF-IFFT 更合適；更合適；DIF-FFT改為改為IFFT后后, 應(yīng)稱為應(yīng)稱為DIT-IFFT。knNWpNWpNWknNW 如果希望直接調(diào)用如果希望直接調(diào)用FFT子程序計(jì)算子程序計(jì)算IFFT，則可用，則可用下面的方法：下面的方法：由于由于所以，可以先將所以，可以先將X(k)取復(fù)共軛，然后直接調(diào)用取復(fù)共軛，然后直接調(diào)用FFT子子程序，最后取復(fù)共軛并乘以程序，最后取復(fù)共軛并乘以1/N得到

31、序列得到序列x(n)。這種方。這種方法雖然用了兩次取共軛運(yùn)算，但可以與法雖然用了兩次取共軛運(yùn)算，但可以與FFT共用同一共用同一子程序，因而用起來(lái)很方便。子程序，因而用起來(lái)很方便。*10*)(1)(1)(kXDFTNWkXNnxNkknN 圖圖4.2.4 8點(diǎn)點(diǎn)DIT-FFT運(yùn)算流圖運(yùn)算流圖 L=1 L=2 L=3 4.3 進(jìn)一步減少運(yùn)算量的措施進(jìn)一步減少運(yùn)算量的措施4.3.1 多類蝶形單元運(yùn)算多類蝶形單元運(yùn)算由由DIT-FFT運(yùn)算流圖已得出結(jié)論，運(yùn)算流圖已得出結(jié)論，N=2M點(diǎn)點(diǎn)FFT共需要共需要MN/2次復(fù)數(shù)乘法。次復(fù)數(shù)乘法。 由由(4.2.12)式，當(dāng)式，當(dāng)L=1時(shí)，只有一種旋轉(zhuǎn)因子時(shí)，只有

32、一種旋轉(zhuǎn)因子所以，第一級(jí)不需要乘法運(yùn)算。當(dāng)所以，第一級(jí)不需要乘法運(yùn)算。當(dāng)L=2 時(shí)，共有兩個(gè)時(shí)，共有兩個(gè)旋轉(zhuǎn)因子：旋轉(zhuǎn)因子： 和和 ，因此，第二級(jí)也不，因此，第二級(jí)也不需要乘法運(yùn)算。在需要乘法運(yùn)算。在DFT中，又稱其值為中，又稱其值為1和和j的旋的旋轉(zhuǎn)因子為無(wú)關(guān)緊要的旋轉(zhuǎn)因子如轉(zhuǎn)因子為無(wú)關(guān)緊要的旋轉(zhuǎn)因子如 ， ， 等。等。10NW10NWjWNN4/0NW2/NNW4/NNW 綜上所述，先除去第一、二兩級(jí)后，所需復(fù)數(shù)乘綜上所述，先除去第一、二兩級(jí)后，所需復(fù)數(shù)乘法次數(shù)應(yīng)是法次數(shù)應(yīng)是進(jìn)一步考慮各級(jí)中的無(wú)關(guān)緊要旋轉(zhuǎn)因子。當(dāng)進(jìn)一步考慮各級(jí)中的無(wú)關(guān)緊要旋轉(zhuǎn)因子。當(dāng)L=3時(shí)，時(shí)，有兩個(gè)無(wú)關(guān)緊要的旋轉(zhuǎn)因子和

33、，因?yàn)橥挥袃蓚€(gè)無(wú)關(guān)緊要的旋轉(zhuǎn)因子和，因?yàn)橥恍D(zhuǎn)因子對(duì)應(yīng)著旋轉(zhuǎn)因子對(duì)應(yīng)著2ML=N/2L個(gè)碟形運(yùn)算，所以第三級(jí)共個(gè)碟形運(yùn)算，所以第三級(jí)共有有2N/23=N/4 個(gè)碟形不需要復(fù)數(shù)乘法運(yùn)算。依此類推，個(gè)碟形不需要復(fù)數(shù)乘法運(yùn)算。依此類推，當(dāng)當(dāng)L3時(shí)，第時(shí)，第L級(jí)的級(jí)的2個(gè)無(wú)關(guān)緊要的旋轉(zhuǎn)因子減少?gòu)?fù)數(shù)乘個(gè)無(wú)關(guān)緊要的旋轉(zhuǎn)因子減少?gòu)?fù)數(shù)乘法的次數(shù)為法的次數(shù)為2N/2L=N/2L1。這樣，從。這樣，從L=3至至L=M共減共減少?gòu)?fù)數(shù)乘法次數(shù)為少?gòu)?fù)數(shù)乘法次數(shù)為 0NW4/NNW(2)2MNCM(4.3.1) 因此，因此，DIT-FFT的的復(fù)乘次數(shù)降至復(fù)乘次數(shù)降至 下面再討論下面再討論FFT中特殊的復(fù)數(shù)運(yùn)算，以便進(jìn)

34、一步減少中特殊的復(fù)數(shù)運(yùn)算，以便進(jìn)一步減少 復(fù)數(shù)乘法次數(shù)。復(fù)數(shù)乘法次數(shù)。一般實(shí)現(xiàn)一次復(fù)數(shù)乘法運(yùn)算需要四次一般實(shí)現(xiàn)一次復(fù)數(shù)乘法運(yùn)算需要四次 實(shí)數(shù)乘，兩次實(shí)數(shù)加實(shí)數(shù)乘，兩次實(shí)數(shù)加。但對(duì)這一特。但對(duì)這一特 殊復(fù)數(shù)，任一復(fù)數(shù)殊復(fù)數(shù)，任一復(fù)數(shù)(x+jy)與其相乘時(shí)，與其相乘時(shí)，(4.3.2)222122331NNNMLLMLL2/2)1 (8/jWNN(2)2(3)2222MNNNCMM（4.3.3） 22(1j)(j )(jj)222()j()2xyxyxyxyxyRjI2()222()()22RxyIxyyx 只需要兩次實(shí)數(shù)加和兩次實(shí)數(shù)乘就可實(shí)現(xiàn)。這樣，只需要兩次實(shí)數(shù)加和兩次實(shí)數(shù)乘就可實(shí)現(xiàn)。這樣，對(duì)應(yīng)

35、的每個(gè)蝶形節(jié)省對(duì)應(yīng)的每個(gè)蝶形節(jié)省兩次實(shí)數(shù)乘兩次實(shí)數(shù)乘。8/NNW 在在DIT-FFT運(yùn)算流圖中，從運(yùn)算流圖中，從L=3至至L=M級(jí)，每級(jí)級(jí)，每級(jí)都包含旋轉(zhuǎn)因子都包含旋轉(zhuǎn)因子 ，第，第L級(jí)中，級(jí)中， 對(duì)應(yīng)對(duì)應(yīng)N/2L個(gè)蝶個(gè)蝶形運(yùn)算。因此從第三級(jí)至最后一級(jí)，旋轉(zhuǎn)因子形運(yùn)算。因此從第三級(jí)至最后一級(jí)，旋轉(zhuǎn)因子 節(jié)省的實(shí)數(shù)乘次數(shù)與節(jié)省的實(shí)數(shù)乘次數(shù)與(4.3.2)式相同。式相同。 所以從實(shí)數(shù)乘運(yùn)算考慮，計(jì)算所以從實(shí)數(shù)乘運(yùn)算考慮，計(jì)算N=2M點(diǎn)點(diǎn)DIT-FFT所所需需實(shí)數(shù)乘法實(shí)數(shù)乘法次數(shù)為次數(shù)為 8/NNW8/NNW8/NNW(4.3.4)134(3)22210222MNNRMNM 在基在基2FFT程序中，

36、若包含了所有旋轉(zhuǎn)因子，則稱程序中，若包含了所有旋轉(zhuǎn)因子，則稱該算法為一類碟形單元運(yùn)算；若去掉該算法為一類碟形單元運(yùn)算；若去掉 的旋轉(zhuǎn)因的旋轉(zhuǎn)因子，則稱之為二類碟形單元運(yùn)算；若再去掉子，則稱之為二類碟形單元運(yùn)算；若再去掉 的旋的旋轉(zhuǎn)因子，則稱為三類碟形單元運(yùn)算；若再判斷處理轉(zhuǎn)因子，則稱為三類碟形單元運(yùn)算；若再判斷處理，則稱之為四類碟形運(yùn)算。我們將后三種運(yùn)算稱為多，則稱之為四類碟形運(yùn)算。我們將后三種運(yùn)算稱為多類碟形單元運(yùn)算。顯然，類碟形單元運(yùn)算。顯然，碟形單元類型越多，編程就越碟形單元類型越多，編程就越復(fù)雜，但當(dāng)復(fù)雜，但當(dāng)N較大時(shí)，乘法運(yùn)算的減少量是相當(dāng)可觀的。較大時(shí)，乘法運(yùn)算的減少量是相當(dāng)可觀的

37、。例如，例如，N=4096時(shí)，三類碟形單元運(yùn)算的乘法次數(shù)為一類時(shí)，三類碟形單元運(yùn)算的乘法次數(shù)為一類碟形單元運(yùn)算的碟形單元運(yùn)算的75%。 1mNW (1j) 2 /2mNWmNWj 4.3.2 旋轉(zhuǎn)因子的生成旋轉(zhuǎn)因子的生成在在FFT運(yùn)算中，旋轉(zhuǎn)因子運(yùn)算中，旋轉(zhuǎn)因子，求正弦和余弦函數(shù)值的計(jì)算量是很，求正弦和余弦函數(shù)值的計(jì)算量是很大的。所以編程時(shí)，產(chǎn)生旋轉(zhuǎn)因子的方法直接影響運(yùn)大的。所以編程時(shí)，產(chǎn)生旋轉(zhuǎn)因子的方法直接影響運(yùn)算速度。算速度。一種方法是在每級(jí)運(yùn)算中直接產(chǎn)生；另一種一種方法是在每級(jí)運(yùn)算中直接產(chǎn)生；另一種方法是在方法是在FFT程序開(kāi)始前預(yù)先計(jì)算出程序開(kāi)始前預(yù)先計(jì)算出，m = 0，1，N/21，

38、 存放在數(shù)組存放在數(shù)組中，作為旋轉(zhuǎn)因子表，中，作為旋轉(zhuǎn)因子表，在程序執(zhí)行過(guò)程中直接查表得到所需旋轉(zhuǎn)因子值，不在程序執(zhí)行過(guò)程中直接查表得到所需旋轉(zhuǎn)因子值，不再計(jì)算。再計(jì)算。這樣使運(yùn)算速度大大提高，其不足之處是占這樣使運(yùn)算速度大大提高，其不足之處是占用內(nèi)存較多。用內(nèi)存較多。)/2cos(NmWmN)/2sin(jNmmNW 4.3.3 在實(shí)際工作中，數(shù)據(jù)在實(shí)際工作中，數(shù)據(jù)x(n)常常是實(shí)數(shù)序列。如果直常常是實(shí)數(shù)序列。如果直接按接按FFT運(yùn)算流圖計(jì)算，就是把運(yùn)算流圖計(jì)算，就是把x(n)看成一個(gè)虛部為零看成一個(gè)虛部為零的復(fù)序列進(jìn)行計(jì)算，這就增加了存儲(chǔ)量和運(yùn)算時(shí)間。的復(fù)序列進(jìn)行計(jì)算，這就增加了存儲(chǔ)量和運(yùn)

39、算時(shí)間。處處理該問(wèn)題的方法有兩種。理該問(wèn)題的方法有兩種。早期提出的早期提出的方法是用一個(gè)方法是用一個(gè)N點(diǎn)點(diǎn)FFT計(jì)算兩個(gè)計(jì)算兩個(gè)N點(diǎn)實(shí)序列的點(diǎn)實(shí)序列的FFT，一個(gè)實(shí)序列作為，一個(gè)實(shí)序列作為x(n)的的實(shí)部，另一個(gè)作為虛部，計(jì)算完實(shí)部，另一個(gè)作為虛部，計(jì)算完FFT后，根據(jù)后，根據(jù)DFT的共的共軛對(duì)稱性，由輸出軛對(duì)稱性，由輸出X(k)分別得到兩個(gè)實(shí)序列的分別得到兩個(gè)實(shí)序列的N點(diǎn)點(diǎn)DFT（例題（例題3.2.2）。）。第二種方法是用第二種方法是用N/2點(diǎn)點(diǎn)FFT計(jì)算一個(gè)計(jì)算一個(gè)N點(diǎn)點(diǎn)實(shí)序列的實(shí)序列的DFT。下面簡(jiǎn)要介紹第二種方法。下面簡(jiǎn)要介紹第二種方法。 設(shè)設(shè)x(n)為為N點(diǎn)實(shí)序列，取點(diǎn)實(shí)序列，取x(

40、n)的偶數(shù)點(diǎn)和奇數(shù)點(diǎn)分的偶數(shù)點(diǎn)和奇數(shù)點(diǎn)分別作為新構(gòu)造序列別作為新構(gòu)造序列y(n)的實(shí)部和虛部，即的實(shí)部和虛部，即對(duì)對(duì)y(n)進(jìn)行進(jìn)行N/2點(diǎn)點(diǎn)FFT，輸出，輸出Y(k)，則，則1210)(j)()(1210) 12()()2()(2121NnnxnxnyNnnxnxnxnx，1122( )DFT( )( )0112( )DFT( )( )epopX kx nYkNkXkx njYk ， ， 根據(jù)根據(jù)DIT-FFT的思想及式的思想及式(4.2.7)和和(4.2.8)，可得到，可得到X(k)的前的前 個(gè)值：個(gè)值：式中，式中， 。由于。由于x(n)為實(shí)序列，為實(shí)序列，因此因此X(k)具有共軛對(duì)稱性，

41、具有共軛對(duì)稱性，X(k)的后的后N/2點(diǎn)的值為點(diǎn)的值為12N)0(2 ),0(22211XNXXNX1210)()(*NkkXkNX，210)()()(21NkkXWkXkXkN，（4.3.5） 計(jì)算計(jì)算 N/2點(diǎn)點(diǎn)FFT的復(fù)乘次數(shù)為的復(fù)乘次數(shù)為N(M-1)/4，計(jì)算式，計(jì)算式(4.3.5)的復(fù)乘次數(shù)為的復(fù)乘次數(shù)為N/2，所以用這種算法，所以用這種算法, 計(jì)算計(jì)算X(k)所需所需復(fù)數(shù)乘法次數(shù)為復(fù)數(shù)乘法次數(shù)為 。相對(duì)一般的。相對(duì)一般的N點(diǎn)點(diǎn)FFT算法，上述算法的運(yùn)算效率為算法，上述算法的運(yùn)算效率為當(dāng)當(dāng)N=2M=210時(shí)，時(shí)，=20/11，運(yùn)算速度提高近，運(yùn)算速度提高近1倍。倍。) 1(42) 1

42、(4MNNMN) 1/(2) 1(4/2MMMNMN 4.4 其他快速算法簡(jiǎn)介其他快速算法簡(jiǎn)介快速傅里葉變換算法是信號(hào)處理領(lǐng)域重要的研究課快速傅里葉變換算法是信號(hào)處理領(lǐng)域重要的研究課題。題。本章僅介紹算法最簡(jiǎn)單、編程最容易的基本章僅介紹算法最簡(jiǎn)單、編程最容易的基2FFT算法算法原理及其編程思想，使讀者建立快速傅里葉變換的基本原理及其編程思想，使讀者建立快速傅里葉變換的基本概念，了解研究概念，了解研究FFT算法的主要途徑和編程思路。例如，算法的主要途徑和編程思路。例如，分裂基分裂基FFT算法、離散哈特萊變換算法、離散哈特萊變換(DHT)、基、基4FFT、基、基8FFT、基、基rFFT、混合基、混合基FFT，以及進(jìn)一步減少運(yùn)算量的，以及進(jìn)一步減少運(yùn)算量的途徑等內(nèi)容，對(duì)研究新的快速算法都是很有用的。本節(jié)途徑等內(nèi)容，對(duì)研究新的快速算法都是很有用的。本節(jié)簡(jiǎn)要介紹其他幾種快速算法的運(yùn)算量及其主要特點(diǎn)，以簡(jiǎn)要介紹其他幾種快速算法的運(yùn)算量及其主要特點(diǎn)，以便讀者選擇快速算法時(shí)參考。便讀者選擇快速算法時(shí)參考。 從理論上講，不同基數(shù)的從理論上講，不同基數(shù)的F