fft蝶形算法.ppt

《fft蝶形算法.ppt》由会员分享，可在线阅读，更多相关《fft蝶形算法.ppt（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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为整数n

2、NWWnmknNmkN/,/将时域序列逐次分解为一组子序列，利用旋转因子的特性，由子序列的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,

3、241mmXWmXmXm1 , 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算法流图第一级第一级第二级第二级第三级第三级复

4、乘次数NN2log2复乘次数NN 2NN2log2第一级第一级第二级第二级第三级第三级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算法算法mkNNNkmkNNkWk

5、xWkxmX12/12/0 )2/(12/012/02/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

6、x3x1x2x4x5x6x70NW2NW2点点DFT-1-1-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