第4章快速傅里葉變換

1、第4章 快速傅里葉變換(FFT) 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 4.1 引言引言 4.2 基基2FFT算法算法 4.3 進一步減少運算量的措施進一步減少運算量的措施 4.4 其他快速算法簡介其他快速算法簡介習(xí)題與上機題習(xí)題與上機題第4章 快速傅里葉變換(FFT) 4.1 引引 言言DFT是數(shù)字信號分析與處理中的一種重要變換。但直接計算DFT的計算量與變換區(qū)間長度N的平方成正比，當(dāng)N較大時，計算量太大，所以在快速傅里葉變換FFT(Fast Fourier Transform)出現(xiàn)以前，直接用DFT算法進行譜分析和信號的實時處理是不切實際的。直到1965年提出DFT的一種快速

2、算法以后，情況才發(fā)生了根本的變化。第4章 快速傅里葉變換(FFT) 自從1965年庫利(T. W. Cooley)和圖基(J. W. Tuky)在計算數(shù)學(xué)(Math. Computation, Vol. 19, 1965)雜志上發(fā)表了著名的機器計算傅里葉級數(shù)的一種算法論文后，桑德(G. Sand)圖基等快速算法相繼出現(xiàn)，又經(jīng)人們進行改進，很快形成一套高效計算方法，這就是現(xiàn)在的快速傅里葉變換（FFT）。這種算法使DFT的運算效率提高了1 2個數(shù)量級，為數(shù)字信號處理技術(shù)應(yīng)用于各種信號的實時處理創(chuàng)造了條件，大大推動了數(shù)字信號處理技術(shù)的發(fā)展。第4章 快速傅里葉變換(FFT) 人類的求知欲和科學(xué)的發(fā)展是

3、永無止境的。多年來，人們繼續(xù)尋求更快、更靈活的好算法。1984年，法國的杜哈梅爾(P. Dohamel)和霍爾曼(H. Hollmann)提出的分裂基快速算法，使運算效率進一步提高。本章主要討論基2FFT算法及其編程思想。 第4章 快速傅里葉變換(FFT) 4.2 基基2FFT算法算法4.2.1 直接計算直接計算DFT的特點及減少運算量的的特點及減少運算量的 基本途徑基本途徑有限長序列x(n)的N點DFT為 (4.2.1)考慮x(n)為復(fù)數(shù)序列的一般情況，對某一個k值，直接按(4.2.1)式計算X(k)的1個值需要N次復(fù)數(shù)乘法和(N1)次復(fù)數(shù)加法。因此，計算X(k)的所有N個值，共需N2次復(fù)數(shù)

