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

1、第第6 6章章 快速傅立叶变换快速傅立叶变换(FFT)(FFT) 虽然频谱分析和虽然频谱分析和DFTDFT运算很重要，但在很长一段运算很重要，但在很长一段时间里，由于时间里，由于DFTDFT运算复杂，并没有得到真正的运用，运算复杂，并没有得到真正的运用，而频谱分析仍大多采用模拟信号滤波的方法解决，而频谱分析仍大多采用模拟信号滤波的方法解决，直到直到19651965年首次提出年首次提出DFTDFT运算的一种快速算法以后，运算的一种快速算法以后，情况才发生了根本变化，人们开始认识到情况才发生了根本变化，人们开始认识到DFTDFT运算的运算的一些内在规律，从而很快地发展和完善了一套高速一些内在规律，

2、从而很快地发展和完善了一套高速有效的运算方法有效的运算方法快速付里变换（快速付里变换（FFTFFT）算法。）算法。FFTFFT的出现，使的出现，使DFTDFT的运算大大简化，运算时间缩短的运算大大简化，运算时间缩短一二个数量级，使一二个数量级，使DFTDFT的运算在实际中得到广泛应的运算在实际中得到广泛应用。用。6.1 6.1 引言引言一一.DFT.DFT的计算工作量的计算工作量 两者的差别仅在指数的符号和两者的差别仅在指数的符号和因子因子1/N1/N. . 1, 1 , 0 ,)()(10NkWnxkXNnnkN101, 1 , 0 ,)(1)(NknkNNnWkXNnx 通常通常x(n)x

3、(n)和和都是复数都是复数, ,所以计算一个所以计算一个X(k)X(k)的值需要的值需要N N次复数乘法运算次复数乘法运算, ,和和 次复数加法运次复数加法运算算. .那么那么, ,计算全部计算全部N N点的点的X(k)X(k)就要就要N N2 2次复数乘法运次复数乘法运算算, ,N(N-1)N(N-1)次复数加法运算次复数加法运算. .一般来说一般来说, ,乘法运算乘法运算要比相加运算复杂要比相加运算复杂, ,为讨论简单起见为讨论简单起见, ,我们以复数我们以复数乘法运算次数近似作为运算工作量的衡量标准乘法运算次数近似作为运算工作量的衡量标准. .当当N N很大时很大时, ,运算量将是惊人的

4、运算量将是惊人的, ,如如N=1024,N=1024,则要完则要完成成1048576 1048576 次次( (一百多万次一百多万次) )运算运算. .这样这样, ,难以做到难以做到实时处理实时处理. .nkNW1N一个X(k)的值的工作量,如X(1)1210) 1() 2() 1 () 0() 1 (NNNNNWNxWxWxWxX二二. .改进的途径改进的途径 1. 1. 的对称性和周期性的对称性和周期性nkNW;,)()()(*NknNkNnNnkNnkNnkNWWWWW.),1( 1),1()2/(2/)(2)()(2kNNkNjNNNnkNnNNkNnkNknNNkNnNWWeWWeW

5、WWWWN得:对称性:周期性:利用上述特性利用上述特性, ,可以将有些项合并可以将有些项合并22)()()(NNNkXkXkX把把N N点数据分成点数据分成两两半：半：其运算量为：其运算量为：2)2(N2)2(N2N再分两半：再分两半：44)()(NNkXkX44)()(NNkXkX+=22N2)4(N2)4(N2)4(N2)4(N+=24N这样一直分下去，剩下两点的变换。这样一直分下去，剩下两点的变换。 把长度为把长度为N N点的大点数的点的大点数的DFTDFT运算依次分解为若干运算依次分解为若干个小点数的个小点数的DFTDFT。因为。因为DFTDFT的计算量正比于的计算量正比于N N2 2

6、，N N小，小，计算量也就小。计算量也就小。 FFT FFT算法正是基于这样的基本思想发展起来的。算法正是基于这样的基本思想发展起来的。19651965年年, ,库库利利(cooley)(cooley)和图基和图基(Tukey)(Tukey)首先提出首先提出FFTFFT算法算法. .对于对于N N点点DFT,DFT,仅需仅需(N/2)log(N/2)log2 2N N 次复数乘法运算次复数乘法运算. .例如例如N=1024=2N=1024=21010 时，需要时，需要(1024/2)log(1024/2)log2 2 2 21010 =512 =512* *10=512010=5120次。次。

7、5120/1048576=4.88%5120/1048576=4.88% , ,速速度提高度提高2020倍倍. . 应用第三代数字信号处理器应用第三代数字信号处理器TMS320C30-40TMS320C30-40，具有，具有50ns50ns的单的单周期执行时间，每秒周期执行时间，每秒2000020000次浮点运算，完成乘法、加法及运次浮点运算，完成乘法、加法及运算控制、数据存取共需约算控制、数据存取共需约1s1s左右，而采用左右，而采用FFTFFT算法，计算时间算法，计算时间可缩减为可缩减为2.366ms2.366ms。 FFT FFT有多种形式，但基本上可分为两类：有多种形式，但基本上可分为

8、两类：时间抽取法和频时间抽取法和频率抽取法率抽取法。 按按“基数基数”分：基分：基-2FFT-2FFT算法；基算法；基-4FFT-4FFT算法；混合基算法；混合基 FFTFFT算法；分裂基算法；分裂基FFTFFT算法算法 其它方法：线性调频其它方法：线性调频Z Z变换变换(CZT(CZT法法) ) 1. 1. 设输入序列长度为设输入序列长度为N=2N=2L L( (L L为正整数，将该为正整数，将该序列按时间顺序的奇偶分解为越来越短的子序序列按时间顺序的奇偶分解为越来越短的子序列，称为基列，称为基2 2按时间抽取的按时间抽取的FFTFFT算法。也称为算法。也称为Coolkey-TukeyCoo

9、lkey-Tukey算法。算法。 2. 2. 其中基数其中基数2-N=22-N=2L L，L L为整数为整数. .若不满足若不满足这个条件，可以人为地加上若干零值（加零补这个条件，可以人为地加上若干零值（加零补长）使其达到长）使其达到 N=2 N=2L L6.2 6.2 按时间抽取按时间抽取(DIT)(DIT)的的FFTFFT算法算法 库利库利- -图基算法图基算法算法原理算法原理(1).N/2(1).N/2点点DFTDFT1.1.先将先将 按按n n的奇偶分为两组作的奇偶分为两组作DFT,DFT,这样这样有有: : n n为偶数时为偶数时: : n n为奇数时为奇数时: :1, 1 , 0

10、),() 12(1, 1 , 0 ),()2(2221NNrrxrxrrxrx10)()()(NnnkNWnxnxDFTkX因此，因此，)(nx由于由于: :所以所以, ,上式可表示为上式可表示为: :1022102110)12(10210102222)()()12()2()()()(NNNNrrkNkNrrkNrkrNrrkNNnNnnkNnkNWrxWWrxWrxWrxWnxWnxkX(n(n为偶数为偶数) ) ( (n n为奇数为奇数) )222)/(222NNNWeeWjjN)()()()()(211021012222kXWkXWrxWWrxkXkNrrkkNrrkNNNN 其中,2.

11、2.两点结论: (1) X (1) X (k),X(k),X (k)(k)均为N/2N/2点的DFTDFT。 (2) X(k)=X (2) X(k)=X (k)+W(k)+W X X (k)(k)只能确定出 X(k) X(k)的k= k= 个；即前一半的结果。1 21 2kN10102210101122222222) 12()()()2()()(NNNNNNNNrrkrrkrrkrrkWrxWrxkXWrxWrxkX1, 1 , 02 N 同理同理, , 这就是说这就是说,X,X1 1(k),X(k),X2 2(k)(k)的后一半的后一半, ,分别分别 等于其前一半的值。等于其前一半的值。3.

12、X(k)3.X(k)的后一半的确定的后一半的确定rkkrNNNWW222)()()()()2(1101)(101122222kXWrxWrxkNXNNNNNrrkkrr由于由于 （周期性）（周期性）, ,所以所以: :)()2(22kXkNX 可见可见,X(k),X(k)的后一半，也完全由的后一半，也完全由X X1 1(k), X(k), X2 2(k)(k)的前一半所确定。的前一半所确定。 * *N N点的点的DFTDFT可由两个可由两个N/2N/2点的点的DFTDFT来计算。来计算。kNkNNkNWWWWNN22)()2()2()2(212NkXWNkXNkXNkN1, 1 , 0 ),(

13、)(221NkNkkXWkX又由于又由于 , ,所以所以实现上式运算的流图称作蝶形运算实现上式运算的流图称作蝶形运算 前一半4.4.蝶形运算蝶形运算 后一半（N/2N/2个蝶形个蝶形) )( (前一半前一半) )( (后一半后一半) )1 1 11-1-1)()()()()()(2121kXWkXkXkXWkXkXkNkN)1,()1, 1 ,0(22 N Nk kk kN NN N)()()(21kXWkXkXkN)()()2(21kXWkXkNXkN)(1kX)(2kXkNW由由X X1 1(k)(k)、X X 2 2(k)(k)表示表示X(k)X(k)的运算是一种特殊的运算的运算是一种特

14、殊的运算- -碟形运算碟形运算X1(k)X2(k)kNW)()(21kXWkXkN)()(21kXWkXkN作图要素：作图要素：(1)(1)左边两路为输入左边两路为输入(2)(2)右边两路为输出右边两路为输出(3)(3)中间以一个小圆表示加、中间以一个小圆表示加、减运算（右上路为相加输减运算（右上路为相加输出、右下路为相减输出出、右下路为相减输出) )(4)(4)如果在某一支路上信号需要进行如果在某一支路上信号需要进行相乘运算，则在该支路上标以箭头，相乘运算，则在该支路上标以箭头，将相乘的系数标在箭头旁。将相乘的系数标在箭头旁。(5)(5)当支路上没有箭头及系当支路上没有箭头及系数时，则该支路

