按时间抽取的FFT算法合集课件.ppt

上传人(卖家):三亚风情 文档编号:3326159 上传时间:2022-08-20 格式:PPT 页数:28 大小:1.27MB
下载 相关 举报
按时间抽取的FFT算法合集课件.ppt_第1页
第1页 / 共28页
按时间抽取的FFT算法合集课件.ppt_第2页
第2页 / 共28页
按时间抽取的FFT算法合集课件.ppt_第3页
第3页 / 共28页
按时间抽取的FFT算法合集课件.ppt_第4页
第4页 / 共28页
按时间抽取的FFT算法合集课件.ppt_第5页
第5页 / 共28页
点击查看更多>>
资源描述

1、时间抽选法时间抽选法DIT:Decimation-In-Time频率抽选法频率抽选法DIF:Decimation-In-Frequency7-2 按按时间抽取的FFT算法一、按时间抽取的算法原理二、按时间抽取的算法特点三、按时间抽取FFT算法的其他形式22022-8-12一、按时间抽取的算法原理设序列点数 N=2L,L 为整数。若不满足,则补零N为2的整数幂的FFT算法称基-2FFT算法。将序列x(n)按n的奇偶分成两组:3 12221xrx rxrxr0,1,.,/2 1rN2022-8-124 则则x(n)的的DFT:111000NNNnknknkNNNnnnXkx n Wx n Wx n

2、 Wn为偶数n为奇数/2 1/2 121200221NNrkrkNNrrxr WxrW /2 1/2 1221200NNrkrkkNNNrrx rWWxrW /2 1/2 11/22/200NNrkkrkNNNrrx r WWxr W 12kNXkW Xk,0,1,./2 1r kN2022-8-125 再利用周期性求再利用周期性求X(k)的后半部分的后半部分 121122,/222XkXkNNNXkXkXkXk是以为周期的/22NkNkkNNNNWWWW 又2022-8-1261212()()()()()()2kNkNX kX kW XkNX kX kW Xk0,1,.,/21kN 一个一个

3、“蝶形运算蝶形运算”包含包含1次乘法,次乘法,2次加法次加法2022-8-1272022-8-12复数乘法复数乘法复数加法复数加法一个一个N/2点点DFT(N/2)2N/2(N/2 1)两个两个N/2点点DFTN 2/2N(N/2 1)一个蝶形一个蝶形12N/2个蝶形个蝶形N/2N总计总计8分解后的运算量:分解后的运算量:运算量减少了近一半运算量减少了近一半22/2/2/2NNN2/2 1/2N NNN2022-8-12N/2仍为偶数,进一步分解:N/2 N/491314(2)()(21)()xlxlxlxl0,1,.,/41lN13/2413/24()()()()()()4kNkNXkXkW

4、XkNXkXkWXk0,1,.,14Nk 2022-8-12102/2kkNNWW统一系数:10同理同理:25/2625/26()()()()()()4kNkNXkXkWXkNXkXkWXk0,1,.,14Nk 其中:其中:552()()(2)XkDFT xlDFT xl662()()(21)XkDFT xlDFT xl0,1,.,/41lN这样逐级分解,直到这样逐级分解,直到2点点DFT11N=2xk=x0,x1 1 0002xWxX 1 0 1 12xWxX0 x 1 x0X-102W 1 X 1 002xWx2022-8-1212x0 x2x1x3X10X11X20X212点DFT2点D

5、FT111104W14W02W02WX 0X 1X 2X 31,0,241mmXWmXmXm1,0,2241mmXWmXmXm2022-8-12132022-8-12144点DFT4点DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7111108W18W28W38W3,2,1,0,4281mmXWmXmXm3,2,1,0,281mmXWmXmXm2022-8-12154点DFT4点DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6

6、X 7111108W18W28W38W8点基2时间抽取FFT算法流图2022-8-1216第一级第一级第二级第二级第三级第三级2022-8-12171.计算速度 当N=2L时,共有L级蝶形,每级N/2个蝶形,每个蝶形有1次复数乘法2次复数加法。2log22FNNmLN复数乘法复数乘法:2logFaNLNN复数加法复数加法:222()2()loglog2FFmDFTNNNmFFTNN比较比较DFT 2022-8-12182022-8-1219复乘次数NN 2NN2log22022-8-12例.如果一台通用计算机的速度为平均每次复乘 ,每次复加 ,用它来计算512点的 ,问直接计算需要多少时间,用

7、 运算需要多少时间。5 s0.5 s DFT x nFFT解:(1)直接利用 计算:复乘次数为 ,复加次数为 。DFT2N1N N 复乘所需时间 626215 105 105121.31072TNs 复加所需时间 6260.5 1010.5 10512512 10.130816TNNs所以直接利用DFT 计算所需时间:121.441536TTTs2022-8-1220复乘所需时间 612625 10log25125 10log 5120.011522NTNs 622620.5 10log0.5 10512log 5120.002304TNNs复加所需时间 所以用 FFT 计算所需时间 120.

8、013824TTTs(2)利用 计算:复乘次数为 ,复加次数为 。FFT2log2NN2logNN2022-8-1221222.倒序排列n0n1n200011011001101倒位序倒位序 自然序自然序0000000010041001010220101106301100114100101551010113611011177111222 1 02()nn nn0 122()nn nn2 102()()x nnn n n23倒序倒序k0k1k2xk2 k1k0 x000 x100 x0100101112 xk k0 xk2 k101x110 x001x101x011x111010101012022-8-1224 3.同址运算 在同一级蝶形运算中,两信号只参与一次运算。4.蝶距规律240NW142NNW02NW12NNW三、按时间抽取FFT算法的其它形式252022-8-12262022-8-12272022-8-12282022-8-12

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 办公、行业 > 各类PPT课件(模板)
版权提示 | 免责声明

1,本文(按时间抽取的FFT算法合集课件.ppt)为本站会员(三亚风情)主动上传,163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。
2,用户下载本文档,所消耗的文币(积分)将全额增加到上传者的账号。
3, 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(发送邮件至3464097650@qq.com或直接QQ联系客服),我们立即给予删除!


侵权处理QQ:3464097650--上传资料QQ:3464097650

【声明】本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是网络空间服务平台,本站所有原创文档下载所得归上传人所有,如您发现上传作品侵犯了您的版权,请立刻联系我们并提供证据,我们将在3个工作日内予以改正。


163文库-Www.163Wenku.Com |网站地图|