4、乘法和N(N1)次復(fù)數(shù)加法運算。10110 )()(NnknNNkWnxkX，第4章 快速傅里葉變換(FFT) 1N當(dāng)時，N(N1)N2。由上述可見，N點DFT的乘法和加法運算次數(shù)均為N2。當(dāng)N較大時，運算量相當(dāng)可觀。例如N=1024時，N2=1 048 576。這對于實時信號處理來說，必將對處理設(shè)備的計算速度提出難以實現(xiàn)的要求。所以，必須減少其運算量，才能使DFT在各種科學(xué)和工程計算中得到應(yīng)用。如前所述，N點DFT的復(fù)乘次數(shù)等于N2。顯然，把N點DFT分解為幾個較短的DFT，可使乘法次數(shù)大大減少。另外，旋轉(zhuǎn)因子具有明顯的周期性和對稱性。其周期性表現(xiàn)為 （4.2.2）mNmNlNmNlNmNW

5、W2j)(2jee第4章 快速傅里葉變換(FFT) (4.2.3a) (4.2.3b) FFT算法就是不斷地把長序列的DFT分解成幾個短序列的DFT，并利用的周期性和對稱性來減少DFT的運算次數(shù)。算法最簡單最常用的是基2FFT。 其對稱性表現(xiàn)為mNNmNWW或者 mNmNNWW*mNNmNWW2knNW第4章 快速傅里葉變換(FFT) 4.2.2 時域抽取法基時域抽取法基2FFT基本原理基本原理基2FFT算法分為兩類：時域抽取法FFT(DecimationIn Time FFT，簡稱DITFFT )； 頻域抽取法FFT (Decimation In Frequency FFT，簡稱DIFFFT

6、)。本節(jié)介紹DITFFT算法。設(shè)序列x(n)的長度為N，且滿足N=2M，M為自然數(shù)。按n的奇偶把x(n)分解為兩個N/2點的子序列12( )(2 )0112( )(21)0112Nx rxrrNx rxrr， ， ，第4章 快速傅里葉變換(FFT) 則x(n)的DFT為/2 1/2 12(21)00/2 1/2 1221200( )( )( )(2 )(21)( )( )knknNNnnNNkrkrNNrrNNkrkkrNNNrrX kx n Wx n Wxr WxrWx r WWx r W偶數(shù)奇數(shù)第4章 快速傅里葉變換(FFT) 因為所以(4.2.4) 22jj222/2eekrkrkrkr

7、NNNNWW/2 1/2 11/22/20012( )( )( ) ( )( ) 0,1,2,-1 NNkrrkrNNNrrkNX kx r WWx r WX kW XkkN第4章 快速傅里葉變換(FFT) 其中1(k)和X2(k)分別為x1(r)和x2(r)的N/2點DFT, 即(4.2.5) (4.2.6) 由于X1(k)和X2(k)均以N/2為周期，且 ，因此X(k)又可表示為/2 111/2120( )( )DFT( )NkrNNrX kx r Wx r/2 122/2220( )( )DFT( )NkrNNrXkx r Wx rkNNkNWW2第4章 快速傅里葉變換(FFT) (4.

8、2.7) (4.2.8) 這樣，就將N點DFT分解為兩個N/2點DFT和(4.2.7)式以及(4.2.8)式的運算。(4.2.7)和(4.2.8)式的運算可用圖4.2.1所示的流圖符號表示，稱為蝶形運算符號。采用這種圖示法，經(jīng)過一次奇偶抽取分解后，N點DFT運算圖可以用圖4.2.2表示。圖中，N=23=8， X(0)X(3)由(4.2.7)式給出，而X(4) X(7)則由(4.2.8)式給出。 1210)()()(21NkkXWkXkXkN，1210)()()2(21NkkXWkXNkXkN，第4章 快速傅里葉變換(FFT) 圖4.2.1 蝶形運算符號第4章 快速傅里葉變換(FFT) 圖4.2

9、.2 8點DFT一次時域抽取分解運算流圖第4章 快速傅里葉變換(FFT) 由圖4.2.1可見，要完成一個蝶形運算，需要一次復(fù)數(shù)乘法和兩次復(fù)數(shù)加法運算。由圖4.2.2容易看出，經(jīng)過一次分解后，計算1個N點DFT共需要計算兩個N/2點DFT和N/2個蝶形運算。而計算一個N/2點DFT需要(N/2)2次復(fù)數(shù)乘法和N/2(N/21)次復(fù)數(shù)加法。所以，按圖4.2.2計算N點DFT時，總共需要的復(fù)數(shù)乘法次數(shù)為 221(1)22222NNNN NN第4章 快速傅里葉變換(FFT) 復(fù)數(shù)加法次數(shù)為由此可見，僅僅經(jīng)過一次分解，就使運算量減少近一半。既然這樣分解對減少DFT的運算量是有效的，且N=2M, N/2仍

10、然是偶數(shù)，故可以對N/2點DFT再作進一步分解。與第一次分解相同，將x1(r)按奇偶分解成兩個N/4點的子序列x3(l)和x4(l)，即222122NNNN1410) 12()()2()(1423Nllxlxlxlx，第4章 快速傅里葉變換(FFT) X1(k)又可表示為(4.2.9) 1210)()()()() 12()2()(42/314/04/42/14/04/314/0)12(2/114/022/11NkkXWkXWlxWWlxWlxWlxkXkNNlklNkNNlklNNllkNNlklN，第4章 快速傅里葉變換(FFT) 式中同理，由X3(k)和X4(k)的周期性和的對稱性最后得到

11、： (4.2.10) /4 133/4340( )( )DFT( )NklNNlXkx l Wx l/4 144/4440( )( )DFT( )NklNNlXkx l Wx lmNW2/kNNkNWW2/4/2/14/10)()()4/()()()(42/3142/31NkkXWkXNkXkXWkXkXkNkN，第4章 快速傅里葉變換(FFT) 用同樣的方法可計算出 (4.2.11)其中1410 )()(4)()()(62/5262/52NkkXWkXNkXkXWkXkXkNkN，/4 155/4540/4 166/46405262( )( )DFT( )( )( )DFT( )( )(2

12、)01/4 1( )(21)NklNNlNklNNlXkx l Wx lXkx l Wx lx lxllNx lxl， ，第4章 快速傅里葉變換(FFT) 這樣，經(jīng)過第二次分解，又將N/2點DFT分解為2個N/4點DFT和(4.2.10)式或(4.2.11)式所示的N/4個蝶形運算，如圖4.2.3所示。依次類推，經(jīng)過M次分解，最后將N點DFT分解成N個1點DFT和M級蝶形運算，而1點DFT就是時域序列本身。一個完整的8點DITFFT運算流圖如圖4.2.4所示。圖中用到關(guān)系式。圖中輸入序列不是順序排列，但后面會看到，其排列是有規(guī)律的。圖中的數(shù)組A用于存放輸入序列和每級運算結(jié)果，在后面討論編程方法

13、和倒序時要用到。 mkNkmNWW/第4章 快速傅里葉變換(FFT) 圖4.2.3 8點DFT二次時域抽取分解運算流圖第4章 快速傅里葉變換(FFT) 圖4.2.4 8點DIT-FFT運算流圖第4章 快速傅里葉變換(FFT) 4.2.3 DIT-FFT算法與直接計算算法與直接計算DFT運算量的比較運算量的比較由DIT-FFT算法的分解過程及圖4.2.4可見，N=2M 時，其運算流圖應(yīng)有M級蝶形，每一級都由N/2個蝶形運算構(gòu)成。因此，每一級運算都需要N/2次復(fù)數(shù)乘和N次復(fù)數(shù)加(每個蝶形需要兩次復(fù)數(shù)加法)。所以，M級運算總共需要的復(fù)數(shù)乘次數(shù)為lb22MNNCMNlbACN MNN復(fù)數(shù)加次數(shù)為第4章

14、 快速傅里葉變換(FFT) 而直接計算DFT的復(fù)數(shù)乘為N2次，復(fù)數(shù)加為N(N1)次。當(dāng)N1時，N2(N/2) lbN，所以，DIT-FFT算法比直接計算DFT的運算次數(shù)大大減少。例如，N=210=1024時，這樣，就使運算效率提高200多倍。圖4.2.5為FFT算法和直接計算DFT所需復(fù)數(shù)乘法次數(shù)CM與變換點數(shù)N的關(guān)系曲線。由此圖更加直觀地看出FFT算法的優(yōu)越性，顯然，N越大時，優(yōu)越性就越明顯。8 .2045120576 048 1lb22NNN第4章 快速傅里葉變換(FFT) 圖4.2.5 DIT-FFT算法與直接計算DFT所需復(fù)數(shù)乘法次數(shù)的比較曲線第4章 快速傅里葉變換(FFT) 4.2.

15、4 DIT-FFT的運算規(guī)律及編程思想的運算規(guī)律及編程思想1 原位計算原位計算由圖4.2.4可以看出，DIT-FFT的運算過程很有規(guī)律。N=2M點的FFT共進行M級運算，每級由N/2個蝶形運算組成。同一級中，每個蝶形的兩個輸入數(shù)據(jù)只對計算本蝶形有用，而且每個蝶形的輸入、輸出數(shù)據(jù)結(jié)點又同在一條水平線上，這就意味著計算完一個蝶形后，所得輸出數(shù)據(jù)可立即存入原輸入數(shù)據(jù)所占用的存儲單元(數(shù)組元素)。這樣，經(jīng)過M級運算后，原來存放輸入序列數(shù)據(jù)的N個存儲單元(數(shù)組A)中便依次存放X(k)的N個值。這種利用同一存儲單元存儲蝶形計算輸入、輸出數(shù)據(jù)的方法稱為原位(址)計算。原位計算可節(jié)省大量內(nèi)存，從而使設(shè)備成本降

16、低。第4章 快速傅里葉變換(FFT) 2 旋轉(zhuǎn)因子的變化規(guī)律旋轉(zhuǎn)因子的變化規(guī)律如上所述，N點DIT-FFT運算流圖中，每級都有N/2個蝶形。每個蝶形都要乘以因子，稱其為旋轉(zhuǎn)因子，p為旋轉(zhuǎn)因子的指數(shù)。但各級的旋轉(zhuǎn)因子和循環(huán)方式都有所不同。為了編寫計算程序，應(yīng)先找出旋轉(zhuǎn)因子與運算級數(shù)的關(guān)系。用L表示從左到右的運算級數(shù)(L=1，2，M)。觀察圖4.2.4不難發(fā)現(xiàn)，第L級共有2L1個不同的旋轉(zhuǎn)因子。N=23=8時的各級旋轉(zhuǎn)因子表示如下：pNWpNW第4章 快速傅里葉變換(FFT) 對N=2M的一般情況，第L級的旋轉(zhuǎn)因子為3, 2, 1, 0 31, 0 20 1222/24/JWWWLJWWWLJWW

17、WLJJNpNJJNpNJJNpNLLL時時時第4章 快速傅里葉變換(FFT) 因為所以(4.2.12) (4.2.13)這樣，就可按(4.2.12)和(4.2.13)式確定第L級運算的旋轉(zhuǎn)因子(實際編程序時，L為最外層循環(huán)變量)。L-12,0,1,2,21LpJNWWJMLMLMLN222212, 2, 1, 0122LJNJNpNJWWWLMMLLMJp2第4章 快速傅里葉變換(FFT) 3 蝶形運算規(guī)律蝶形運算規(guī)律設(shè)序列x(n)經(jīng)時域抽選(倒序)后，按圖4.2.4所示的次序(倒序)存入數(shù)組A中。如果蝶形運算的兩個輸入數(shù)據(jù)相距B個點，應(yīng)用原位計算，則蝶形運算可表示成如下形式：式中下標(biāo)L表示

18、第L級運算，AL(J)則表示第L級運算后的數(shù)組元素A(J)的值（即第L級蝶形的輸出數(shù)據(jù)）。而AL1(J)表示第L級運算前A(J)的值（即第L級蝶形的輸入數(shù)據(jù)）。11( )( )()pLLLNA JAJAJB W11()( )()pLLLNA JBAJAJB W12 0,1,21; 1,2,MLLpJJLM第4章 快速傅里葉變換(FFT) 4. 編程思想及程序框圖編程思想及程序框圖 仔細(xì)觀察圖4.2.4，還可以歸納出一些對編程有用的運算規(guī)律：第L級中，每個蝶形的兩個輸入數(shù)據(jù)相距B=2L1個點；每級有B個不同的旋轉(zhuǎn)因子；同一旋轉(zhuǎn)因子對應(yīng)著間隔為2L點的2ML個蝶形?？偨Y(jié)上述運算規(guī)律，便可采用下述運

19、算方法。先從輸入端(第1級)開始，逐級進行，共進行M級運算。在進行第L級運算時，依次求出B個不同的旋轉(zhuǎn)因子，每求出一個旋轉(zhuǎn)因子，就計算完它對應(yīng)的所有2ML個蝶形。這樣，我們可用三重循環(huán)程序?qū)崿F(xiàn)DIT-FFT運算，程序框圖如圖4.2.6所示。 第4章 快速傅里葉變換(FFT) 圖4.2.6 DIT-FFT運算和程序框圖第4章 快速傅里葉變換(FFT) 另外，DIT-FFT算法運算流圖的輸出X(k)為自然順序，但為了適應(yīng)原位計算，其輸入序列不是按x(n)的自然順序排列，這種經(jīng)過M次偶奇抽選后的排序稱為序列x(n)的倒序(倒位)。因此，在運算M級蝶形之前應(yīng)先對序列x(n)進行倒序。下面介紹倒序算法。

