【文章內容簡介】 就是 DITFFT這一算法。 設序列 x(n)的長度為 N，并且有以下的條件成立 N=2M， M為自然數 1(r)和 2(r)是 x(n)按 n的奇偶性分解成的兩個 N/2 點的子序列，如下式所示 12,.. .1,0),2()(1 ??? Nrrxrx 12,...,1,0),12()(2 ???? Nrrxr 那么 x(n)的 DFT 為 ?? ?? ?? n knNn knN WnxWnxkX )()()( ?? ?? ??? ?? 12/ 0 )12(212/ 0 2 )12()2( N r rkNN r krN WrxWrx ?? ???? ? 12/ 0 2212/ 0 1 )()( N r krNN r kN WrxWrx 由于 krNkrNjkrNjkrN WeeW 2 2/22222 ??? ??ππ 所以 1,.. .,1,0)()()()()( 2112/0 2/212/0 2/1?????? ?? ????NkkXWkXWrxWWrxkW kNNrkrNkNNrkrN （ ） 其中)(1kX和)(2k分別為 1rx和(2r的 N/2 點 DFT，即 理工大學學士學位論文 8 )]([)()()]([)()(212/02/22112/02/11rxDFTWrxkXrxDFTWrxkXNrkrNNrkrN?????????? （ ） （ ） 又由于)(1kX和)(2k都是以 N/2 為周期，且 kNNkN WW ??? 2 所以 X(k)又可 以表示為如下所示的表達式 12,...,1,0)()()( 21 ???? NkkXWkXkX kN （ ） 12,...1,0)()()2( 21 ????? NkkXWkXNk kN （ ） 這樣一個 N點的 DFT就被拆分成為了兩個 N/2點的 DFT。式 ()和式 ()說明了原 N點的 DFT和這兩個 N/2點的 DFT之間的關系。通常為了后續(xù)說明的方便，和其它許多文獻一樣，在本文中也將式 ()和式 ()的運算用圖 。因為這個流圖符號形狀酷似一只蝴蝶，所以稱其為蝶形運算符號。 圖 采用蝶形運算符號的這種圖示方法，可以用圖 2． 2來表示前面所講到的運算。在圖 ， N=23=8，式 ()給出了 X(O)～ X(3)的計算方法，而式 ()給出了 X(4)～ X(7)的計算方法。由圖 ，要完成一個蝶形運算，需要一次復數乘法和兩次復數加法運算。由圖 ，經過一次分解后，計算一個 N點 DFT共需要計算兩個 N/2點DFT可和 N/2個蝶形運算。由前面的說明可以 知道，計算一個 N/2點 DFT需要 (N2)2次復數 乘 法 和 N/2(N/21) 次 復 數 加 法 。 那 么 按 圖 計算 N 點 DFT 共需要 2(N ／2)2+N/2=N(N+1)/2≈N2/2（ N1） 次復數乘法和 N(N/21)+2N/2=N2/2次復數加法運算。通過對比可以看出，只進行過這樣的次分解就使得運算量減少了近一半，充分說明了這樣分解對減少 DFT的運算量是十分有效的。由這里 N=2M， N/2仍然是偶數，為了使得計算理工大學學士學位論文 9 量能夠得到進一步的減少，可以仿效前面的做法對 N/2點 DFT再做進一步分解。 圖 N點 DFT的一次時域抽取分解圖 (NtiS) 與第一次分解相同，1(3x和 4為)rx按奇偶分解成的兩個長為 N/4的子序列，即 14,.. .,1,0,)12()( )2()(1423 ???????? Nllxlx lxlx 那么，)(1kX又可表示為 ?? ?? ??? ??? 14/ 0 )12( 2/114/ 0 2 2/11 )12()2()( N i lkNN i klN WlxWlxkX ?? ???? ?? 14/ 0 4/42/14/ 0 4/3 )()( N i klNkNN i klN WlxWWlx 12/,.. .,1,0),()( 42/3 ???? NkkXWkx kN （ ） 其中 ??????????14/044/414/034/33)]([)())]([)()(NiklNNiklNlxDFTWlxklxDFTWlxkx 同理，由)(3kX和)(4k的周期性和 Wm2/N尼的對稱性2/2/4/ NkNNk WW ???最后得到： 理工大學學士學位論文 10 14/,.. .,1,0,)()()4/( )()()(42/3142/31 ?????????? ?? NkkXWkXNkX kXWkXkXkNkN （ ） 同理可得 14/,.. .,1,0,)()4/( )()()(62/5262/52 ?????????? ?? NkkXWkXNkX kXWkXkXkNkN （ ） 其中有 14/,.. .1,0,)12()()2()()]([)()()]([)()(2625614/04/66514/04/55??????????????????NllxlxlxlxlXDFTWlxkXlXDFTWlxkXNiklNNiklN 這樣，如圖 ，經過第二次的分解，一個 N/2點的 DFT就被拆分成為了兩個 N/4點的 DFT了。式 ()和式 (2． 11)說明了原 N/2點的 DFT和這兩個 N/4點的 DFT之間的關系。依次類推，經過 M1次分解，最后將 N點 DFT分解成 N/2個 2點 DFT。將前面兩次分解的過程綜合起來，就得到了一個完整的 8點 DITFFT運算流圖，如圖 。圖中 用到關系式mkNk m WW ?/。圖中的輸入序列不是順序的，但是后面會看到，其排列是有規(guī)律的。 圖 N點 DFT的第二次時域抽取分解圖 (N_8) 理工大學學士學位論文 11 圖 N點 DITFFT運算流圖 （ N=8） DITFFT算法與直接計算 DFT運算量的比較 由 DITFFT算法的分解過程及圖 ， N=2M時，其運算流圖應該有 M級蝶形，每一級都由 N/2蝶形 運算構成。每一級運算都需要 N/2次復數乘和 N次復數 an(每個蝶形需要兩次復數加法 )。所以， M級運算總共需要的復數乘次數為 NNMNC M 2log22)2( ?? 復數加次數為 NNNMC A 2log)2( ?? 而由前面的介紹，直接計算 N點的 DFT需要 N2次復數乘法以及 N(N1)次復數加法運算。 N1時， N(N1)是約等于 N2的。當 N=210=1024時，可以求得直接計算 N點的 DFT和使用基 2DITFFT算法的所需乘法次數的比值為 )2/( 22 ??NN N 這樣，運算效率就提高了 200多倍。圖 FFT算法與直接計算 DFT所需乘法次數的比較曲線。由此圖更加直觀地看出 FFT算法的優(yōu)越性，從圖 ， N越大時，優(yōu)越性就越明顯。 理工大學學士學位論文 12 圖 FFT算法與直接計算 DFT所需乘法次數的比較曲線 DITFFT的一些運算規(guī)律 DITFFT運算中是存在一些規(guī)律的，下面簡單的介紹一下這些規(guī)律。 (1)原址計算 由 圖 ， DITFFT的運算過程是很有規(guī)律的。 N=2M點的 FFT共需要進行進行 M級運算，每級由 N/2個蝶形運算組成。在同一級運算中，每一個蝶形運算是有兩個輸入和兩個輸出的。這兩個輸入、輸出數據節(jié)點在同一水平線上，并且它們只對本蝶形運算有效，對其它的蝶形運算是無效的。因為這樣，當計算完一個蝶形以后，所得輸出數據可立即存入原輸入數據所占用的存儲單元 i以此類推，當 M級運算都計算完畢以后，原來存放輸入序列數據的 N個存儲單元中便依次存放了 X(k)的 N個值。這種利用同一存儲單元存儲蝶形運算計算輸入、輸出數據的 方法就稱為原址計算。很明顯原址計算可以節(jié)省存儲資源，從而降低硬件的成本。 (2)旋轉因子的變化規(guī)律 由 8點 DITFFT的運算流圖可以推得在 N點 DITFFT運算流圖中，每級都有 N/2個蝶形。每個蝶形都要乘以因子pW。p被稱為旋轉因子，其中 p為旋轉因子的指數。 通過觀察圖 ，第 L級共有 2L1個不同的旋轉因子。 N=23=8時的各 級旋轉因子表示如下： 理工大學學士學位論文 13 3,2,1,0,31,0,20,1222/24/????????????JWWWLJWWWLJWWWLJJNpNJJNpNJJNpNLLL時，時，時， () 對 N=2M的一半情況，第 L級的旋轉因子為 LMLJNJNpNMLMLMLLJpNJpJWWWNJLWWLMML??????????????????212,.. .,2,1,0,222212,.. .,2,1,0,12212 （ ） (3)蝶形運算規(guī)律 設序列 x(n)經時域抽選 (倒序 )后，存入數組 X中。如果蝶形運算的兩個輸入數據相距 B個點，應用原位計算，則蝶形運算可表示成如下形式： pNLLpNLLWBJXJXBJ WBJXJXJX )()()( )()()( 11 11 ????? ???? ?? ?? 其中 p=J2ML； J=0,1,...,2L1。L=1,2,...,M 下標 L表示第 L級運算， XI， (J)則表示第 L級運算后數組元素 X(J)的值。 (4)序列的倒序 仔細分析可以發(fā)現看似毫無規(guī)律可循的 DITFFT算法的輸入序列的排序其實是很有規(guī)律的。由于 N=2M，所以順序數可用 M位二迸制數 (0121 ... nnnn MM ??)表示。 當 N=8時，這種規(guī)律就可以用圖 。 圖 形成倒序的樹狀圖 (N23) 理工大學學士學位論文 14 表 順序和倒序二進制數對照表 順序 倒敘 十進制數 I 二進制數 二進制數 十進制數 J 0 000 000 0 1 001 100 4 2 010 010 2 3 011 110 6 4 100 001 1 5 101 101 5 6 110 011 3 7 111 111 7 DITFFT的輸入順序輸出倒序的信號流圖 DITFFT的信號流圖的形式不是唯一的，它還有多種表現形式。圖 DITFFT的一種變形的運算流圖，其中蝶形運算的旋轉因子、運算量與圖 。從圖中很容易看出它是一種順序輸入，倒序輸出的方式。這種結構的信號流圖有一個非常特別的優(yōu)點就是前一級的旋轉因子剛好是后一級上一半蝶形運算的旋轉因子，且順序不變，如果旋轉因子的計算采用查表法，只要構造出一個 N/2點的NpW，就可以 用它來計算 N、 N/ N/ ...長度的 FFT。因此在大型數據處理系統(tǒng)的 FFT算法中，較多采用的是圖 法。本課題也是采用的圖 。 圖 DITFFT的順序輸入倒序輸出形式 理工大學學士學位論文