基2时域频域FFT算法课件.ppt
《基2时域频域FFT算法课件.ppt》由会员分享,可在线阅读,更多相关《基2时域频域FFT算法课件.ppt(34页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、4 4点序列点序列22,3 3,3 3,2 DFT2 DFT的计算复杂度的计算复杂度1, 1 , 0,10NmWkxmXkmNNk10233200000NNNNWWWWXjWWWWXNNNN12332 1 32100233226420NNNNWWWWXjWWWWXNNNN1233239630如何提高DFT的运算效率?问题的提出 一般性11 , 0;10NmWkxmXkmNNkDFT:直接计算的计算量:N-1复数乘法 N对N个不同Xm复数加法 N(N-1)复数乘法N2对一固定的m复数加法如计算1024点DFT: 复数乘法次数: N2 =10242 = 220 = 1048576 解决问题的思路1
2、.将长序列DFT分解为短序列的DFT2.利用旋转因子 的周期性、对称性、可约性。kmNWkmNNmkNmNkNWWW)()(1)周期性(periodicity)2)复共轭对称性(complex conjugate)kmNmNkNmkNNWWW)()(3)当N是偶数时kmNmkNWW2/)2(2/NmNWmNWkmNW的性质的性质解决问题的方法 将时域序列逐次分解为一组子序列,利用旋转因子的特性,由子序列的DFT来实现整个序列的DFT。基2时间抽取(Decimation in time)FFT算法12, 1 , 0 122Nrrxrxkx基2频率抽取(Decimation in frequenc
3、y)FFT算法 122mXmXmX3.1 基2时域抽取FFT算法算法推导: N=2M时域抽取(Decimation in time)kmNNkWkxmX1012/, 1 , 0; 1 , 0;2Nrllrka1kx2lx21lxkxa+21lxkxa-1(一)算法原理 基本蝶形(butterfly)mrNNrrmNNrWrxWrxmX) 12(12/0212/0 122rmNNrmNrmNNrWrxWWrx2/12/02/12/0 122rmNNrrmNNrWrxmXWrxmX2/12/022/12/01 122记2/2/2/22/1NmXWNmXNmXNmN21mXWmXmN算法推导: N=
4、2M时域抽取21mXWmXmXmN2/21mXWmXNmXmN12/1 , 0Nm例: 1 0,00, 0, 221xXxXmN 1 00 xxX 1 0 1 xxX0X 1 X-110 x 1 x2点FFT流图N=2基2时域FFT流图的推导N=4时域基2FFT流图的推导-1X2X3-12点DFT2点DFTx0 x3x1x2X004WX114W01X 1 1X02X 1 2X21mXWmXmXmN 2/21mXWmXNmXmN2点DFT04W14Wx0 x3x1x2X3X1X2X0-1-1-1-1N=8基2时域FFT流图的推导08W18W28W38W4点DFT4点DFTX0X3X1X2X4X5
5、X6X7x0 x6x2x4x1x3x5x7-1-1-1-121mXWmXmXmN 2/21mXWmXNmXmN12/1 , 0Nm08W18W28W38WX0X3X1X2X4X5X6X7x0 x6x4x2x1x5x3x704W14W04W14W-1-1-1-1-1-1-1-1-1-1-1-18点FFT流图第三级第一级第二级(二 ) 算法工作量a1kx2lx21lxkxa21lxkxa-1一个蝶形计算量: 复数乘法 1,复数加法 2复数乘法:N,NNM2log22复数加法:NNNM2log22N=2M时,分解级数为 M,每级蝶形数 N/2计算1024点复数乘法次数: DFT: N 2 =1024
6、 2 = 220 = 1048576 ;FFT:5120log22NN(三) 流图规律1) 原位运算(In-place Computations)a1kx2lx21lxkxa21lxkxa-1优点:节省存储空间(三) 流图规律PNW第二级的蝶形系数为 ,蝶形节点的距离为2。4/0,NNNWW第一级的蝶形系数均为 ,蝶形节点的距离为1。0NW第三级的蝶形系数为 ,蝶形节点的距离为4。8/38/28/0,NNNNNNNWWWW第M级的蝶形系数为 ,蝶形节点的距离为N/2。) 12/(10,NNNNWWW2)FFT算法流图旋转因子 规律3)倒序规律k0k1k2xk2 k1k0 x000 x100 x
7、0100101112 xk k0 xk2 k101x110 x001x101x010 x11101010101试利用N=4基2时间抽取的FFT流图计算8点序列xk=1, -1, 1, -1, 2, 1, 1, 2的DFT。解: 根据基2时间抽取FFT算法原理,8点序列的DFT Xm可由两个4点序列的DFT X1m和X2m表达。如果按照序列xk序号的奇偶分解为x1k和 x2k,则存在 3 , 2 , 1 , 04281281mmXWmXmXmXWmXmXmm 其中x1k=1, 1, 2, 1,x2k=-1, -1, 1, 2,X1m和X2m可通过4点的FFT来计算。解:-1-1-1-j12115
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 时域 FFT 算法 课件
限制150内