第四讲快速傅里叶变换

1、4-5线性卷积的FFT算法4-3按频率抽取DIF的FFT算法4-4 IFFT算法4-2按时间抽取(DIT)的FFT算法4-1 引言1, 1 , 0 ,)()(10NkWnxkXNnnkN101, 1 , 0 ,)(1)(NknkNNnWkXNnxnkNW1N一个X(k)的值的工作量,如X(1)1210) 1() 2() 1 () 0() 1 (NNNNNWNxWxWxWxXnkNW;,)()()(*NknNkNnNnkNnkNnkNWWWWW2()()2( )/2(/2)(1),1(1),.Nn N kN n knkNkNnjk nNNNNNNjNNk NkNNWWWWWeWWeWW得:对称性

2、:周期性:1, 1 , 0 ),() 12(1, 1 , 0 ),()2(2221NNrrxrxrrxrx10)()()(NnnkNWnxnxDFTkX因此，)(nx1022102110)12(10210102222)()()12()2()()()(NNNNrrkNkNrrkNrkrNrrkNNnNnnkNnkNWrxWWrxWrxWrxWnxWnxkX(n为偶数) (n为奇数)222)/(222NNNWeeWjjN)()()()()(211021012222kXWkXWrxWWrxkXkNrrkkNrrkNNNN1 21 2kN10102210101122222222) 12()()()2(

3、)()(NNNNNNNNrrkrrkrrkrrkWrxWrxkXWrxWrxkX1, 1 , 02 NrkkrNNNWW222)()()()()2(1101)(101122222kXWrxWrxkNXNNNNNrrkkrr由于 （周期性）（周期性）, ,所以:)()2(22kXkNXkNkNNkNWWWWNN22)()2()2()2(212NkXWNkXNkXNkN1, 1 , 0 ),()(221NkNkkXWkX又由于 , ,所以 前一半4.4.蝶形运算蝶形运算 后一半（N/2个蝶形)(前一半)(后一半)1 1 11-1-1)()()()()()(2121kXWkXkXkXWkXkXkNk

4、N)1,()1, 1 ,0(22 N Nk kk kN NN N)()()(21kXWkXkXkN)()()2(21kXWkXkNXkN)(1kX)(2kXkNW由X1(k)、X 2(k)表示X(k)的运算是一种特殊的运算-碟形运算5. .计算工作量分析计算工作量分析复乘:复加:4)2(22NN)12(2NN22N)12(NN2NNN222)12(2NNNN22222NNN总共运算量:按奇、偶分组后的计算量： *但是,N N点DFTDFT的复乘为N N2 2 ; ;复加N(N-1);N(N-1);与分解后相比可知,计算工作点差不多减少 一半。)(42/1kXDFTN，得点的进行3 , 2 ,

5、1 , 0)2()()(30430411kWrxWrxkXrrkrrk);6()3(),4()2(),2()1(),0()0(1111xxxxxxxx);6(),4(),2(),0(xxxx);7()3(),5()2(),3()1(),1()0(2222xxxxxxxx3 , 2 , 1 , 0) 12()()(30430422kWrxWrxkXrrkrrk)(42/2kXDFTN，得点的进行3 , 2 , 1 , 0),()() 4()()()(2121kkXWkXkXkXWkXkXkNkN1 2 X X1(0)(0)X X1(1)(1)X X1(2)(2)X X1(3)(3)X X2(0)

6、(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)( (二二) N/4) 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( (偶中偶) )(

7、(偶中奇) )()()(4312kXWkXkXkN1, 1 , 04Nk从而可得到前N/4的X1(k)()()4(4312kXWkXkNXkN后N/4的X1(k)为1, 1 , 04Nk( (奇中偶奇中偶) )104/64/1026104/5104/254444)()12()()()2()(NNNNllkNlkNlllkNllkNWlxWlxkXWlxWlxkX( (奇中奇奇中奇) )同样对n n为奇数时，N/2N/2点分为两个N/4N/4点 的序列进行DFT，则有:14, 1 , 0k; (k)XW(k) X(k) X6kN/252N14, 1 , 0k; (k)XW(k) Xk)4N( X

8、6kN/252N进行碟形运算，得：、由)()(65kXkX 例如,N=8N=8时的DFTDFT可分解为四个N/4N/4的DFT,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()

9、()()(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)。3 13 14 14 15 25 26 26 2

10、 02NN02NNWWWW0123NNNN-1-1-1-2-1-1WWWWX (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)xxxxxxxxxxxxxxxxxxxxxxxx（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

11、) 。0,1k ,)()(0,1k ,)()(0,1k ,)()(0,1k ,)()(4/1066104/55104/44104/33lkNlllkNllkNllkNWlxkXWlxkXWlxkXWlxkX)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(051255050255xWxxWxXxWxxWxXN

12、N)7() 3() 1 ()0() 1 ()7() 3() 1 ()0()0(061266060266xWxxWxXxWxxWxXNNWN0WN0WN0W0N-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)X(6)X(7)xxxxxxxx( (DITDIT) )3 3WWWWN0N0N0N0-1-1-1-1WW

13、WWN0N2N0N2-1-1-1-1WWWWNNNN0123.三三.DIT.DIT的的FFTFFT算法的特点算法的特点 1.1.原位运算输入数据、中间运算结果和最后输出均用同一存储器。xxxxxxxxrNmmmrNmmmWjXkXjXWjXkXkX)()()()()()(1111),3()6(),2()2(),1 ()4(),0()0(0000XxXxXxXx).7()7(),6()3(),5()5(),4() 1 (0000XxXxXxXx 设用m(m=1,2, ,L)表示第m列; ;用用k,jk,j表示蝶形输入数据所在的（上/下）行数(0,1,2,(0,1,2, ,N-1); ,N-1);

14、这时任何一个蝶形运算可用下面通用式表示， 即 由运算流图可知,一共有N N个输入个输入/ /出出行,一共有loglog2 2 N=LN=L列（级）蝶形运算( (基本迭代运算). ). 00010001)1()0()1()1()0()0(NNWXXXWXXX00010001)3()2()3()3()2()2(NNWXXXWXXX2112211201120112)3()1()3()3()1()1()2()0()2()2()0()0(NNNNWXXXWXXXWXXXWXXX1223122302230223)5()1()5()5()1()1()4()0()4()4()0()0(NNNNWXXXWXXX

15、WXXXWXXX)(),(jXkXmm)(),(11jXkXmm）；）；7 (),3 (),5 (),1 (6 (),2(),4(),0 (xxxxxxxxn =00n =10n =01n =11n =01n =1101010101 ),(012nnnx(n2)x(000) 0 乾x(100) 4 兑x(010) 2 离x(110) 6 震x(001) 1巽x(101) 5 坎x(011) 3 艮x(111) 7 坤（偶）（奇） 这是由奇偶分组造成的,以N=8N=8为例 说明如下:n 自然顺序n n 二进制n n n n n n 倒位序二进制n n n n n n 倒位顺序n n2 1 0 0

16、 1 2A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(8)x(0) x(1) x(2) x(3) x(4) x(5) x(6) x(7)x(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7)变址处理方法变址处理方法存储单元自然顺序变址倒位序4.4.蝶形运算两节点的距离蝶形运算两节点的距离: :2m-1 其中,m表示第m列, ,且且m =1,=1, ,L ,L 例如N=8=2N=8=23 3 , ,第一级( (列) )距离为2 21-11-1=1,=1, 第二级( (列) )距离为2 22-12-1=2=2， 第三级( (列) )距离为2 23

17、-13-1=4=4。 为此，令k=(n2n1n0)2 , ,再再将k= (n2n1n0)2 左移(L-m)位,右边位置补零,就可得到(r)2 的值，即(r)2 =(k)22L-m 。 xr rN NW W4-3 DIF4-3 DIF的的FFTFFT算法算法( (桑德桑德图基算法图基算法) )10)()(NnnkNWnxkX10)(1012/102222)2()()()(NNNNnknNnnkNNNnnkNnnkNWNnxWnxWnxWnxnkNnkNWWNnxnxNN1022)2()(, 12jNeWNkkNNW) 1(2nkNnkWNnxnxkXN102)2() 1()()(1, 1 , 0

18、NknrnnrNnNNNWNnxnxWNnxnx22210210)2()()2()()2( rX1, 1 , 02Nrk k为偶数时：nrnnNrnNnNNNWWNnxnxWNnxnxrX22210)12(10)2()()2()() 12(xxk k为奇数时：1, 1 , 02Nr-1-1)2()(Nnxnx1, 1 ,02NnnNWNnxnx)2()(3.3.蝶形运算进行如下碟形运算：和)2()(NnxnxnNW)2(Nnx)(nx-1-1-1-1-1-1-1-1W WW WW WW WN NN NN NN N0 01 12 23 34.N=4.N=8 8时时, ,按按k k的奇偶分解过程的

19、奇偶分解过程 先蝶形运算，后先蝶形运算，后DFT:DFT:)0( x) 1 ( x)5( x)4( x) 3( x)2( x)7( x)6( x)0(X)2(X)6(X) 1 (X) 3(X)5(X)7(X)4(XDFTN点2DFTN点2-1-1-1-1-1-1-1-1W WW WW WW WN NN NN NN N0 01 12 23 3-1-1-1-1-1-1-1-1W WW WW WW WN NN NN NN N0 02 20 02 2-1-1-1-1-1-1-1-1W WW WW WW WN NN NN NN N0 00 00 00 0 xxxxxxxx例如 N=8N=8时DIFDIF

20、的FFTFFT流图如下： -1-1W WN Nr rrNmmmmmmWjXkXjXjXkXkX)()()()()()(1111)(1kXm)(1jXm)()()(11jXkXkXmmmrNmmmWjXkXjX)()()(11三三.蝶形运算两节点的距离蝶形运算两节点的距离rNmmmmmmmmmWNkXkXNkXNkXkXkX)2()()2()2()()(1111四四. . 的计算的计算 由于DIFDIF蝶形运算的两节点的距离为 N/2m , , 所以蝶形运算可表为：rNW五五.DIFDIF法与法与DITDIT法的异同法的异同rNmmmWjXkXjX)()()(11rNmmmWjXkXkX)()(

21、)(11)(1kXm)(1jXmrNW1(2)(2)蝶形运算不同a.a.(DIT)(DIT)用矩阵表示)(kXm)(jXmrNWrNW)(1kXm)(1jXm=11rNmmmWjXkXjX)()()(11)()()(11jXkXkXmmm)(1kXm)(1jXmrNW1b.b.(DIF)(DIF)用矩阵表示)(kXm)(jXmrNWrNW)(1kXm)(1jXm=11 将流图的所有支路方向都反向, ,交换输入和输出，即可得到另一种蝶形。 a.a.(DIT)(DIT)b.b.(DIF)(DIF)rNWrNW1111rNWrNWnkNNkNnnkNWkXNkXIDFTnxWnxnxDFTkX1010)(1)()()(