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

第6章快速傅立叶变换(FFT)虽然频谱分析和DFT运算很重要，但在很长一段时间里，由于DFT运算复杂，并没有得到真正的运用，而频谱分析仍大多采用模拟信号滤波的方法解决，直到1965年首次提出DFT运算的一种快速算法以后，情况才发生了根本变化，人们开始认识到DFT运算的一些内在规律，从而很快地发展和完善了一套高速有效的运算方法——快速付里变换（FFT）算法。FFT的出现，使DFT的运算大大简化，运算时间缩短一～二个数量级，使DFT的运算在实际中得到广泛应用。6.1引言一.DFT的计算工作量两者的差别仅在指数的符号和因子1/N.1,,1,0,)()(10NkWnxkXNnnkN101,,1,0,)(1)(NknkNNnWkXNnx通常x(n)和都是复数,所以计算一个X(k)的值需要N次复数乘法运算,和次复数加法运算.那么,计算全部N点的X(k)就要N2次复数乘法运算,N(N-1)次复数加法运算.一般来说,乘法运算要比相加运算复杂,为讨论简单起见,我们以复数乘法运算次数近似作为运算工作量的衡量标准.当N很大时,运算量将是惊人的,如N=1024,则要完成1048576次(一百多万次)运算.这样,难以做到实时处理.nkNW1N一个X(k)的值的工作量,如X(1)1210)1()2()1()0()1(NNNNNWNxWxWxWxX二.改进的途径1.的对称性和周期性nkNW;,)()()(*NknNkNnNnkNnkNnkN.),1(1),1()2/(2/)(2)()(2kNNkNjNNNnkNnNNkNnkNknNNkNnNWWeWWe得:对称性:周期性:利用上述特性,可以将有些项合并22)()()(NNNkXkXkX把N点数据分成两半：其运算量为：2)2(N2)2(N2N再分两半：44)()(NNkXkX44)()(NNkXkX+=22N2)4(N2)4(N2)4(N2)4(N+++=24N这样一直分下去，剩下两点的变换。2.把长度为N点的大点数的DFT运算依次分解为若干个小点数的DFT。因为DFT的计算量正比于N2，N小，计算量也就小。FFT算法正是基于这样的基本思想发展起来的。1965年,库利(cooley)和图基(Tukey)首先提出FFT算法.对于N点DFT,仅需(N/2)log2N次复数乘法运算.例如N=1024=210时，需要(1024/2)log2210=512*10=5120次。5120/1048576=4.88%,速度提高20倍.应用第三代数字信号处理器TMS320C30-40，具有50ns的单周期执行时间，每秒20000次浮点运算，完成乘法、加法及运算控制、数据存取共需约1s左右，而采用FFT算法，计算时间可缩减为2.366ms。FFT有多种形式，但基本上可分为两类：时间抽取法和频率抽取法。按“基数”分：基-2FFT算法；基-4FFT算法；混合基FFT算法；分裂基FFT算法其它方法：线性调频Z变换(CZT法)1.设输入序列长度为N=2L(L为正整数，将该序列按时间顺序的奇偶分解为越来越短的子序列，称为基2按时间抽取的FFT算法。也称为Coolkey-Tukey算法。2.其中基数2----N=2L，L为整数.若不满足这个条件，可以人为地加上若干零值（加零补长）使其达到N=2L6.2按时间抽取(DIT)的FFT算法—库利-图基算法算法原理(1).N/2点DFT1.先将按n的奇偶分为两组作DFT,这样有:n为偶数时:n为奇数时:1,,1,0),()12(1,,1,0),()2(2221NNrrxrxrrxrx10)()]([)(NnnkNWnxnxDFTkX因此，)(nx由于:所以,上式可表示为:1022102110)12(10210102222))(())(()12()2()()()(NNNNrrkNkNrrkNrkrNrrkNNnNnnkNnkNWrxWWrxWrxWrxWnxWnxkX(n为偶数)(n为奇数)222)/(222NNNWeeWjjN)()()()()(211021012222kXWkXWrxWWrxkXkNrrkkNrrkNNNN其中,2.两点结论:(1)X(k),X(k)均为N/2点的DFT。(2)X(k)=X(k)+WX(k)只能确定出X(k)的k=个；即前一半的结果。1212kN10102210101122222222)12()()()2()()(NNNNNNNNrrkrrkrrkrrkWrxWrxkXWrxWrxkX1,,1,02N同理,这就是说,X1(k),X2(k)的后一半,分别等于其前一半的值。3.X(k)的后一半的确定rkkrNNNWW222)()()()()2(1101)(101122222kXWrxWrxkNXNNNNNrrkkrr由于（周期性）,所以:)()2(22kXkNX可见,X(k)的后一半，也完全由X1(k),X2(k)的前一半所确定。*N点的DFT可由两个N/2点的DFT来计算。kNkNNkN22)()2()2()2(212NkXWNkXNkXNkN1,,1,0),()(221NkNkkXWkX又由于,所以实现上式运算的流图称作蝶形运算前一半4.蝶形运算后一半（N/2个蝶形)(前一半)(后一半)1111-1)()()()()()(2121kXWkXkXkXWkXkXkNkN)1,,()1,,1,0(22NkkNN)()()(21kXWkXkXkN)()()2(21kXWkXkNXkN)(1kX)(2kXkNW由X1(k)、X2(k)表示X(k)的运算是一种特殊的运算-碟形运算X1(k)X2(k)kNW)()(21kXWkXkN)()(21kXWkXkN作图要素：(1)左边两路为输入(2)右边两路为输出(3)中间以一个小圆表示加、减运算（右上路为相加输出、右下路为相减输出)(4)如果在某一支路上信号需要进行相乘运算，则在该支路上标以箭头，将相乘的系数标在箭头旁。(5)当支路上没有箭头及系数时，则该支路的传输比为1。(1)N/2点的DFT运算量:复乘次数:复加次数:(2)两个N/2点的DFT运算量:复乘次数:复加次数:(3)N/2个蝶形运算的运算量:复乘次数:复加次数:5.计算工作量分析复乘:复加:4)2(22NN)12(2NN22N)12(NN2NNN222)12(2NNNN22222NNN总共运算量:按奇、偶分组后的计算量：但是,N点DFT的复乘为N2;复加N(N-1);与分解后相比可知,计算工作点差不多减少一半。例如N=8时的DFT,可以分解为两个N/2=4点的DFT.具体方法如下:(1)n为偶数时,即分别记作:)(42/1kXDFTN，得点的进行3,2,1,0)2()()(30430411kWrxWrxkXrrkrrk);6()3(),4()2(),2()1(),0()0(1111xxxxxxxx);6(),4(),2(),0(xxxx(2)n为奇数时,分别记作:);7()3(),5()2(),3()1(),1()0(2222xxxxxxxx3,2,1,0)12()()(30430422kWrxWrxkXrrkrrk)(42/2kXDFTN，得点的进行3,2,1,0),()()4()()()(2121kkXWkXkXkXWkXkXkNkNx1(0)=x(0)x1(1)=x(2)N/2点x1(2)=x(4)DFTx1(3)=x(6)x2(0)=x(1)x2(1)=x(3)N/2点x2(2)=x(5)DFTx2(3)=x(7)~~X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)WN2WN1WN0WN3-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)(3)对X1(k)和X2(k)进行蝶形运算,前半部为X(0)X(3),后半部分为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=2L,所以N/2仍为偶数,可以进一步把每个N/2点的序列再按其奇偶部分分解为两个N/4的子序列。例如，n为偶数时的N/2点分解为:(2).N/4点DFT1,,1,0),()2(431Nlxlx1,,1,0),()12(441Nlxlx进行N/4点的DFT,得到klNllkNllkNllkNlWlxWlxkXWlxWlxkXNNNN)12(2/1014/104422/1014/1033)12()()()2()()(4444(偶中偶)(偶中奇))()()(4312kXWkXkXkN1,,1,04Nk从而可得到前N/4的X1(k))()()4(4312kXWkXkNXkN后N/4的X1(k)为1,,1,04Nk一个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()(NNNNllkNlkNlllkNllkNWlxWlxkXWlxWlxkX(奇中奇)同样对n为奇数时，N/2点分为两个N/4点的序列进行DFT，则有:14,,1,0k;(k)XW(k)X(k)X6kN/252N14,,1,0k;(k)XW(k)Xk)4N(X6kN/252N进行碟形运算，得：、由)()(65kXkX另一个2点的DFT蝶形流图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()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)11121222(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)xxxxxxxx因此,8点DFT的FFT的运算流图如下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/0NNNWW其中旋转因子，共有m=0m=1m=2m为级数,N=2M所以N点DFT可分成M级2点DFT2