15、的传输比数时，则该支路的传输比为为1 1。(1)N/2(1)N/2点的点的DFTDFT运算量运算量: :复乘次数复乘次数: :复加次数复加次数: :(2)(2)两个两个N/2N/2点的点的DFTDFT运算量运算量: :复乘次数复乘次数: :复加次数复加次数: : (3)N/2(3)N/2个蝶形运算的运算量个蝶形运算的运算量: :复乘次数复乘次数: :复加次数复加次数: : 5. .计算工作量分析计算工作量分析复乘复乘: :复加复加: :4)2(22NN)12(2NN22N)12(NN2NNN222)12(2NNNN22222NNN总共运算量总共运算量: :按奇、偶分组后的计算量：按奇、偶分组后

16、的计算量： 但是但是,N,N点点DFTDFT的复乘为的复乘为N N2 2 ; ;复加复加N(N-1);N(N-1);与分解与分解后相比可知后相比可知, ,计算工作点差不多减少计算工作点差不多减少 一半。一半。 例如 N=8 N=8 时的DFT,DFT,可以分解为两个 N/2=4N/2=4点的DFTDFT.具体方法如下: : (1)n(1)n为偶数时,即 分别记作: :)(42/1kXDFTN，得点的进行3 , 2 , 1 , 0)2()()(30430411kWrxWrxkXrrkrrk);6()3(),4()2(),2()1(),0()0(1111xxxxxxxx);6(),4(),2(),

