第5章快速傅立叶变换(FFT)

1、第五章快速傅立叶变换（FFT）主要内容45.1 引言45.2 基2FFT的时间抽取算法及蝶形图45.3 基2FFT的频率抽取算法45.4 进一步减少计算量的措施45.5 基4FFT的频率抽取算法45.6 分裂基FFT算法45.7 多种形式的FFT算法45.8 结束语5.1 引言(1)离散傅立叶变换（DFT） (2)意义 DFT是离散谱。从理论上解决了离散谱的计算问题，具有重要的理论意义。(3)计算量和存储量分析 计算量用复数加法和复数乘法次数表示。与N2成正比。 复数加法次数：N(N-1)次。复数乘法次数：N2次。 存储量用占用随机存取存储器和只读存储器的数量表示。 RAM单元：N+N=2N个

2、。 ROM单元：N2个。 结论：计算量和存储量，随着数据量的增加都迅速增大。应用困难。(4)解决方法快速算法 J.W.Cooley (IBM), J.W.Tukey(MIT), “机器计算傅立叶级数的一种算法”，Math. Computation, Vol.19,1965.称为 Cooley and Turkey 算法。 以后，出现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因子的特性： 基本思想：分解。 分解的唯一条件：数据长度满足N=2r。否则，补零解决。(2)分解公式的推导(按奇偶序号分解，输入每2点抽1个值) kNNkNkNNkNkNlNkNWWWWWW2，；对称性：周期性：计算。可用短序列可以分解，长序列的结论：，得和进一步，利用，其中：所以：由于：则：，即、为两个短序列。按奇偶序号分解，设一个长序列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两点数据为止更短序列短序列长序列分解分解分解 5.2 基2FFT的时间抽取算法及蝶形图（2）(3) FFT定理或分解公式 (4) 蝶形图和一次分解图：用蝶形图计算DFT。运算量:一次乘，两次加。 一次分解的计算量蝶型运算来计算，即可用两个短数据的那么，长数据的且，即、解为两个短序列把长序列按奇偶序号分。，设一个长序列12/,.,1 , 0),()()2/(12/,.,1 , 0),()()(DFTDFT)()()()(,12/,.,1 , 0),12()(12/,.,1 , 0),2()()()(2),()()(212122112121NkkXWkX

6、NkXNkkXWkXkXnxDFTkXnxDFTkXNnnxnxNnnxnxnxnxNnxDFTkXnxkNkNM倍倍。例；乘次数加次数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点数据时间抽取(Decimation-In-Time)算法的完整分解过程和蝶形流程图 蝶形图（蝶形运算流图）结构：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的运算量（结构：N/2行，M=log2 N 列） 旋转因子(twiddle factor)变化规律100200:1024log1,log2loglog22222RRNNNRNNRNNNN；比较：，加法：乘法：，按规律查表。个，存共产生旋转因子表，：编程时，查表：预先结论个旋转因子。级的转因子：按公式产生：编程时，直接产生旋结论，：，：则例如：计算公式或规律；所以：由于：称指数。，个，为，左到右）旋转因子有级（第设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 ）：指输入数据、中间、最终结果可存放在同一存储单元。 序列的整序（倒序） 整序：字位倒置规则（bit reversed） 硬件电路和汇编程序用2进制倒序， 而高级语言则要换算成10进制。7111111730111106510110151001100461100113

12、201001024100001100000000乱序倒置二进制顺序2/NROMNRAM单元单元存储量：。个存储单元，存入结论：同址运算只需要差）。序距离（即存储器序号表示两个输入数据的顺级运算，表示式中，表示为那么蝶形运算和存储可。，存储器表示为数组时间抽取倒序后，存入设序列放在该蝶形输入处。一个蝶形运算结果可存与前一级结果有关，每注意到：每一级运算只RAMNBLLMLJJpWBJXJXBJXWBJXJXJXNAAAXnxLLMpNLLLpNLLL,.,2 , 1; 12,.,1 , 0;2)()()()()()()(.) 1 ()0()(111115.2 基2FFT的时间抽取算法及蝶形图（6

13、）(7) 16点数据时间抽取算法的完整信号流图。 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)算法的推导个值。点抽部分，每的偶序号部分和奇序号计算结果是原序列可用短序列直接算。，则原、短序列结论：序列对半分构成则：令：则：为奇数为偶数，并注意到：和的奇偶序列记为将则：为短序列，即。将序列前后对半分开，设一个序列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计算，即可用这两个短序列直接那么原序列的蝶型运算并构成两个短序列，即将序列前后对半分解，。，设一个序列 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)基本思想 长序列分解成短序列。从过程看，将输入数据对半分开为两个序列。从结果看，将DFT的输出X(k)按照奇、偶序号分解为两个序列，每2点抽1个值。 命名：基2FFT的频率抽取算法（Sand-Turkey算法，简称DIF-FFT: Decimation In Frequency FFT）。；乘次数加次数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 点数据为止更短用蝶形构成短序列个短序列分解思想：长序列分解分解分解2)(2/2 NN5.3 基2FFT的频率抽取算法（4）(6) 8点数据频率抽取算法的完整分解过程和蝶形流程图 完整分解过程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） 蝶形流程图（结构：N/2行，M=log2 N 列） (7)运算特点：运算量、旋转因子规律、同址运算、存储量、整序规则 整序规则：字位倒置规则。(8)与时间抽取算法比较 分解思想，计算量存储量，整序规则相同。分解方法，碟型图结

22、构，蝶形符号的运算顺序，输入、输出顺序不同。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再取共轭：取共轭：注意到：原理推导：。，得到）结果取共轭，并乘以）对；的程序，作

24、）调用；的共轭，得到）先取分方便。共用子程序，使用十子程序计算方法：直接调用)(/123)(2)()(1*nxNFFTkXFFTkXkXIDFTFFT5.3 基2FFT的频率抽取算法（7） 方法2 防止溢出：1/N=(1/2)M，将1/N分配到M级，每一个蝶形输出支路乘因子1/2。乘法次数增加。.)()()()(3/12;1/12IFFTDITIFFTFFTDIFIFFTDIFnxkXIFFTFFTDITnxkXNWWFFTDIFFFTDITNIDFTDFTFFTpNpN称后算法改为同理，。故称顺序乱序，输出，输入改为特点：。，输出就是）输入；）算法的输出再乘以改为算法中，将与）在。号和系数的

25、差别：旋转因子的符和序。的蝶形图，成为专用程：修改方法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 进一步减少计算量的措施（1）(1)多种类型的蝶形单元运算 .110)2132(22)2(242/13212224)(22),(22)()(2222)1 ()(2/2)1 (31318/8/8/运算。四类：利用特殊复数。三类：去掉一般算法。二类：去掉含一类蝶形单元运算：实数乘法次数为个蝶。，每个对应个级以后，每级。级，无、次实数加。次实数乘和复数运算需要次实数加。而采用特殊次实数乘和分析及结论：复数乘需，其中与其相乘，得是特殊复数。任一复数特殊复数运算：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级以后，复乘法次数为；再去掉级后，复数乘法次数为、去掉法。旋转因子，减少复数乘结论：去掉无关紧要的个蝶形单元运算。个对应个蝶个对应和个无关紧要级后，每级，规律：无关紧要旋转因子分布例如：等。，。如，：无关紧要旋转因子5.4 进一步减少计算量的措施（2）(2)旋转因子的生成(3)实序列的FFT算法 个。

28、存存放在数组中。占用内预先算出旋转因子表查表方法计算量大。直接产生直接产生方法：编程时旋转因子：2/, 12/,.,1 , 0,:,)2sin()2cos(2NNmWmNjmNeWmNmNjmN计算。的复序列直接用看成虚部为：将方法FFTnx0)(1倍。运算速度提高时当算法，相对一般运算效率即算另一半用共轭对称性计是实序列由于分解公式由所以得到：其中共轭对称、反对称那么：和即并构造复序列分解为奇数偶数点序列点的的对称性。将：利用方法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算法的推导(N=4,16,64,)每个式子都是每4点抽1个值，称基4频率抽取算法。进一步推导得到分解公

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有及分别令，有，其中令个短序列。将序列顺次等分为，设5.5 基4FFT的频率抽取算法(2)分解思想：与下级连接。个乘二级输出一级输出。个纯虚数乘，即个蝶形，只有蝶形图，包括基本运算单元是。点的个分成点的结论则：得令：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) 四点数据为止更短个个、二级蝶型构成个、一级蝶形构成顺序个短序列长序列分解分解分解)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点数据DFT的基4FFT表示和16点数据基4FFT算法的完整信号流图则。，序号符合字位倒置规二级输出一级乘分两级个蝶形运算符的基本运算单元，含每一组都是基结论可以写为点注意到)(,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点数据的完整信号流图（结构：N/4行，M/2=0.5log2 N 列:1个单元即蓝绿黑紫蝶）少。比基类蝶形运算实数乘：。同，复数加：与基复数乘：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)推导 进一步推导得到分解公式，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：点的分解点抽分解，频域每时域顺序的频率抽取算法基：点的分解点抽偶分解，每时域对半分解，频域奇的频

41、率抽取算法基为：点。必有设不来源于旋转因子。连接后级。个个蝶形，乘形图含形图。形，称基本运算单元是。和为，奇数序号的为偶数序号的个奇数序号：个偶数序号和分为，或点个和点个分解为点则：得：；令：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)结论：

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) 两点、四点数据为止更短用蝶形构成短序列点短序列个点和个长序列分解分解分解 )(4/22/1NNN5.6 分裂基FFT算法(5) 16点分裂基FFT算法的完整信号流图 0NW0NW0NW0NW0NW0NW0NW