第5章快速傅立葉變換(FFT)

1、第五章快速傅立葉變換（FFT）主要內(nèi)容45.1 引言45.2 基2FFT的時間抽取算法及蝶形圖45.3 基2FFT的頻率抽取算法45.4 進(jìn)一步減少計算量的措施45.5 基4FFT的頻率抽取算法45.6 分裂基FFT算法45.7 多種形式的FFT算法45.8 結(jié)束語5.1 引言(1)離散傅立葉變換（DFT） (2)意義 DFT是離散譜。從理論上解決了離散譜的計算問題，具有重要的理論意義。(3)計算量和存儲量分析 計算量用復(fù)數(shù)加法和復(fù)數(shù)乘法次數(shù)表示。與N2成正比。 復(fù)數(shù)加法次數(shù)：N(N-1)次。復(fù)數(shù)乘法次數(shù)：N2次。 存儲量用占用隨機(jī)存取存儲器和只讀存儲器的數(shù)量表示。 RAM單元：N+N=2N個

2、。 ROM單元：N2個。 結(jié)論：計算量和存儲量，隨著數(shù)據(jù)量的增加都迅速增大。應(yīng)用困難。(4)解決方法快速算法 J.W.Cooley (IBM), J.W.Tukey(MIT), “機(jī)器計算傅立葉級數(shù)的一種算法”，Math. Computation, Vol.19,1965.稱為 Cooley and Turkey 算法。 以后，出現(xiàn)Sande Tukey算法，P.Dohamel and H.Hollmann的分裂基算法。1,.,1 , 0,)(1)()()(1010NknWkXNnxWnxkXNkknNNknkN1,.,1 , 0,)(1)()()(102102NknekXNnxenxkXNk

3、nkNjNknkNj5.2 基2FFT的時間抽取算法及蝶形圖（1）(1) Cooley and Turkey 算法的基本思想 W因子的特性： 基本思想：分解。 分解的唯一條件：數(shù)據(jù)長度滿足N=2r。否則，補(bǔ)零解決。(2)分解公式的推導(dǎo)(按奇偶序號分解，輸入每2點抽1個值) kNNkNkNNkNkNlNkNWWWWWW2，；對稱性：周期性：計算?？捎枚绦蛄锌梢苑纸?，長序列的結(jié)論：，得和進(jìn)一步，利用，其中：所以：由于：則：，即、為兩個短序列。按奇偶序號分解，設(shè)一個長序列DFTDFTDFTNkkXWkXNkXNkkXWkXkXWWWWWnxkXWnxkXNkkXWkXWnxWWnxkXWWWnxWW

4、nxWnxWnxWnxkXNnnxnxNnnxnxnxnxnxNnxDFTkXnxkNkNkNNkNkNNkNNnknNNnknNkNNnknNkNNnknNknNknNNnknNkNNnknNNnnkNNnknNNnknNM12/,.,1 , 0),()()2/(12/,.,1 , 0),()()()()()()(1,.,1 , 0),()()()()()()() 12()2()()(12/,.,1 , 0),12()(12/,.,1 , 0),2()()()()(2),()()(21212/2/2/2/12/02/2212/02/112112/02/212/02/12/212/02212/

5、02112/0)12(12/02102121兩點數(shù)據(jù)為止更短序列短序列長序列分解分解分解 5.2 基2FFT的時間抽取算法及蝶形圖（2）(3) FFT定理或分解公式 (4) 蝶形圖和一次分解圖：用蝶形圖計算DFT。運算量:一次乘，兩次加。 一次分解的計算量蝶型運算來計算，即可用兩個短數(shù)據(jù)的那么，長數(shù)據(jù)的且，即、解為兩個短序列把長序列按奇偶序號分。，設(shè)一個長序列12/,.,1 , 0),()()2/(12/,.,1 , 0),()()(DFTDFT)()()()(,12/,.,1 , 0),12()(12/,.,1 , 0),2()()()(2),()()(212122112121NkkXWkX

6、NkXNkkXWkXkXnxDFTkXnxDFTkXNnnxnxNnnxnxnxnxNnxDFTkXnxkNkNM倍倍。例；乘次數(shù)加次數(shù)998. 1,2,10242/2/)2/(2:2/) 12/(2/2:222RRNNNNNNNN 蝶形運算符號 X(k+N/2) X(k) X1(k) X2(k) kNWX(k+N/2) X(k) - + kNWX1(k) X2(k) N 點 DFT 的一次分解圖(k=0,1,2,3) N/2 點 DFT X(7) X(6) X(5) X(4) X(3) X(2) X(0) 3NWx(4) x(2) x(0) x(6) x(5) x(3) x(1) x(7)

7、X1(1) X1(0) X1(3) X1(2) X2(1) X2(0) X2(3) X2(2) 0NWX(1) 1NW2NW N/2 點 DFT 5.2 基2FFT的時間抽取算法及蝶形圖（3）(5) 8點數(shù)據(jù)時間抽取(Decimation-In-Time)算法的完整分解過程和蝶形流程圖 蝶形圖（蝶形運算流圖）結(jié)構(gòu)：N/2行，M=log2 N 列。)7()3() 1 ()7()3()0()5() 1 () 1 ()5() 1 ()0(1 , 0,)()()2()()()()6()2() 1 ()6()2()0()4()0() 1 ()4()0()0(1 , 0,)()()2()()()(3 ,

8、2 , 1 , 0,)()()4()()()(0260260250256452645202402402302344314431281281xWxXxWxXxWxXxWxXkkXWkXkXkXWkXkXxWxXxWxXxWxXxWxXkkXWkXkXkXWkXkXkkXWkXkXkXWkXkXkkkkkk)()7()3()()5() 1 ()()7()5()3() 1 ()()6()2()()4()0()()6()4()2()0()()7()6()5()4()3()2() 1 ()0(652431kXxxkXxxkXxxxxkXxxkXxxkXxxxxkXxxxxxxxx 8 點 DIT-FFT

9、 的信號流圖 04/NWX6(1) X6(0) 12/NW12/NWX(7) X(6) X(5) X(4) X(3) X(2) X(0) 3NW04/NWx(2) X3(1) X3(0) x(4) x(0) 04/NWX4(1) X4(0) x(6) x(3) 04/NWX5(1) X5(0) x(5) x(1) x(7) 02/NWX1(1) X1(0) X1(3) X1(2) 02/NWX2(1) X2(0) X2(3) X2(2) 0NWX(1) 1NW2NW5.2 基2FFT的時間抽取算法及蝶形圖（4）(6)時間抽取算法的特點 命名：Cooley-Turkey算法，時間抽取算法（簡稱D

10、IT-FFT: Decimation In Time FFT） DIT-FFT的運算量（結(jié)構(gòu)：N/2行，M=log2 N 列） 旋轉(zhuǎn)因子(twiddle factor)變化規(guī)律100200:1024log1,log2loglog22222RRNNNRNNRNNNN；比較：，加法：乘法：，按規(guī)律查表。個，存共產(chǎn)生旋轉(zhuǎn)因子表，：編程時，查表：預(yù)先結(jié)論個旋轉(zhuǎn)因子。級的轉(zhuǎn)因子：按公式產(chǎn)生：編程時，直接產(chǎn)生旋結(jié)論，：，：則例如：計算公式或規(guī)律；所以：由于：稱指數(shù)。，個，為，左到右）旋轉(zhuǎn)因子有級（第設(shè)ROMNNmWLWWWWLWWWWLWWLMNJpJWWWNpJWWMLLNmNLNNNNNNNNNNLM

11、LJNJNpNMLMLMLLJpNLMLMLML2, 12,.,1 , 0,221321, 3, 8)(212,.,1 , 0,222212,.,1 , 0,2,.2 , 1,213210212/002/004/1221215.2 基2FFT的時間抽取算法及蝶形圖（5） 原址計算（同址計算：In place computation ）：指輸入數(shù)據(jù)、中間、最終結(jié)果可存放在同一存儲單元。 序列的整序（倒序） 整序：字位倒置規(guī)則（bit reversed） 硬件電路和匯編程序用2進(jìn)制倒序， 而高級語言則要換算成10進(jìn)制。7111111730111106510110151001100461100113

12、201001024100001100000000亂序倒置二進(jìn)制順序2/NROMNRAM單元單元存儲量：。個存儲單元，存入結(jié)論：同址運算只需要差）。序距離（即存儲器序號表示兩個輸入數(shù)據(jù)的順級運算，表示式中，表示為那么蝶形運算和存儲可。，存儲器表示為數(shù)組時間抽取倒序后，存入設(shè)序列放在該蝶形輸入處。一個蝶形運算結(jié)果可存與前一級結(jié)果有關(guān)，每注意到：每一級運算只RAMNBLLMLJJpWBJXJXBJXWBJXJXJXNAAAXnxLLMpNLLLpNLLL,.,2 , 1; 12,.,1 , 0;2)()()()()()()(.) 1 ()0()(111115.2 基2FFT的時間抽取算法及蝶形圖（6

13、）(7) 16點數(shù)據(jù)時間抽取算法的完整信號流圖。 32/NW 22/NW12/NW32/NW22/NWX2(7) X2(6) X2(5) X2(4) X2(3) X2(2) X2(1) X2(0) X1(7) X1(6) X1(5) X1(4) X1(2) X1(3) X1(1) X1(0) 7NW6NW5NW4NW3NW2NW1NW0NWX(15) X(14) X(13) X(12) X(11) X(10) X(8) X(9) 14/NW04/NW08/NW08/NW08/NW08/NWx(5) x(9) x(1) x(13) x(7) x(11) x(3) x(15) 16 點 DIT-F

14、FT 的信號流圖 08/NWX10(1X10(014/NW14/NWX(7) X(6) X(5) X(4) X(3) X(2) X(0) 08/NWx(4) X7(1) X7(0) x(8) x(0) 08/NWX8(1) X8(0) x(12) x(6) 08/NWX9(1) X9(0) x(10) x(2) x(14) 04/NWX3(1) X3(0) X3(3) X3(2) 04/NWX4(1) X4(0) X4(3) X4(2) 02/NWX(1) 14/NW04/NW02/NW12/NW5.3 基2FFT的頻率抽取算法（1）(1) 基2FFT的頻率抽取(Decimation-In-F

15、requency)算法的推導(dǎo)個值。點抽部分，每的偶序號部分和奇序號計算結(jié)果是原序列可用短序列直接算。，則原、短序列結(jié)論：序列對半分構(gòu)成則：令：則：為奇數(shù)為偶數(shù)，并注意到：和的奇偶序列記為將則：為短序列，即。將序列前后對半分開，設(shè)一個序列12)()()() 12()()2(12/,.,1 , 0,)2()()(12/,.,1 , 0),2()()(12/,.,1 , 0,)2()()2()() 12(12/,.,1 , 0,)2()()2()()2(, 1, 1) 1() 12()2()()2()()()()()(1,.,12/, 2/),()(12/,.,1 , 0),()(2),()()(2

16、112/02/212/02/12112/02/12/0)12(12/02/12/022/12/02/12/12/010DFTDFTnxnxWnxrXWnxrXNnWNnxnxnxNnNnxnxnxNrWWNnxnxWNnxnxrXNrWNnxnxWNnxnxrXkkWrXrXkXWNnxWnxWnxWnxWnxkXNNNnnxnxNnnxnxNnxDFTkXnxNnnrNNnnrNnNnNNnnrNNnnrNNnnrNNnnrNkkNNNnknNkNNNNnknNNnknNNnknNbfM5.3 基2FFT的頻率抽取算法（2）(2)分解公式(3)蝶形圖、蝶形運算：兩個短序列x1(n)、x2(n

17、)可成對運算。 蝶形運算符：一次乘法，兩次加法。先加減，后乘。而DIT-FFT：先乘，后加減。12/,.,1 , 0,)() 12()()2(12/,.,1 , 0,)2()()()2()()(2),()()(12/02/212/02/121NrWnxrXWnxrXDFTNnWNnxnxnxNnxnxnxNnxDFTkXnxNnrnNNnrnNnNM計算，即可用這兩個短序列直接那么原序列的蝶型運算并構(gòu)成兩個短序列，即將序列前后對半分解，。，設(shè)一個序列 x(n+N/2) x1(n)=x(n)+x(n+N/2) nNWx2(n)=x(n)-x(n+N/2)WnN x(n) DIF-FFT 的蝶形運

18、算符號 5.3 基2FFT的頻率抽取算法（3）(4)一次分解圖(n=0,1,2,3) 一次分解的計算量與時間抽取算法相同。(5)基本思想 長序列分解成短序列。從過程看，將輸入數(shù)據(jù)對半分開為兩個序列。從結(jié)果看，將DFT的輸出X(k)按照奇、偶序號分解為兩個序列，每2點抽1個值。 命名：基2FFT的頻率抽取算法（Sand-Turkey算法，簡稱DIF-FFT: Decimation In Frequency FFT）。；乘次數(shù)加次數(shù)2/2/)2/(2:2/) 12/(2/2:222NNNNNNN X(2) X(7) X(5) X(3) X(1) X(6) X(4) X(0) 3NW2NW1NWx2

19、(3) x2(2) x(2) x1(1) x1(0 x(1) x(0 x1(3) x1(2) x(3) x(6) x2(1) x2(0) x(5) x(4) x(7) N/2 點 DFT 0NW8 點 DIF-FFT 的次分解圖 N/2 點 DFT 點數(shù)據(jù)為止更短用蝶形構(gòu)成短序列個短序列分解思想：長序列分解分解分解2)(2/2 NN5.3 基2FFT的頻率抽取算法（4）(6) 8點數(shù)據(jù)頻率抽取算法的完整分解過程和蝶形流程圖 完整分解過程0666605555044440333322622511411321)1 ()0()7() 1 ()0()3()1 ()0()5() 1 ()0() 1 ()1

20、 ()0()6() 1 ()0()2()1 ()0()4() 1 ()0()0(1 , 0,)2()()()2()()(1 , 0,)2()()()2()()(32 , 1 , 0,)2()()()2()()(NNNNnNnNnNWxxXxxXWxxXxxXWxxXxxXWxxXxxXnWNnxnxnxNnxnxnxnWNnxnxnxNnxnxnxnWNnxnxnxNnxnxnx，)7()3()34() 1 ()0()5() 1 () 14() 1 ()0(3210)7()5()3() 1 () 12()3()2() 1 ()0()6()2()24() 1 ()0()4()0()4() 1 (

21、)0(3210)6()4()2()0()2()3()2() 1 ()0()7()6()5()4()3()2() 1 ()0()()7()6()5()4()3()2() 1 ()0(6655222244331111XXrXxxXXrXxxXXXXrXxxxxXXrXxxXXrXxxXXXXrXxxxxXXXXXXXXkXxxxxxxxx5.3 基2FFT的頻率抽取算法（5） 蝶形流程圖（結(jié)構(gòu)：N/2行，M=log2 N 列） (7)運算特點：運算量、旋轉(zhuǎn)因子規(guī)律、同址運算、存儲量、整序規(guī)則 整序規(guī)則：字位倒置規(guī)則。(8)與時間抽取算法比較 分解思想，計算量存儲量，整序規(guī)則相同。分解方法，碟型圖結(jié)

22、構(gòu)，蝶形符號的運算順序，輸入、輸出順序不同。NNRNNRNNNN2222log1,log2loglog2；比較：，加法：乘法：2/NROMNRAM單元單元存儲量： 0NW3NW2NW1NW0NWX(4) x4(1) x6(1) x6(0) x5(0) x4(0) x3(0) 0NWx2(3) x2(2) 2NW2NWX(7) X(3) X(5) X(1) X(6) X(2) X(0) x(2) x1(1) x1(0 x(1) x(0 0NWx1(3) x1(2) x(3) x(6) 0NWx2(1) x2(0) x(5) x(4) x(7) 0NWx3(1) 0NWx5(1) 0NW8 點 D

23、IF-FFT 的信號流圖 5.3 基2FFT的頻率抽取算法（6）(9)IDFT(Inverse Discrete Fourier Transform)的快速算法（高效算法IFFT） DFT和IDFT的定義式 方法1：1,.2 , 1 , 0)(1)()(1,.2 , 1 , 0)()()(1010NnWkXNkXIDFTnxNkWnxnxDFTkXNknkNNnnkN，*10*10*10)(1)(1)()(1)()(1)()(kXDFTNWkXNnxWkXNnxWkXNkXIDFTnxNknkNNknkNNknkN再取共軛：取共軛：注意到：原理推導(dǎo)：。，得到）結(jié)果取共軛，并乘以）對；的程序，作

24、）調(diào)用；的共軛，得到）先取分方便。共用子程序，使用十子程序計算方法：直接調(diào)用)(/123)(2)()(1*nxNFFTkXFFTkXkXIDFTFFT5.3 基2FFT的頻率抽取算法（7） 方法2 防止溢出：1/N=(1/2)M，將1/N分配到M級，每一個蝶形輸出支路乘因子1/2。乘法次數(shù)增加。.)()()()(3/12;1/12IFFTDITIFFTFFTDIFIFFTDIFnxkXIFFTFFTDITnxkXNWWFFTDIFFFTDITNIDFTDFTFFTpNpN稱后算法改為同理，。故稱順序亂序，輸出，輸入改為特點：。，輸出就是）輸入；）算法的輸出再乘以改為算法中，將與）在。號和系數(shù)的

25、差別：旋轉(zhuǎn)因子的符和序。的蝶形圖，成為專用程：修改方法ss 1/N 1/N 1/N 1/N 1/N x5(1) 3NW2NW1NW0NWX(4) x4(1) x6(1) x6(0) x5(0) x4(0) x3(0) 0NWx2(3) x2(2) 2NW2NWX(7) X(3) X(5) X(1) X(6) X(2) X(0) x(2) x1(1) x1(0 x(1) x(0 0NWx1(3) x1(2) x(3) x(6) 0NWx2(1) x2(0) x(5) x(4) x(7) 0NWx3(1) 0NW0NWDIF-FFT 修改為 DIT-IFFT 的信號流圖 1/N 1/N 1/N 5

26、.4 進(jìn)一步減少計算量的措施（1）(1)多種類型的蝶形單元運算 .110)2132(22)2(242/13212224)(22),(22)()(2222)1 ()(2/2)1 (31318/8/8/運算。四類：利用特殊復(fù)數(shù)。三類：去掉一般算法。二類：去掉含一類蝶形單元運算：實數(shù)乘法次數(shù)為個蝶。，每個對應(yīng)個級以后，每級。級，無、次實數(shù)加。次實數(shù)乘和復(fù)數(shù)運算需要次實數(shù)加。而采用特殊次實數(shù)乘和分析及結(jié)論：復(fù)數(shù)乘需，其中與其相乘，得是特殊復(fù)數(shù)。任一復(fù)數(shù)特殊復(fù)數(shù)運算：jWWMNNNMNNWWyxIyxRjIRyxjyxjjyxjWpNpNMLLMLLLNNNNdefNN2)3(22)2(23)2(221

27、2/2 ,2/1 ,:23, 1:3, 1:21:1, 3, 8, 111).(3114/03210212/002/004/4/2/0MNNMNMNNNWWWjWWWLjWWWWLWWLMNjWWWjWWfactortwiddletrivialMLLLLNNNNNNNNNNNNNNNNNNpNpN級以后，復(fù)乘法次數(shù)為；再去掉級后，復(fù)數(shù)乘法次數(shù)為、去掉法。旋轉(zhuǎn)因子，減少復(fù)數(shù)乘結(jié)論：去掉無關(guān)緊要的個蝶形單元運算。個對應(yīng)個蝶個對應(yīng)和個無關(guān)緊要級后，每級，規(guī)律：無關(guān)緊要旋轉(zhuǎn)因子分布例如：等。，。如，：無關(guān)緊要旋轉(zhuǎn)因子5.4 進(jìn)一步減少計算量的措施（2）(2)旋轉(zhuǎn)因子的生成(3)實序列的FFT算法 個。

28、存存放在數(shù)組中。占用內(nèi)預(yù)先算出旋轉(zhuǎn)因子表查表方法計算量大。直接產(chǎn)生直接產(chǎn)生方法：編程時旋轉(zhuǎn)因子：2/, 12/,.,1 , 0,:,)2sin()2cos(2NNmWmNjmNeWmNmNjmN計算。的復(fù)序列直接用看成虛部為：將方法FFTnx0)(1倍。運算速度提高時當(dāng)算法，相對一般運算效率即算另一半用共軛對稱性計是實序列由于分解公式由所以得到：其中共軛對稱、反對稱那么：和即并構(gòu)造復(fù)序列分解為奇數(shù)偶數(shù)點序列點的的對稱性。將：利用方法1,11/20,10242).1/(2:12/,.,1 , 0),()(,)(12/,.,1 , 0),()()(:)()( 5 . 0)()()()( 5 . 0

29、)()()()( 5 . 0)()()()( 5 . 0)()(),)()()()()()()(; 12/,.,1 , 0),12()()2()(),(,)(210*21*22*11*2*12121NMMFFTNkkXkNXnxNkkXWkXkXFFTkNYkYjnxDFTkXkNYkYnxDFTkXkNYkYnjxDFTkXkNYkYnxDFTkXkXkXnyDFTkYnjxnxnyNnnxnxnxnxnynxNDFTkNopepopep5.5 基4FFT的頻率抽取算法(1)(1)基4FFT算法的推導(dǎo)(N=4,16,64,)每個式子都是每4點抽1個值，稱基4頻率抽取算法。進(jìn)一步推導(dǎo)得到分解公

30、式 14/04/314/04/14/04/214/04/14/0340240400404)4/14/0304014/030)4/(00014/314/32/12/4/14/010)43()4()2()()34()43()4()2()() 14()43()4()2()()24()43()4()2()()4(, 14/,.,1 , 0, 3414, 24,4)43()2()4()()()4()4()(3 , 2 , 1 , 014,.,1 , 04)()()()()(:41,.,1 , 0)()(4000000NnrnNnNNnrnNnNNnrnNnNNnrnNNnknNkkkklNklNNnlk

31、lknNNnllNnkNNNnknNNNnknNNNnknNNnknNNnknNMWWNnxNnxjNnxnxrXWWNnxNnxjNnxnxrXWWNnxNnxNnxnxrXWNnxNnxNnxnxrXNrrkrkrkrkWWNnxWNnxWNnxWnxWWWlNnxWWlNnxkXlNnlNnnWnxWnxWnxWnxkXNnWnxkXN有及分別令，有，其中令個短序列。將序列順次等分為，設(shè)5.5 基4FFT的頻率抽取算法(2)分解思想：與下級連接。個乘二級輸出一級輸出。個純虛數(shù)乘，即個蝶形，只有蝶形圖，包括基本運算單元是。點的個分成點的結(jié)論則：得令：WnxnxnxnxjDFTNDFTNWW

32、nxrXWWnxrXWWnxrXWnxrXNnnxnxnxnxnxnxNnnxnxnxnxnxnxNnNnxNnxjnxNnxNnxnxNnNnxnxnxNnxnxnxNnrnNnNNnrnNnNNnrnNnNNnrnN3),()(),()(1444/4:)()34()() 14()()24()()4(14/,.,1 , 0,)()()()()()(14/,.,1 , 0,)()()()()()(:14/,.,1 , 0,)43()4()()43()4()(, 14/,.,1 , 0,)2()()()2()()(854114/04/3814/04/714/04/2614/04/54284273

33、163154321 x5(n) x6(n) x7(n) x8(n) nNW3nNWnNW2x3(n) -j x(n+N/4) x(n+3N/4) x(n+N/2) x1(n) x2(n) x(n) 基 4FFT 的基本運算單元4 蝶形圖 x4(n) 四點數(shù)據(jù)為止更短個個、二級蝶型構(gòu)成個、一級蝶形構(gòu)成順序個短序列長序列分解分解分解)444(4/4NN5.5 基4FFT的頻率抽取算法(3)(2)N=16，一次分解信的信號流圖(n=0,1,2,3) 9NW6NW3NW0NW3NW2NW1NW0NWX(4) X(14) X(10) X(6) X(2) X(12) X(8) X(0) X(13) X(9

34、) X(5) X(1) X(15) X(11) X(7) X(3) x7(1) x8(3) x8(2) x8(1) x8(0) x7(3) x7(2) x7(0) -j -j -j -j x5(1) x6(3) x6(2) x6(1) x6(0) x5(3) x5(2) x5(0) 6NW4NW2NWx3(3) x3(2) x(2) x1(1) x1(0 x(1) x(0 x1(3) x1(2) x(3) x(6) x3(1) x3(0) x(5) x(4) x(7) 0NW16 點基 4FFT 的次分解流圖 x4(3) x4(2) x(10) x2(1) x2(0 x(9) X8 x2(3)

35、 x2(2) x(11) x(14) x4(1) x4(0) x(13) x(12) x(15) N/4 點 DFT N/4 點 DFT N/4 點 DFT N/4 點 DFT 5.5 基4FFT的頻率抽取算法(4)(3) 4個4點數(shù)據(jù)DFT的基4FFT表示和16點數(shù)據(jù)基4FFT算法的完整信號流圖則。，序號符合字位倒置規(guī)二級輸出一級乘分兩級個蝶形運算符的基本運算單元，含每一組都是基結(jié)論可以寫為點注意到)(,44:)3() 1 ()2()0()15()3() 1 ()2()0()7()3() 1 ()2()0()11()3() 1 ()2()0()3()()34()3() 1 ()2()0()1

36、3()3() 1 ()2()0()5()3() 1 ()2()0()9()3() 1 ()2()0() 1 ()() 14()3() 1 ()2()0()14()3() 1 ()2()0()6()3() 1 ()2()0()10()3() 1 ()2()0()2()()24()3() 1 ()2()0()12()3() 1 ()2()0()4()3() 1 ()2()0()8()3() 1 ()2()0()0()()4(4888888888888888814/04/8777777777777777714/04/7666666666666666614/04/6555555555555555514

37、/04/5kXjFFTxxjxxXxxjxxXxxxxXxxxxXWnxrXxxjxxXxxjxxXxxxxXxxxxXWnxrXxxjxxXxxjxxXxxxxXxxxxXWnxrXxxjxxXxxjxxXxxxxXxxxxXWnxrXDFTNnnrNNnnrNNnnrNNnnrN5.5 基4FFT的頻率抽取算法(5)16點數(shù)據(jù)的完整信號流圖（結(jié)構(gòu)：N/4行，M/2=0.5log2 N 列:1個單元即藍(lán)綠黑紫蝶）少。比基類蝶形運算實數(shù)乘：。同，復(fù)數(shù)加：與基復(fù)數(shù)乘：FFTNNNNN285log2342log8322 0NW0NW0NW0NW0NW0NW0NW0NW0NW0NW0NW0NW-j

38、-j -j -j 9NW6NW3NW0NW3NW2NW1NW0NWX(8) X(14) X(6) X(10) X(2) X(12) X(4) X(0) X(13) X5) X(9) X(1) X(15) X(7) X(11) X(3) x7(1) x8(3) x8(2) x8(1) x8(0) x7(3) x7(2) x7(0) -j -j -j -j x5(1) x6(3) x6(2) x6(1) x6(0) x5(3) x5(2) x5(0) 6NW4NW2NWx3(3) x3(2) x(2) x1(1) x1(0 x(1) x(0 x1(3) x1(2) x(3) x(6) x3(1)

39、x3(0) x(5) x(4) x(7) 0NW16 點基 4FFT 的信號流圖 x4(3) x4(2) x(10) x2(1) x2(0 x(9) X8 x2(3) x2(2) x(11) x(14) x4(1) x4(0) x(13) x(12) x(15) 5.6 分裂基FFT算法(1)(1)分裂基(split radix)FFT算法(基2/基4算法,P.Dohamel & H.Hollmann,1984)推導(dǎo) 進(jìn)一步推導(dǎo)得到分解公式，X(k)可表示為14/,.,1 , 0,)43()4()2()()34()43()4()2()() 14()43()4()2()()24()43(

40、)4()2()()4()144(412/,.,1 , 0,)2()() 12()2()()2()12(2)()()()2(414/04/314/04/14/04/214/04/12/02/12/02/10NrWWNnxNnxjNnxnxrXWWNnxNnxjNnxnxrXWWNnxNnxNnxnxrXWNnxNnxNnxnxrXFFTNrWWNnxnxrXWNnxnxrXFFTWnxnxDFTkXDFTNNNNnrnNnNNnrnNnNNnrnNnNNnrnNNnrnNnNNnrnNNnknNMM：點的分解點抽分解，頻域每時域順序的頻率抽取算法基：點的分解點抽偶分解，每時域?qū)Π敕纸?，頻域奇的頻

41、率抽取算法基為：點。必有設(shè)不來源于旋轉(zhuǎn)因子。連接后級。個個蝶形，乘形圖含形圖。形，稱基本運算單元是。和為，奇數(shù)序號的為偶數(shù)序號的個奇數(shù)序號：個偶數(shù)序號和分為，或點個和點個分解為點則：得：；令：jWLLLrXrXkXrXkXkXDFTNDFTNDFTNWWnxrXWWnxrXWnxrXNnnxnxnxnxnxnxNnNnxNnxjnxNnNnxnxnxNnNnxNnxNnxNnxnxnxNnNnxnxnxNrWWNnxNnxjNnxnxrXNrWWNnxNnxjNnxnxrXNrWNnxnxrXNnrnNnNNnrnNnNNnrnNNnrnNnNNnrnNnNNnrnN23)34() 14()(

42、)2()(21)(4/22/1)()34()() 14()()2(14/,.,1 , 0,)()()()()()(14/,.,1 , 0),4/3()4/()(14/,.,1 , 0),2/()()(14/,.,1 , 0,)4/3()4/()4/()2/()()(12/,.,1 , 0),2/()()(14/,.,1 , 0,)43()4()2()()34(14/,.,1 , 0,)43()4()2()() 14(12/,.,1 , 0,)2()()2(14/04/3814/04/712/02/14384374311114/04/314/04/12/02/5.6 分裂基FFT算法(2)結(jié)論：

43、 x1(n+N/4) x7(n) x8(n) nNW3nNW-j x(n+N/4) x(n+3N/4) x(n+N/2) x1(n) x3(n) x(n) 分裂基 FFT 的 L 形運算單元 x4(n) 5.6 分裂基FFT算法(3)(2)分裂基FFT算法的信號流圖,N=16點 一步分解信號流圖(n=0,1,2,3):16點DFT分解為16/4個L形圖,1個8點DFT,2個4點DFT。 x(2) x(1) x(0 x(3) x(6) x(5) x(4) x(7) x(10) x(9) X8 x(11) x(14) x(13) x(12) x(15) 9NW6NW3NW0NW3NW2NW1NW0

44、NWX(2) X(14) X(12) X(10) X(8) X(6) X(4) X(0) X(13) X(9) X(5) X(1) X(15) X(11) X(7) X(3) x7(1) x8(3) x8(2) x8(1) x8(0) x7(3) x7(2) x7(0) -j -j -j -j x1(7) x16) x1(1) x1(0 x1(3) x1(2) x1(5) x1(4) 16 點分裂基 FFT 的次分解流圖 x4(3) x4(2) x3(1) x3(0 x3(3) x3(2) x4(1) x4(0) N/2 點 DFT N/4 點 DFT N/4 點 DFT 5.6 分裂基FFT

45、算法(4) 8點分裂基FFT算法的一步分解信號流圖(n=0,1) 8點DFT可分解為8/4=2個L形圖、1個4點DFT和2個2點DFT（圖中紫線） 4點分裂基FFT算法的一步分解信號流圖 4點DFT可分解為4/4=1個L形圖、1個2點DFT和2個1點DFT（圖中紫線） x(2) x(1) x(0 x(3) x(6) x(5) x(4) x(7) 3NW0NW1NW0NWX(2) X(7) X(3) X(5) X(1) X(6) X(4) X(0) x7(1) x8(1) x8(0) x7(0) -j -j x4(1) x4(0) x1(1) x1(0 x(3) x1(2) x3(1) x3(0) 8 點分裂基 FFT 的次分解流圖 N/2 點 DFT 4 點 x(2) x(0) x(1) x(3) x1(1) x7(0) x8(0) 0NW0NW-j x(1) x(3) x(2) x1(0) x3(0) x(0) 4 點分裂基 FFT 的分解流圖 x4(0) 兩點、四點數(shù)據(jù)為止更短用蝶形構(gòu)成短序列點短序列個點和個長序列分解分解分解 )(4/22/1NNN5.6 分裂基FFT算法(5) 16點分裂基FFT算法的完整信號流圖 0NW0NW0NW0NW0NW0NW0NW