20、第4章 快速傅里葉變換(FFT) 5 序列的倒序序列的倒序DIT-FFT算法的輸入序列的排序看起來似乎很亂，但仔細(xì)分析就會發(fā)現(xiàn)這種倒序是很有規(guī)律的。由于N=2M，因此順序數(shù)可用M位二進制數(shù)(nM1 nM2n1n0)表示。M次偶奇時域抽選過程如圖4.2.7所示。第4章 快速傅里葉變換(FFT) 第一次按最低位n0的0和1將x(n)分解為偶奇兩組，第二次又按次低位n1的0、1值分別對偶奇組分組；依次類推，第M次按nM1位分解，最后所得二進制倒序數(shù)如圖4.2.7所示。表4.2.1列出了N=8時以二進制數(shù)表示的順序數(shù)和倒序數(shù)，由表顯而易見，只要將順序數(shù)(n2n1n0)的二進制位倒置，則得對應(yīng)的二進制倒

21、序值(n0n1n2)。按這一規(guī)律，用硬件電路和匯編語言程序產(chǎn)生倒序數(shù)很容易。但用有些高級語言程序?qū)崿F(xiàn)時，直接倒置二進制數(shù)位是不行的，因此必須找出產(chǎn)生倒序數(shù)的十進制運算規(guī)律。第4章 快速傅里葉變換(FFT) 由表4.2.1可見，自然順序數(shù)I增加1，是在順序數(shù)的二進制數(shù)最低位加1，逢2向高位進位。而倒序數(shù)則是在M位二進制數(shù)最高位加1，逢2向低位進位。例如，在(000)最高位加1，則得（100），而(100)最高位為1，所以最高位加1要向次高位進位，其實質(zhì)是將最高位變?yōu)?，再在次高位加1，得到(010)。用這種算法，可以從當(dāng)前任一倒序值求得下一個倒序值。 第4章 快速傅里葉變換(FFT) 圖4.2.

