4第四讲_快速傅里叶变换.

§4-5线性卷积的FFT算法§4-3按频率抽取DIF的FFT算法§4-4IFFT算法§4-2按时间抽取(DIT)的FFT算法§4-1引言§4-1引言一.DFT的计算工作量两者的差别仅在指数的符号和因子1/N.1,,1,0,)()(10NkWnxkXNnnkN101,,1,0,)(1)(NknkNNnWkXNnx通常x(n)和都是复数,所以计算一个X(k)的值需要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2()()2()/2(/2)(1),1(1),.NnNkNnknkNkNnjknNNNNNNjNNkNkNN得:对称性:周期性:利用上述特性,可以将有些项合并,并将DFT分解为短序列,从而降低运算次数,提高运算速度.1965年,库利(cooley)和图基(Tukey)首先提出FFT算法.对于N点DFT,仅需(N/2)log2N次复数乘法运算.例如N=1024=210时，需要(1024/2)log2210=512*10=5120次。5120/1048576=4.88%,速度提高20倍§4-2按时间抽取(DIT)的FFT算法—库利-图基算法一.算法原理(基2FFT)(一)N/2点DFT1.先将按n的奇偶分为两组作DFT,设N=2L,不足时,可补些零。这样有: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)的运算是一种特殊的运算-碟形运算(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)12~~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)对X(k)和X(k)进行蝶形运算,前半部为X(0)X(3),后半部分为X(4)X(7)整个过程如下图所示:由于N=2L,所以N/2仍为偶数,可以进一步把每个N/2点的序列再按其奇偶部分分解为两个N/4的子序列。例如，n为偶数时的N/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(奇中偶)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例如,N=8时的DFT可分解为四个N/4的DFT,具体步骤如下:)4()2()1()0()0()0()()()(131313xxxxxxnxrxlx(1)将原序列x(n)的“偶中偶”部分:构成N/4点DFT，从而得到X3(0),X3(1)。)6()3()1()2()1()0()()()(141414xxxxxxnxrxlx(2)将原序列x(n)的“偶中奇”部分:构成N/4点DFT，从而得到X4(0),X4(1)。(3)将原序列x(n)的“奇中偶”部分:)5()2()1()1()0()0()()()(252525xxxxxxnxrxlx构成N/4点DFT，从而得到X5(0),X5(1)。(4)将原序列x(n)的“奇中奇”部分:)7()3()1()3()1()0()()()(262626xxxxxxnxrxlx构成N/4点DFT，从而得到X6(0),X6(1)。（5）由X3(0),X3(1),X4(0),X4(1)进行碟形运算,得到X1(0),X1(1),X1(2),X1(3)。（6）由X5(0),X5(1),X6(0),X6(1)进行碟形运算,得到X2(0),X2(1),X2(2),X2(3)。(0)=(0)=(0)N/4(1)=(2)=(4)DFT(0)=(1)=(2)N/4(1)=(3)=(6)DFT(0)=(0)=(1)N/4(1)=(2)=(5)DFT(0)=(1)=(3)N/4(1)=(3)=(7)DFT313141415252626202NN02NN(0)X(1)X(0)X(1)X(0)X(1)X(0)X(1)33445566X(0)X(1)X(2)X(3)X(0)X(1)X(2)X(3)11122221X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)（7）由X1(0),X1(1),X1(2),X1(3)，X2(0),X2(1),X2(2),X2(3)进行碟形运算,得到X(0),X(1),X(2),X(3)X(4),X(5),X(6),X(7)。这样,又一次分解,得到四个N/4点DFT,两级蝶形运算,其运算量有大约减少一半即为N点DFT的1/4。对于N=8时DFT,N/4点即为两点DFT,因此0,1k,)()(0,1k,)()(0,1k,)()(0,1k,)()(4/1066104/55104/44104/33lkNlllkNllkNllkNWlxkXWlxkXWlxkXWlxkX亦即,)4()0()1()0()1()4()0()1()0()0(031233030233xWxxWxXxWxxWxXNN)6()2()1()0()1()6()2()1()0()0(041244040244xWxxWxXxWxxWxXNN)5()1()1()0()1()5()1()1()0()0(051255050255xWxxWxXxWxxWxXNN)7()3()1()0()1()7()3()1()0()0(061266060266xWxxWxXxWxxWxXNN(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的运算流图如下这种FFT算法,是在时间上对输入序列的次序是属于偶数还是属于奇数来进行分解的,所以称作按时间抽取的算法。二.运算量由上述分析可知,N=8需三级蝶形运算N=2=8,由此可知,N=2L共需L级蝶形运算,而且每级都由N/2个蝶形运算组成,每个蝶形运算有一次复乘,两次复加。(DIT)3因此,N点的FFT的运算量为复乘:mF=（N/2）L=（N/2）log2N复加:aF=NL=Nlog2N(0)=X0(0)X1(0)X2(0)X3(0)=X(0)(4)=X0(1)X