1、4点序列点序列2，3，3，2 DFT的计算复杂度的计算复杂度1,1,0,10NmWkxmXkmNNk10233200000NNNNWWWWXjWWWWXNNNN12332 1 32100233226420NNNNWWWWXjWWWWXNNNN1233239630复数加法复数加法 N(N-1)复数乘法复数乘法 N 2如何提高DFT的运算效率?1.将长序列DFT分解为短序列的DFT2.利用旋转因子 的周期性、对称性、可约性。kmNWkmNWkmNNmkNmNkNWWW)()(1)周期性周期性2)对称性对称性mkNkmNWW3)可约性可约性mkNNmkNWW2nmknNmkNWW为整数nNWWnmk
2、nNmkN/,/将时域序列逐次分解为一组子序列，利用旋转因子的特性，由子序列的DFT来实现整个序列的DFT。基基2时间抽取时间抽取(Decimation in time)FFT算法算法12,1,0 122Nrrxrxkx基基2频率抽取频率抽取(Decimation in frequency)FFT算法算法 122mXmXmXN=2xk=x0,x1 1 0002xWxX 1 0 1 12xWxX0 x 1 x0X-102W 1 X 1 002xWxx0 x2x1x3X10X11X20X212点DFT2点DFT111104W14W02W02WX 0X 1X 2X 31,0,241mmXWmXmXm
3、1,0,2241mmXWmXmXm4点DFT4点DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7111108W18W28W38W3,2,1,0,4281mmXWmXmXm3,2,1,0,281mmXWmXmXm4点DFT4点DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7111108W18W28W38W8点基2时间抽取FFT算法流图第一级第一级第二级第二级第三级第三级复乘次数NN2log2复乘次数NN 2NN2log2第
4、一级第一级第二级第二级第三级第三级PNW第二级的蝶形系数为 ，蝶形节点的距离为2。4/0,NNNWW第一级的蝶形系数均为 ，蝶形节点的距离为1。0NW第三级的蝶形系数为 ，蝶形节点的距离为4。8/38/28/0,NNNNNNNWWWW第M级 的蝶形系数为 ，蝶形节点的距离为N/2。)12/(10,NNNNWWW倒序倒序k0k1k2xk2 k1k0 x000 x100 x0100101112 xk k0 xk2 k101x110 x001x101x011x11101010101 基基2频率抽取频率抽取FFT算法算法mkNNNkmkNNkWkxWkxmX12/12/0 )2/(12/012/02/
5、NkmNNkmkNNkWNkxWkx mkNmNkWNkxkx2/)1(12/0 rkNNkWNkxkxrX2/12/02/2 rkNkNNkWWNkxkxrX2/12/02/12 rkNNkWNkxkxrX2/12/02/2 rkNkNNkWWNkxkxrX2/12/02/12 12/1,0 Nr3NW-1-12NW-1-11NW-1-10NW-1-1x0 x4x1x5x2x6x3x74点点DFTX0X6X2X44点点DFTX1X3X5X7X0X6X4X2X1X5X3X70NW1NW2NW3NW-1-1-1-1-1-1-1-1x0 x3x1x2x4x5x6x70NW2NW2点点DFT-1-1
6、-1-12NW0NW-1-1-1-12点点DFT2点点DFT2点点DFT0NW1NW2NW3NW-1-1-1-1-1-1-1-1x0 x3x1x2x4x5x6x70NW2NW2NW0NWX0X6X4X2X1X5X3X70NW0NW0NW0NW-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1利用利用N点复序列的点复序列的FFT算法计算算法计算两个两个N点实序列点实序列FFTx1k,x2k是实序列，将其构成复序列yk=x1k+j x2kDFTx1k+j x2k=YR m+jYI m?1kxDFT?2kxDFT21kjxkxDFT)()(NINRmjYmY)()(211NIINRRmYmYjmYmYkxDFT)()(212NIINRRmYmYjmYmYjkxDFTyk是一个长度为2N的序列1,1,0 12221Nkkykxkykxky1,1,0 221221NmmXWmXNmYmXWmXmYmNmN问题：如何利用利用N点点FFT，计算，计算4N点序列的点序列的FFT？利用利用FFT实现实现IFFTmkNNkWkxkxDFTmX10mkNNmWmXNmXIDFTkx110mkNNmWmXNkx110步骤：A)将X m取共轭)mXDFTFFTB流图计算用C)对B)中结果取共轭并除以N