22、7 形成例序的樹狀圖（N=23）第4章 快速傅里葉變換(FFT) 表4.2.1 順序和倒序二進制數(shù)對照表第4章 快速傅里葉變換(FFT) 為了敘述方便，用J表示當(dāng)前倒序數(shù)的十進制數(shù)值。對于N=2M，M位二進制數(shù)最高位的十進制權(quán)值為N/2，且從左向右二進制位的權(quán)值依次為N/4，N/8，2，1。因此，最高為加1相當(dāng)于十進制運算J+N/2。如果最高位是0(JN/2)，則直接由J+N/2得下一個倒序值；如最高位是1(JN/2), 則先將最高位變成0(JJN/2)，然后次高位加1(J+N/4)。但次高位加1時，同樣要判斷0、1值，如果為0(JN/4)，則直接加1(JJ+N/4)， 否則將次高位變成0(J

23、JN/4)，再判斷下一位；依此類推，直到完成最高位加1，逢2向右進位的運算。圖4.2.9所示的倒序的程序框圖中的虛線框內(nèi)就是完成計算倒序值的運算流程圖。 第4章 快速傅里葉變換(FFT) 形成倒序J后，將原數(shù)組A中存放的輸入序列重新按倒序排列。設(shè)原輸入序列x(I)先按自然順序存入數(shù)組A中。例如，對N=8，A(0)，A(1)，A(7)中依次存放著x(0)，x(1)，x(2)，x(7)。對x(n)的重新排序(倒序)規(guī)律如圖4.2.8所示。倒序的程序框圖如圖4.2.9所示。由圖4.2.8可見，第一個序列值x(0)和最后一個序列值x(N1)不需要重排， 每計算出一個倒序值J，便與循環(huán)語句自動生成的順序