17、0(xxxx (2) n (2) n为奇数时,分别记作:);7()3(),5()2(),3()1(),1()0(2222xxxxxxxx3 , 2 , 1 , 0) 12()()(30430422kWrxWrxkXrrkrrk)(42/2kXDFTN，得点的进行3 , 2 , 1 , 0),()() 4()()()(2121kkXWkXkXkXWkXkXkNkN x1 1(0)=(0)=x(0) (0) x1(1)=(1)=x(2) (2) N/2N/2点点 x1(2)=(2)=x(4) DFT (4) DFT x1(3)=(3)=x(6) (6) x2(0)=(0)=x(1) (1) x2(

18、1)=(1)=x(3) (3) N/2N/2点点 x2(2)=(2)=x(5) (5) DFT DFT x2(3)=(3)=x(7)(7) X X1(0)(0)X X1(1)(1)X X1(2)(2)X X1(3)(3)X X2(0)(0)X X2(1)(1)X X2(2)(2)X X2(3)(3)WN2WN1WN0WN3-1-1-1-1X(0)X(0)X(1)X(1)X(2)X(2)X(3)X(3)X(4)X(4)X(5)X(5)X(6)X(6)X(7)X(7)(3)(3)对X 1(k)X 1(k)和X 2(k)X 2(k)进行蝶形运算,前半部为 X(0) X(3),X(0) X(3),后半

19、部分为X(4) X(7)X(4) X(7) 整个过程如下图所示:4点DFTx(0)x(2)x(4)x(6)4点DFTx(1)x(3)x(5)x(7)08W18W28W38WX(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)偶数序列奇数序列3821282118210821) 3 () 3 (3) 2() 2(2) 1 () 1 (1) 0() 0(0WXXXWXXXWXXXWXXX）（）（）（）（如：x1(r)x2(r) 由于N=2 N=2 L L , ,所以 N/2N/2仍为偶数,可以进 一步把每个N

20、/2N/2点的序列再按其奇偶部分 分解为两个N/4N/4的子序列。例如，n为偶数时的 N/2N/2点分解为:(2).N/4(2).N/4点点DFTDFT1, 1 , 0),()2(431Nlxlx1, 1 , 0),() 12(441Nlxlx进行N/4N/4点的DFTDFT,得到klNllkNllkNllkNlWlxWlxkXWlxWlxkXNNNN) 12(2/1014/104422/1014/1033) 12()()()2()()(4444( (偶中偶) )( (偶中奇) )()()(4312kXWkXkXkN1, 1 , 04Nk从而可得到前从而可得到前N/4N/4的的X X1 1(k

21、)(k)()()4(4312kXWkXkNXkN后后N/4N/4的的X X1 1(k)(k)为为1, 1 , 04Nk一个2点的DFT蝶形流图2点DFT2点DFTx(0)x(4)x(2)x(6)X3(0)X3(1)X4(0)X4(1)X1(0)X1(1)X1(2)X1(3)04W14W) 1 () 1 () 1 () 0() 0() 2() 1 () 1 () 1 () 0() 0() 0(41431404314143140431XWXXXWXXXWXXXWXX其中( (奇中偶奇中偶) )104/64/1026104/5104/254444)()12()()()2()(NNNNllkNlkNl

22、llkNllkNWlxWlxkXWlxWlxkX( (奇中奇奇中奇) )同样对同样对n n为奇数时，为奇数时，N/2N/2点分为两个点分为两个N/4N/4点点 的序列进行的序列进行DFTDFT，则有，则有: :14, 1 , 0k; (k)XW(k) X(k) X6kN/252N14, 1 , 0k; (k)XW(k) Xk)4N( X6kN/252N进行碟形运算，得：、由)()(65kXkX另一个另一个2 2点的点的DFTDFT蝶形流图蝶形流图2点DFT2点DFTx(1)x(5)x(3)x(7)X5(0)X5(1)X6(0)X6(1)X2(0)X2(1)X2(2)X2(3)04W14W) 1

23、 () 1 () 1 () 0() 0() 2() 1 () 1 () 1 () 0() 0() 0(61452604526145260452XWXXXWXXXWXXXWXX其中 (0) (4) (2) (6) (1) (5) (3) (7)WN0WN0WN0W0N-1-1-1-1X (0)X (1)X (0)X (1)X (0)X (1)X (0)X (1)33445566WN0WN2WN0WN2-1-1-1-1X (0)X (1)X (2)X (3)X (0)X (1)X (2)X (3)11121222WWWWN0N1N2N3-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5

24、)X(6)X(7)xxxxxxxx因此因此,8,8点点DFTDFT的的FFTFFT的运算流图如下的运算流图如下x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)38W28W18W08W08W08W08W08W08W08W28W28WX(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)12/0NNNWW其中旋转因子，共有m=0m=1m=2m m为级数为级数, , N=2N=2M M所以所以N N点点DFTDFT可分成可分成M M级级2点DFT2点DFT2点DFT2点DFT2点DFT2点DFT2点DFT2点DFT两个2点DFT两个2点DFT两个2点DFT两个2点DFT两个

25、4点DFT两个4点DFT两个N/2点DFTX1(k).X2(k)X(k) 由于每一步分解都是基于在每级按输入时间序列由于每一步分解都是基于在每级按输入时间序列的次序是属于偶数还是奇数来分解为两个更短的序列，的次序是属于偶数还是奇数来分解为两个更短的序列，所以称为所以称为“按时间抽取法按时间抽取法”. .x(n)( (二二).).运算量运算量 由上述分析可知,N=8N=8需三级蝶形运算 N=2 =8,N=2 =8,由此可知,N=2N=2L L 共需L L级蝶形运算, 而且每级都由N/2N/2个蝶形运算 组成,每个蝶形运算有一次复乘,两次复加。3 3 因此因此,N,N点的点的FFTFFT的运算量为

26、的运算量为复乘复乘: m: mF F = =（N/2N/2）L=L=（N/2N/2） loglog2 2 N N复加复加: a: aF F =N L=N log =N L=N log2 2 N N 由于计算机的乘法运算比加法运算所由于计算机的乘法运算比加法运算所需的时间多得多，故以乘法作为比较基准需的时间多得多，故以乘法作为比较基准. . (0)=(0)=X X0 0(0)(0) X X1 1(0)(0) X X2 2(0) X(0) X3 3(0)(0)=X(0) =X(0) (4)=(4)=X X0 0(1)(1) X X1 1(1) X(1) X2 2(1) X(1) X3 3(1)(1

27、)=X(1)=X(1) (2)=(2)=X X0 0(2)(2) X X3 3(2)(2)=X(2)=X(2) (6)=(6)=X X0 0(3)(3) X X3 3(3)(3)=X(3)=X(3) (1)=(1)=X X0 0(4)(4) X X1 1(4) X(4) X2 2(4) X(4) X3 3(4)(4)=X(4)=X(4) (5)=(5)=X X0 0(5)(5) X X3 3(5)(5)=X(5)=X(5) (3)=(3)=X X0 0(6)(6) X X3 3(6)(6)=X(6)=X(6) (7)=(7)=X X0 0(7)(7) X X1 1(7) X(7) X2 2(7

28、) X(7) X3 3(7)(7)=X(7)=X(7)WWWWN0N0N0N0-1-1-1-1WWWWN0N2N0N2-1-1-1-1WWWWNNNN0123.( (三三).DIT).DIT的的FFTFFT算法的特点算法的特点 1.1.原位运算原位运算输入数据、中间运算结果和最后输出均用同一存储器。输入数据、中间运算结果和最后输出均用同一存储器。xxxxxxxx2 2 倒位序规律倒位序规律 由图可知由图可知, ,输出输出X(k)X(k)按正常顺序排列在存按正常顺序排列在存储单元储单元, ,即即X(0)X(7),X(0)X(7),输入却输入却不能按自然顺不能按自然顺序存入到存储单元中，而是序存入

29、到存储单元中，而是x(0),x(4),x(2), x(0),x(4),x(2), x(6).x(6).的顺序存入存储单元的顺序存入存储单元，即为即为乱序输入，乱序输入，顺序输出顺序输出。 这种顺序称作这种顺序称作倒位序倒位序, ,即二进制数倒位。即二进制数倒位。 3.3.倒位序实现倒位序实现 输入序列先按自然顺序存入存储单元输入序列先按自然顺序存入存储单元, ,然后经变址运算来实现然后经变址运算来实现倒位序排列倒位序排列. . 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 4 1 0 0 1 1 0 0 4 2 0 1 0 0 1 0 2 2 0

30、1 0 0 1 0 2 3 0 1 1 1 1 0 6 3 0 1 1 1 1 0 6 4 1 0 0 0 0 1 1 4 1 0 0 0 0 1 1 5 1 0 1 1 0 1 5 5 1 0 1 1 0 1 5 6 1 1 0 0 1 1 3 6 1 1 0 0 1 1 3 7 1 1 1 1 1 1 7 7 1 1 1 1 1 1 7 自然顺序自然顺序n n 二进制二进制n n n n n n 倒位序二进制倒位序二进制n n n n n n 倒位顺序倒位顺序n n2 1 0 0 1 2看出：倒位序后的顺序刚好是数据送入计算机内的顺序。看出：倒位序后的顺序刚好是数据送入计算机内的顺序。4.

31、4.蝶形运算所需系数蝶形运算所需系数mM 2lmW212m0NW12, 1 ,01mlnkNW 蝶形运算所需系数，各级有所不同。每级自上蝶形运算所需系数，各级有所不同。每级自上而下观察，均是以而下观察，均是以 开始，按等比级数依次递开始，按等比级数依次递增，周期重复。例如，第增，周期重复。例如，第m m级运算，系数为级运算，系数为 , ,共共 个系数，指数个系数，指数l l逐次增逐次增1 1，周期重复周期重复 次。计算时所需系数可以事前计算好次。计算时所需系数可以事前计算好存在一个数表中，这样运算速度快，但需开销内存存在一个数表中，这样运算速度快，但需开销内存亦可在需要时依次递推计算，这样可节

32、省内存，但亦可在需要时依次递推计算，这样可节省内存，但要增加一定的运算工作量。要增加一定的运算工作量。6.3 6.3 频率抽取基频率抽取基2-2-FFTFFT算法算法( (桑德桑德图基算法图基算法) ) 对于对于N=2N=2M M情况下的另外一种普遍使用的情况下的另外一种普遍使用的FFTFFT结结构是频率抽取法，按输出构是频率抽取法，按输出X X（k k）在频域的顺序上）在频域的顺序上属于偶数还是奇数分解为两组属于偶数还是奇数分解为两组 对于频率抽取法，输入序列不是按偶数奇数，对于频率抽取法，输入序列不是按偶数奇数，而是按而是按前后对半前后对半分开，这样便将分开，这样便将N N点点DFTDFT

33、写成前后两写成前后两部分：部分：前半子序列前半子序列x(n),x(n), 0 0nN/2-1nN/2-1; ;后半子序列后半子序列x(n+N/2),0 x(n+N/2),0nN/2-1nN/2-1; ;例：例：N=8N=8时，前半序列为：时，前半序列为：x(0),x(1),x(2),x(3);x(0),x(1),x(2),x(3); 后半序列为：后半序列为：x(4),x(5),x(6),x(7); x(4),x(5),x(6),x(7); ( (一一).).算法原理算法原理 1.N1.N点点DFTDFT的另一种表达形式的另一种表达形式10)()(NnnkNWnxkX10)(1012/10222

34、2)2()()()(NNNNnknNnnkNNNnnkNnnkNWNnxWnxWnxWnxnkNnkNWWNnxnxNN1022)2()(nkNnkWNnxnxkXN102)2() 1()()(1, 1 , 0Nk 2.N2.N点点DFTDFT按按k k的奇偶分组可分为两个的奇偶分组可分为两个N/2N/2的的DFTDFT 当当k k为偶数为偶数, ,即即 k=2rk=2r时时, (-1), (-1)k k =1 =1； 当当k k为奇数为奇数, ,即即 k=2r+1k=2r+1时时 (-1)(-1)k k =-1 =-1 这时这时 X(k) X(k) 可分为两部分：可分为两部分： nrnnrN

35、nNNNWNnxnxWNnxnx22210210)2()()2()()2( rX1, 1 , 02Nrk k为偶数时：为偶数时： 可见可见, ,上面两式均为上面两式均为N/2N/2的的DFTDFT。nrnnNrnNnNNNWWNnxnxWNnxnxrX22210)12(10)2()()2()() 12(k k为奇数时：为奇数时：1, 1 , 02Nr-1-1)2()(Nnxnx1, 1 ,02NnnNWNnxnx)2()(3.3.蝶形运算蝶形运算进行如下碟形运算：和)2()(NnxnxnNW)2(Nnx)(nx 4. 4.仿照仿照DITDIT的方法的方法 再将再将N/2N/2点点DFTDFT按

36、按k k的奇偶分解为两个的奇偶分解为两个N/4N/4点点的的DFT,DFT,如此进行下去如此进行下去, ,直至分解为直至分解为2 2点点DFTDFT。 例子：求例子：求 N=2 N=23 3=8=8点点DIFDIF （1 1）先按）先按N=8-N/2=4N=8-N/2=4，做做4 4点的点的DIFDIF：nNWNnxnxnxNnxnxnx)2()()()2()()(21先将先将N=8DFTN=8DFT分解成分解成2 2个个4 4点点DFTDFT：可知：时域上：可知：时域上：x(0),x(1),x(2),x(3)x(0),x(1),x(2),x(3)为偶子序列为偶子序列 x(4),x(5),x(

37、6),x(7) x(4),x(5),x(6),x(7)为奇子序列为奇子序列 频域上：频域上：X(0),X(2),X(4),X(6)X(0),X(2),X(4),X(6)由由x x1 1(n)(n)给出给出 X(1),X(3),X(5),X(7), X(1),X(3),X(5),X(7),由由x x2 2(n)(n)给出给出将将N=8N=8点分解成点分解成2 2个个4 4点的点的DIFDIF的信号流图的信号流图 4点DFTx(0)x(1)x(2)x(3)4点DFTx(4)x(5)x(6)x(7)X(0)X(2)X(4)X(6)X(1)X(3)X(5)X(7)X1(k)前半部分序列后半部分序列nN

38、nNnNnNWxxxWxxxWxxxWxxxxxxxxxxxxxxx)7()3(3,)6()2(2,)5() 1 (1,)4()0(0)7()3(3),6()2(2),5() 1 (1),4()0(022221111）（）（）（）（）（）（）（）（如：08W18W28W38Wx1(n)x2(n)X2(k)(2)N/2(4(2)N/2(4点点)-N/4(2)-N/4(2点点) )FFTFFT(a)(a)先将先将4 4点分解成点分解成2 2点的点的DIFDIF：后半部分序列、前半部分序列、) 3 () 2() 1 () 0(: )(11111xxxxnx10140)2()()()2()(41131

39、1，），在此（）（若设：LNLLxWNnxnxLxNnxnxnN后半部分序列、前半部分序列、同理：) 3 () 2() 1 () 0(: )(22222xxxxnx10140)2()()()2()(622522，），在此（）（同理：LNLLxWNnxnxLxNnxnxnN（b b) )一个一个2 2点的点的DIFDIF蝶形流图蝶形流图2点DFT2点DFTx1(0)x1(1)x1(2)x1(3)x3(0)x3(1)x4(0)x4(1)X(0)X(4)X(2)X(6)08W28W) 3 () 1 () 1 (,) 2() 0() 0(113113xxxxxx其中(c)(c)另另一个一个2 2点的点

40、的DIFDIF蝶形流图蝶形流图2点DFT2点DFTx2(0)x2(1)x2(2)x2(3)x5(0)x5(1)x6(0)x6(1)X(1)X(5)X(3)X(7)08W28W(3)(3)将将N/4N/4（2 2点）点）DFTDFT再分解成再分解成2 2个个1 1点的点的DFTDFT(a)(a)求求2 2个一点的个一点的DFTDFT021022120202120230202020231021 , 0; 1 , 0)4()0()4()0() 1 ()4()0()4()0()0()()(2WWknWWWWWxWxWxWxXWxWxWxWxXWnxkXnknknkNnkNnnkN，其中，则这里用到对称

41、性这是一蝶形结代入上面流图可知： 最后剩下两点最后剩下两点DFT,DFT,它可分解成两个一点它可分解成两个一点DFTDFT，但一点，但一点DFTDFT就等于输入信号本身，所以两点就等于输入信号本身，所以两点DFTDFT可用一个蝶形结表可用一个蝶形结表示。取示。取x3(0)x3(0)、x3(1)x3(1)为例。为例。(b)2(b)2个个1 1点的点的DFTDFT蝶形流图蝶形流图 1点DFTx3(0)1点DFTx3(1)X(0)X(4)02W进一步简化为进一步简化为蝶形流图：蝶形流图：02WX(0)X(4)x3(0)x3(1)(4(4) )一个完整一个完整N=8N=8的按频率抽取的按频率抽取FFT

42、FFT的的运算流图运算流图 x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)38W28W18W08W08W08W08W08W08W08W28W28WX(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)12/0NNNWW其中旋转因子，共有m=0m=1m=2频率抽取法频率抽取法FFTFFT的运算特点：的运算特点：（1 1）蝶形运算）蝶形运算 对于任何一个对于任何一个2 2的整数幂的整数幂N=2N=2M M，总是可以通过，总是可以通过M M次次分解最后完全成为分解最后完全成为2 2点的点的DFTDFT运算。这样的运算。这样的M M次分解，次分解，就构成从就构成从x(n)x

