电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

完整版按时间抽取的基2FFT算法分析VIP免费

完整版按时间抽取的基2FFT算法分析_第1页
1/15
完整版按时间抽取的基2FFT算法分析_第2页
2/15
完整版按时间抽取的基2FFT算法分析_第3页
3/15
57 第四章快速傅里叶变换有限长序列可以通过离散傅里叶变换(DFT) 将其频域也离散化成有限长序列 .但其计算量太大,很难实时地处理问题,因此引出了快速傅里叶变换(FFT). 1965 年, Cooley 和 Tukey 提出了计算离散傅里叶变换(DFT )的快速算法,将 DFT 的运算量减少了几个数量级。从此,对快速傅里叶变换 (FFT)算法的研究便不断深入,数字信号处理这门新兴学科也随FFT 的出现和发展而迅速发展。根据对序列分解与选取方法的不同而产生了FFT 的多种算法,基本算法是基2DIT 和基2 DIF 。FFT 在离散傅里叶反变换、线性卷积和线性相关等方面也有重要应用。快速傅里叶变换(FFT)是计算离散傅里叶变换(DFT )的快速算法。DFT 的定义式为)(kX=)()(10kRWnxNNnknN在所有复指数值knNW的值全部已算好的情况下,要计算一个)(kX需要N次复数乘法和N- 1 次复数加法。算出全部N 点)(kX共需2N次复数乘法和)1(NN次复数加法。即计算量是与2N成正比的。FFT 的基本思想:将大点数的DFT 分解为若干个小点数DFT 的组合,从而减少运算量。NW因子具有以下两个特性,可使 DFT 运算量尽量分解为小点数的DFT运算:(1)周期性:kNnNknNnNkNWWW)()((2)对称性:kNNkNWW)2/(58 利用这两个性质,可以使DFT 运算中有些项合并,以减少乘法次数。例子:求当 N=4 时, X(2) 的值)()]3()1([)]2()0([)()]3()1([)]2()0([)3()2()1()0()()2(042404644424043024对称性-=周期性WxxxxWxxWxxWxWxWxWxWnxXnn通过合并,使乘法次数由4 次减少到 1 次,运算量减少。FFT 的算法形式有很多种,但基本上可以分为两大类:按时间抽取(DIT )和按频率抽取(DIF)。4.1 按时间抽取( DIT )的 FTT 为了将大点数的DFT 分解为小点数的DFT 运算,要求序列的长度N 为复合数,最常用的是MN2的情况( M 为正整数)。该情况下的变换称为基 2FFT。下面讨论基2 情况的算法。先将序列 x(n)按奇偶项分解为两组)()12()()2(21rxrxrxrx12,,1,0Nr将 DFT 运算也相应分为两组)]([)(nxDFTkX10)(NnknNWnx1n 010)()(NnknNNnnknNWnxWnx为奇数为偶数+12/0)12(12/02)12()2(NrkrNNrrkNWrxWrx=59 12/02212/021)()(NrrkNkNNrrkNWrxWWrx=12/02/212/02/1)()(NrrkNkNNrrkNWrxWWrx=(因为rkNrkNWW2/2))()(21kXWkXkN其中)(1 kX、)(2 kX分别是)()(21nxnx、的 N/2 点的 DFT )(1 kX120,)2()(12/02/12/02/1NkWrxWrxNrrkNNrrkN=)(2 kX120,)12()(12/02/12/02/2...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

完整版按时间抽取的基2FFT算法分析

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部