24、I比較，當(dāng)I=J時，不需要交換，當(dāng)IJ時, A(I)與A(J)交換數(shù)據(jù)。 另外，為了避免再次調(diào)換前面已調(diào)換過的一對數(shù)據(jù)，框圖中只對IJ的情況調(diào)換A(I)和A(J)的內(nèi)容。第4章 快速傅里葉變換(FFT) 圖4.2.8 倒序規(guī)律第4章 快速傅里葉變換(FFT) 圖4.2.9 倒序程序框圖第4章 快速傅里葉變換(FFT) 第3章介紹的MATLAB函數(shù)fft是一個計算DFT的智能程序，如果計算點數(shù)N=2M，則自動按DIT-FFT快速算法計算，否則，直接計算DFT。所以，調(diào)用該函數(shù)計算DFT時，最好選取N=2M，使處理速度大大提高。第4章 快速傅里葉變換(FFT) 4.2.5 頻域抽取法頻域抽取法FF

25、T(DIF-FFT)在基2FFT算法中，頻域抽取法FFT也是一種常用的快速算法，簡稱DTF- FFT。設(shè)序列x(n)長度為N=2M，首先將x(n)前后對半分開，得到兩個子序列，其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第4章 快速傅里葉變換(FFT) 式中 將X(k)分解成偶數(shù)組與奇數(shù)組，當(dāng)k取偶數(shù)(k=2m, m=0, 1, , N/21)