43、(n)到到X(k)X(k)的的M M级运算过程。将频率抽取法级运算过程。将频率抽取法的流图反转，并将输入变输出，输出变输入，得到的的流图反转，并将输入变输出，输出变输入，得到的便是时间抽取法流图（反映了时域，频域的对称法）便是时间抽取法流图（反映了时域，频域的对称法）。频率抽取法也共有。频率抽取法也共有M M级运算（级运算（N=2N=2M M），其运算量与），其运算量与时间抽取法相同。时间抽取法相同。（2 2）原位计算）原位计算 类似于时间抽取法，当数据输入到存储器中以后类似于时间抽取法，当数据输入到存储器中以后，每一级运算的结果仍然储存在同一组存储器中，直，每一级运算的结果仍然储存在同一组存

44、储器中，直到最后输出，中间无需其它存储器，所以频域抽取法到最后输出，中间无需其它存储器，所以频域抽取法也可进行原位计算。也可进行原位计算。（3 3）序数重排）序数重排 它的输入正好是自然顺序。但它的输出却是码位倒它的输入正好是自然顺序。但它的输出却是码位倒置的顺序。因此运算完毕后，要通过变址运算将码位倒置的顺序。因此运算完毕后，要通过变址运算将码位倒置的顺序转换为自然顺序，然后输出，变址方法同时间置的顺序转换为自然顺序，然后输出，变址方法同时间抽取法。抽取法。（4 4）蝶形类型随迭代次数成倍减少）蝶形类型随迭代次数成倍减少( (与时间抽取相反与时间抽取相反) ) 第一级迭代中有第一级迭代中有N