26、時/21( 1)1kNkNkWk 偶數(shù)奇數(shù)，/220/2 1/20(2 )( )2( )(4.2.14)2NmnNnNmnNnNXmx nx nWNx nx nW第4章 快速傅里葉變換(FFT) 當(dāng)k取奇數(shù)(k=2m+1, m=0, 1, , N/21)時，/2 1(21)0/2 1/20(21)( )2( )2 (4.2.15)NnmNnNnnmNNnNXmx nx nWNx nx nWW令122102)()(2)()(21NnWNnxnxnxNnxnxnxnN，第4章 快速傅里葉變換(FFT) 將x1(n)和x2(n)分別代入(4.2.14)和(4.2.15)式，可得 (4.2.16)(4

27、.2.16)式表明，X(k)按奇偶k值分為兩組，其偶數(shù)組是x1(n)的N/2點DFT，奇數(shù)組則是x2(n)的N/2點DFT。x1(n)、x2(n)和x(n)之間的關(guān)系也可用圖4.2.10所示的蝶形運算流圖符號表示。圖4.2.11表示N=8時第一次分解的運算流圖。/2 11/20/2 12/20(2 )( )(21)( )NmnNnNmnNnXmx n WXmx n W第4章 快速傅里葉變換(FFT) 圖4.2.10 DTFFFT蝶形運算流圖符號第4章 快速傅里葉變換(FFT) 圖4.2.11 DIF-FFT第一次分解運算流圖（N=8）第4章 快速傅里葉變換(FFT) 由于N=2M，N/2仍然是

28、偶數(shù)，繼續(xù)將N/2點DFT分成偶數(shù)組合奇數(shù)組，這樣每個N/2點DFT又可由兩個N/4點DFT形成，其輸入序列分別是x1(n)和x2(n)按上下對半分開形成的四個子序列。圖4.2.12示出了N=8時第二次分解運算流圖。這樣繼續(xù)分解下去，經(jīng)過M1次分解，最后分解為2M1個兩點DFT，兩點DFT就是一個基本蝶形運算流圖。當(dāng)N=8，經(jīng)兩次分解，便分解為四個兩點DFT。N = 8的完整DIF-FFT運算流圖如圖4.2.13所示。第4章 快速傅里葉變換(FFT) 圖4.2.12 DIF-FFT第二次分解運算流圖（N = 8）第4章 快速傅里葉變換(FFT) 圖4.2.13 DIF-FFT運算流圖（N =8

29、）第4章 快速傅里葉變換(FFT) 這種算法是對X(k)進行奇偶抽取分解的結(jié)果，所以稱之為頻域抽取法FFT。觀察圖4.2.13可知，DIF-FFT算法與DIT-TTF算法類似，可以原位計算，共有M級運算，每級共有N/2個蝶形運算，所以兩種算法的運算次數(shù)亦相同。不同的是DIF-FFT算法輸入序列為自然順序，而輸出為倒序排列。因此，M級運算完后，要對輸出數(shù)據(jù)進行倒序才能得到自然順序的X(k)。另外，蝶形運算略有不同，DIT-FFT蝶形先乘后加(減)，而DIF-FFT蝶形先加(減)后相乘。最后要說明的是，上述兩種FFT的算法流圖形式不是唯一的。只要保證各支路傳輸比不變，改變輸入與輸出點以及中間結(jié)點的

30、排列順序，就可以得到其他變形的FFT運算流圖，各種運算流圖各有特點1。 第4章 快速傅里葉變換(FFT) 4.2.6 IDFT的高效算法的高效算法上述FFT算法流圖也可以用于計算IDFT。比較DFT和IDFT的運算公式：1010( )DFT ( )( )1( )IDFT ( )( )NknNnNknNkX kx nx n Wx nx nX k WN第4章 快速傅里葉變換(FFT) 只要將DFT運算式中的系數(shù)改變?yōu)?，最后乘?/N，就是IDFT運算公式。所以，只要將上述的DIT-FFT與DIF-FFT算法中的旋轉(zhuǎn)因子改為，最后的輸出再乘以1/N就可以用來計算IDFT。只是現(xiàn)在流圖的輸入是X(k)

31、，輸出就是x(n)。因此，原來的DIT-FFT改為IFFT后，稱為DIF-IFFT更合適；DIF-FFT改為IFFT后, 應(yīng)稱為DIT-IFFT。knNWpNWpNWknNW第4章 快速傅里葉變換(FFT) 如果希望直接調(diào)用FFT子程序計算IFFT，則可用下面的方法：由于所以，可以先將X(k)取復(fù)共軛，然后直接調(diào)用FFT子程序，或者送入FFT專用硬件設(shè)備進行DFT運算，最后取復(fù)共軛并乘以1/N得到序列x(n)。這種方法雖然用了兩次取共軛運算，但可以與FFT共用同一子程序，因而用起來很方便。*10*)(1)(1)(kXDFTNWkXNnxNkknN第4章 快速傅里葉變換(FFT) 4.3 進一步

32、減少運算量的措施進一步減少運算量的措施4.3.1 多類蝶形單元運算多類蝶形單元運算由DIT-FFT運算流圖已得出結(jié)論，N=2M點FFT共需要MN/2次復(fù)數(shù)乘法。由(4.2.12)式，當(dāng)L=1時，只有一種旋轉(zhuǎn)因子 ，所以，第一級不需要乘法運算。當(dāng)L=2 時，共有兩個旋轉(zhuǎn)因子： 和 ，因此，第二級也不需要乘法運算。在DFT中，又稱其值為1和j的旋轉(zhuǎn)因子為無關(guān)緊要的旋轉(zhuǎn)因子，如 ， ， 等。10NW10NWjWNN4/0NW2/NNW4/NNW第4章 快速傅里葉變換(FFT) 綜上所述，先除去第一、二兩級后，所需復(fù)數(shù)乘法次數(shù)應(yīng)是(4.3.1)進一步考慮各級中的無關(guān)緊要旋轉(zhuǎn)因子。當(dāng)L=3時，有兩個無關(guān)

33、緊要的旋轉(zhuǎn)因子和，因為同一旋轉(zhuǎn)因子對應(yīng)著2ML=N/2L個碟形運算，所以第三級共有2N/23=N/4 個碟形不需要復(fù)數(shù)乘法運算。依此類推，當(dāng)L3時，第L級的2個無關(guān)緊要的旋轉(zhuǎn)因子減少復(fù)數(shù)乘法的次數(shù)為2N/2L=N/2L1。這樣，從L=3至L=M共減少復(fù)數(shù)乘法次數(shù)為 (2)2MNCM0NW4/NNW第4章 快速傅里葉變換(FFT) 因此，DIT-FFT的復(fù)乘次數(shù)降至 (4.3.3) 下面再討論FFT中特殊的復(fù)數(shù)運算，以便進一步減少復(fù)數(shù)乘法次數(shù)。一般實現(xiàn)一次復(fù)數(shù)乘法運算需要四次實數(shù)乘，兩次實數(shù)加。但對這一特殊復(fù)數(shù)，任一復(fù)數(shù)(x+jy)與其相乘時，(4.3.2)222122331NNNMLLMLL(

34、2)2(3)2222MNNNCMM2/2)1 (8/jWNN第4章 快速傅里葉變換(FFT) 22(1j)(j )(jj)222()j()def2xyxyxyxyxyRjI2()222()()22RxyIxyyx 第4章 快速傅里葉變換(FFT) 只需要兩次實數(shù)加和兩次實數(shù)乘就可實現(xiàn)。這樣，對應(yīng)的每個蝶形節(jié)省兩次實數(shù)乘。在DIT-FFT運算流圖中，從L=3至L=M級，每級都包含旋轉(zhuǎn)因子 ，第L級中， 對應(yīng)N/2L個蝶形運算。因此從第三級至最后一級，旋轉(zhuǎn)因子 節(jié)省的實數(shù)乘次數(shù)與(4.3.2)式相同。所以從實數(shù)乘運算考慮，計算N=2M點DIT-FFT所需實數(shù)乘法次數(shù)為 (4.3.4)8/NNW8/

35、NNW8/NNW8/NNW134(3)22210222MNNRMNM第4章 快速傅里葉變換(FFT) 在基2FFT程序中，若包含了所有旋轉(zhuǎn)因子，則稱該算法為一類碟形單元運算；若去掉的旋轉(zhuǎn)因子，則稱之為二類碟形單元運算；若再去掉的旋轉(zhuǎn)因子，則稱為三類碟形單元運算；若再判斷處理，則稱之為四類碟形運算。我們將后三種運算稱為多類碟形單元運算。顯然，碟形單元類型越多，編程就越復(fù)雜，但當(dāng)N較大時，乘法運算的減少量是相當(dāng)可觀的。例如，N=4096時，三類碟形單元運算的乘法次數(shù)為一類碟形單元運算的75%。 1mNW jWrN(1j) 2 /2mNW第4章 快速傅里葉變換(FFT) 4.3.2 旋轉(zhuǎn)因子的生成旋

36、轉(zhuǎn)因子的生成在FFT運算中，旋轉(zhuǎn)因子，求正弦和余弦函數(shù)值的計算量是很大的。所以編程時，產(chǎn)生旋轉(zhuǎn)因子的方法直接影響運算速度。一種方法是在每級運算中直接產(chǎn)生；另一種方法是在FFT程序開始前預(yù)先計算出，m = 0，1，N/21， 存放在數(shù)組中，作為旋轉(zhuǎn)因子表，在程序執(zhí)行過程中直接查表得到所需旋轉(zhuǎn)因子值，不再計算。這樣使運算速度大大提高，其不足之處是占用內(nèi)存較多。)/2cos(NmWmN)/2sin(jNmmNW第4章 快速傅里葉變換(FFT) 4.3.3 實序列的實序列的FFT算法算法在實際工作中，數(shù)據(jù)x(n)常常是實數(shù)序列。如果直接按FFT運算流圖計算，就是把x(n)看成一個虛部為零的復(fù)序列進行計

37、算，這就增加了存儲量和運算時間。處理該問題的方法有三種。早期提出的方法是用一個N點FFT計算兩個N點實序列的FFT，一個實序列作為x(n)的實部，另一個作為虛部，計算完FFT后，根據(jù)DFT的共軛對稱性，用例3.2.2 所述的方法由輸出X(k)分別得到兩個實序列的N點DFT。第二種方法是用N/2點FFT計算一個N點實序列的DFT。第三種方法是用離散哈特萊變換（DHT）1。下面簡要介紹第二種方法。第4章 快速傅里葉變換(FFT) 設(shè)x(n)為N點實序列，取x(n)的偶數(shù)點和奇數(shù)點分別作為新構(gòu)造序列y(n)的實部和虛部，即對y(n)進行N/2點FFT，輸出Y(k)，則1210)(j)()(1210)