45、/2N/2种蝶形运算系数，参加蝶形运种蝶形运算系数，参加蝶形运算的两个数据相隔算的两个数据相隔N/2N/2，随后每次迭代，蝶形类形比前，随后每次迭代，蝶形类形比前一级减少一倍，间距也减少一倍，最后一级迭代，蝶形一级减少一倍，间距也减少一倍，最后一级迭代，蝶形类形只有一种类形只有一种W W0 0N N，数据间隔为，数据间隔为1 1。 由这几点规律可以看出，频率抽取法与时间抽取法由这几点规律可以看出，频率抽取法与时间抽取法是两种等价的是两种等价的FFTFFT运算。运算。1.1.相同点相同点 (1)(1)进行原位运算；进行原位运算； (2)(2)运算量相同运算量相同, ,均为（均为（N/2) Log

46、N/2) Log2 2N N次复次复乘乘,N Log,N Log2 2N N次复加。次复加。 2.2.不同点不同点 (1)DIT(1)DIT输入为倒位序输入为倒位序, ,输出为自然顺序；输出为自然顺序； DIFDIF正好与此相反。但正好与此相反。但DITDIT也有输入为自然顺也有输入为自然顺序序, ,输出为倒位序的情况。输出为倒位序的情况。( (二二).DIF).DIF法与法与DITDIT法的异同法的异同rNmmmWjXkXjX)()()(11rNmmmWjXkXkX)()()(11)(1kXm)(1jXmrNW1(2)(2)蝶形运算不同蝶形运算不同a.a.(DIT)(DIT)用矩阵表示用矩阵

47、表示)(kXm)(jXmrNWrNW)(1kXm)(1jXm=11rNmmmWjXkXjX)()()(11)()()(11jXkXkXmmm)(1kXm)(1jXmrNW1b.b.(DIF)(DIF)用矩阵表示)(kXm)(jXmrNWrNW)(1kXm)(1jXm=11(3)(3)两种蝶形运算的关系两种蝶形运算的关系 互为转置（矩阵）；互为转置（矩阵）；将流图的将流图的所有支路所有支路方向都反方向都反向向, ,交换输交换输入和输出，入和输出，即可得到即可得到另一种蝶另一种蝶形。形。 a.a.(DIT)(DIT)b.b.(DFT)(DFT)rNWrNW1111rNWrNWDIFDIF与与DIT

48、DIT根本区别：根本区别：在于蝶形结不同。在于蝶形结不同。DITDIT的复数相乘出现在减法之前。的复数相乘出现在减法之前。DIFDIF的复数相乘出现在减法之后。的复数相乘出现在减法之后。 6.5 6.5离散傅里叶反变换的计算方法离散傅里叶反变换的计算方法一一. .稍微变动稍微变动FFTFFT程序和参数可实现程序和参数可实现IFFTIFFT nkNNkNnnkNWkXNkXIDFTnxWnxnxDFTkX1010)(1)()()()()( 比较两式可知比较两式可知, ,只要只要DFTDFT的每个系数的每个系数 换换成成 , ,最后再乘以常数最后再乘以常数1/N1/N就可以得到就可以得到IDFTI

49、DFT的快速算法的快速算法-IFFT-IFFT。 另外另外, ,可以将常数可以将常数1/N1/N分配到每级运算中分配到每级运算中, , , ,也就是每级也就是每级蝶形运算均乘蝶形运算均乘以以1/1/2 2。 nkNWnkNWLLN)21(211利用利用FFTFFT计算计算IFFTIFFT时在命名上应注意：时在命名上应注意： (1)(1)把把FFTFFT的时间抽取法，用于的时间抽取法，用于IDFTIDFT运算运算时，由于输入变量由时间序列时，由于输入变量由时间序列x(n)x(n)改成频率改成频率序列序列X(k),X(k),原来按原来按x(n)x(n)的奇、偶次序分组的的奇、偶次序分组的时间抽取法

50、时间抽取法FFTFFT，现在就变成了按，现在就变成了按X(k)X(k)的奇的奇偶次序抽取了。偶次序抽取了。 ( (2 2) )同样，频率抽取的同样，频率抽取的FFTFFT运算用于运算用于IDFTIDFT运算时，也应改变为时间抽取的运算时，也应改变为时间抽取的IFFTIFFT。二、改变二、改变FFTFFT流图系数的方法流图系数的方法 1 1、在、在IFFTIFFT的运算中，常常把的运算中，常常把1/N1/N分解为分解为(1/2)(1/2)m m，并且在并且在M M级运算中每一级运算都分别乘以级运算中每一级运算都分别乘以1/21/2因子，因子，就可得到就可得到IFFTIFFT的两种基本蝶形运算结构

51、的两种基本蝶形运算结构。21nNW21BWAnN21BWAnN21AB21nNW21BA21nNWBA21AB(b)(b)时间抽时间抽取取IFFTIFFT的蝶形运算的蝶形运算(a)(a)频率抽取频率抽取IFFTIFFT的蝶形运算的蝶形运算2 2、IFFTIFFT的基本蝶形运算的基本蝶形运算三三. .不改不改(FFT)(FFT)的程序直接实现的程序直接实现IFFT IFFT nkNNkNknkNWkXNWkXNnx1010*)(1)(1)()(1)(110kXDFTNWkXNnkNNk)(nx因此，BABAWWnkNnkN , 这就是说这就是说, ,先将先将X(k)X(k)取共轭取共轭, ,即将

52、即将X(k)X(k)的的虚部乘虚部乘-1-1，直接利用，直接利用FFTFFT程序计算程序计算DFTDFT；然后；然后再取一次共轭；最后再乘再取一次共轭；最后再乘1/N,1/N,即得即得 (n)(n)。所。所以以FFT,IFFTFFT,IFFT可用一个子程序。可用一个子程序。x四、直接利用四、直接利用FFTFFT流图方法的注意点流图方法的注意点（1 1）FFTFFT与与IFFTIFFT连接应用时，注意输入输出序列的连接应用时，注意输入输出序列的 排列顺序，是自然顺序还是倒序。排列顺序，是自然顺序还是倒序。（2 2）FFTFFT和和IFFTIFFT共用同一个程序时，也应注意利用共用同一个程序时，也

53、应注意利用 FFTFFT算法输入输出的排列顺序，即应注意自然算法输入输出的排列顺序，即应注意自然 顺序还是例位序顺序还是例位序（3 3）当把频率抽取）当把频率抽取FFTFFT流图用于流图用于IDFTIDFT时，应改称时时，应改称时 间抽取间抽取IFFTIFFT流图。流图。（4 4）当把时间抽取）当把时间抽取FFTFFT流图用于流图用于IDFTIDFT时，应改称频时，应改称频 率抽取率抽取IFFTIFFT流图。流图。6.66.6 任意基数的任意基数的FFTFFT算法算法 以上讨论的都是以以上讨论的都是以2 2为基数的为基数的FFTFFT算法，即算法，即N=2N=2M M。优点：程序简单，效率高，

54、使用方便。优点：程序简单，效率高，使用方便。 实际应用时，有限长序列的长度实际应用时，有限长序列的长度N N很大程度上由人很大程度上由人为因素确定，因此多数场合可取为因素确定，因此多数场合可取 N=2N=2M M，从而直接使用，从而直接使用以以 2 2 为基数的为基数的FFTFFT算法。如算法。如N N不能人为确定不能人为确定 , N, N的数值的数值也不是以也不是以2 2为基数的整数次方为基数的整数次方, ,处理方法有两种处理方法有两种: : 补零补零: : 将将x(n)x(n)补零补零 , , 使使N=2N=2M.M. 例如例如N=30,N=30,补上补上x(30)=x(31)=0 x(3

55、0)=x(31)=0两点两点, ,使使N=32=2N=32=25 5, ,这这样可直接采用以样可直接采用以2 2为基数为基数M=5M=5的的FFTFFT程序。程序。 有限长度序列补零后并不影响其频谱有限长度序列补零后并不影响其频谱 X(eX(ejwjw) )，只，只是频谱的采样点数增加了是频谱的采样点数增加了, ,上例中由上例中由3030点增加到点增加到3232点，点，所以在许多场合这种处理是可接受的。所以在许多场合这种处理是可接受的。 如要求准确的如要求准确的N N点点DFTDFT值值, ,可采用任意数为基数的可采用任意数为基数的 FFT FFT 算法算法 , , 其其 计算效率低于以计算效

56、率低于以2 2为基数为基数FFTFFT算法。算法。 如如N N为复合数，可分解为两个整数为复合数，可分解为两个整数p p与与q q的乘积的乘积, ,像像前面以前面以2 2为基数时一样为基数时一样,FFT,FFT的基本思想是将的基本思想是将DFTDFT的运算的运算尽量分小尽量分小, ,因此因此, ,在在N=pqN=pq情况下情况下, ,也希望将也希望将N N点的点的DFTDFT分分解为解为p p个个q q点点DFTDFT或或q q个个p p点点DFT,DFT,以减少计算量。以减少计算量。步骤：步骤：0101kPkknQnn10,kn分别为0, 1,，Q-1; 01,kn分别为0, 1,，P-1。

57、 N N点点DFTDFT可以重新写成为可以重新写成为 100101)(,)()(NnknNWnxkkXkPkXkX1010)(01010101QnPnnQnkPkNWnQnx10100110100101010001100100011011,QnPnnkNPnkNQnkNQnPnnkNPnkNQnkNPQnkNWWWnnxWWWWnnxkkX考虑到考虑到 再令再令1010nkPQnkNWW令令 1010010100100110,QnnkQnkNPnnkPWWWnnxkkXPnnkPWnnxnkX,01000,0011001nkQnkNQnWWnkXkkX00001001,nkNWnkXnkXQn

58、nkQWnkXkkX,以以P P=3=3，Q Q=4, =4, N N=12=12为例为例 (1) (1) 先将先将 x(n)x(n)通过通过 x(nx(n1 1Q+nQ+n0 0) )改写成改写成 x(nx(n1 1,n,n0 0) )。因为。因为 Q=4, nQ=4, n1 1=0,1,2, n=0,1,2, n0 0=0,1,2,3,=0,1,2,3,故输入是按自然顺序故输入是按自然顺序的，即的，即 x(0,0)=x(0) x(0,1)=x(1) x(0,2)=x(2) x(0,0)=x(0) x(0,1)=x(1) x(0,2)=x(2) x(0,3)=x(3)x(0,3)=x(3)

59、x(1,0)=x(4) x(1,1)=x(5) x(1,2)=x(6) x(1,0)=x(4) x(1,1)=x(5) x(1,2)=x(6) x(1,3)=x(7)x(1,3)=x(7) x(2,0)=x(8) x(2,1)=x(9) x(2,2)=x(10) x(2,0)=x(8) x(2,1)=x(9) x(2,2)=x(10) x(2,3)=x(11)x(2,3)=x(11)(2) (2) 求个点的求个点的DFT DFT （）（）X X1 1(k(k0 0,n,n0 0) )乘以得到乘以得到X X1 1(k(k0 0,n,n0 0) )。（）求（）求P P个点的个点的DFTDFT，参变

60、量是，参变量是k k0 020301001110,nnkWnnxnkX304001102001,nnkWnkXkkX（）将（）将X X2 2(k(k0 0,k,k1 1) )通过通过X(kX(k0 0+k+k1 1P)P)恢复为恢复为X(k)X(k)N=12为组合数时的FFT（）求个（）求个P P点点DFTDFT需要需要P P2 2次复数乘法和次复数乘法和 P(P-1)P(P-1)次复数加法；次复数加法；（）乘个（）乘个W W因子需要次复数乘法；因子需要次复数乘法；（）求（）求P P个点个点DFTDFT需要需要PQPQ2 2 次复数乘法和次复数乘法和 PP（-1)-1)次复数加法。次复数加法。