38、 12()()2()(2121NnnxnxnyNnnxnxnxnx，1122( )DFT( )( )011( )DFT( )( )2epopX kx nYkNkXkx njYk ， ，第4章 快速傅里葉變換(FFT) 根據(jù)DIT-FFT的思想及式(4.2.7)和(4.2.8)，可得到X(k)的前 個值： (4.3.5)式中， 。由于x(n)為實序列，因此X(k)具有共軛對稱性，X(k)的另外N/2點的值為12N210)()()(21NkkXWkXkXkN，)0(2 ),0(22211XNXXNX1210)()(*NkkXkNX，第4章 快速傅里葉變換(FFT) 計算 點FFT的復(fù)乘次數(shù)為 ，計

39、算式(4.3.5)的復(fù)乘次數(shù)為，所以用這種算法, 計算X(k)所需復(fù)數(shù)乘法次數(shù)為。相對一般的N點FFT算法，上述算法的運算效率為，當(dāng)N=2M=210時，=20/11，運算速度提高近1倍。2N) 1(4MN2N) 1(42) 1(4MNNMN) 1/(2) 1(4/2MMMNMN第4章 快速傅里葉變換(FFT) 4.4 其他快速算法簡介其他快速算法簡介快速傅里葉變換算法是信號處理領(lǐng)域重要的研究課題。由于教材篇幅和教學(xué)大綱所限，本章僅介紹算法最簡單、編程最容易的基2FFT算法原理及其編程思想，使讀者建立快速傅里葉變換的基本概念，了解研究FFT算法的主要途徑和編程思路。其他高效快速算法請讀者參考文獻

40、1、3、12。例如，分裂基FFT算法、離散哈特萊變(換DHT)、基4FFT、基8FFT、基rFFT、混合基FFT，以及進一步減少運算量的途徑等內(nèi)容，對研究新的快速算法都是很有用的。本節(jié)簡要介紹其他幾種快速算法的運算量及其主要特點，以便讀者選擇快速算法時參考。第4章 快速傅里葉變換(FFT) 從理論上講，不同基數(shù)的FFT算法的運算效率不同，實際中最常用的是基2FFT、基4 FFT、分裂基FFT和DHT 1。為此，下面簡要介紹后三種FFT算法的特點和運算效率，以擴展讀者的視野。其具體算法請參考文獻1、12。在基rFFT算法中，基4FFT算法運算效率與基8FFT很接近，但基4FFT算法實現(xiàn)程序簡單，

41、且判斷開銷少?？梢宰C明，當(dāng)FFT的基大于4時，不會明顯降低計算量?；?FFT要求N=4M，M為自然數(shù)。其復(fù)數(shù)乘法次數(shù)為12（4.4.1） 3lb()8NNCM(基4)第4章 快速傅里葉變換(FFT) 其中未計入乘以j和1的計算。比較基2FFT的復(fù)數(shù)乘法次數(shù) ，基4FFT的復(fù)數(shù)乘法次數(shù)減少25%。1984年，法國的杜梅爾（P.Dohamel）和霍爾曼（H. Hollmann）將基2分解和基4分解糅合，提出了分裂基FFT算法，其復(fù)數(shù)乘法次數(shù)接近FFT理論最小值，但其運算流圖卻與基2FFT很相似，編程簡單，運算程序也很短，是一種很實用的高效算法。分裂基FFT算法復(fù)數(shù)乘法次數(shù)為2 CM(分裂基)= （

42、4.4.2）NNCMlb21)2(22lb()1399MNNN 第4章 快速傅里葉變換(FFT) 只考慮（4.4.2）式的第一項，分裂基FFT算法的復(fù)數(shù)乘法次數(shù)就比基2FFT減少33%，比基4FFT減少11%。應(yīng)當(dāng)說明，在比較時，未考慮（4.4.2）式后2項減少的運算量，所以分裂基FFT算法的效率更高。由以上比較可見，分裂基FFT算法的效率最高，所以得到廣泛應(yīng)用。但是，對實序列x(n)，上述各種FFT算法仍將其看成虛部為零的復(fù)序列存儲和計算。而一次復(fù)數(shù)乘法需要四次實數(shù)乘法和二次實數(shù)加法。所以，必然浪費存儲資源和增加多余的運算量。我們知道，實序列的N點DFT具有共軛對稱性，即*()( ), 0,1,2,1X NkXkkN第4章 快速傅里葉變換(FFT) 所以，只要計算出X（k）的前面N/2個值，則其后面的N/2個值可以由對稱性求得。因此，F(xiàn)FT算法得到的N個X（k）值有一半是多余的。由以上分析可見，對實序列一定存在更高效的快速算法。離散哈特萊變換（DHT）就是針對實序列的一種高效變換算法，相對一般的FFT