-按时间抽取的FFT算法.pptx
FFTFFT算法分类算法分类:时间抽选法时间抽选法DIT:Decimation-In-Time频率抽选法频率抽选法DIF:Decimation-In-Frequency7-2 7-2 按时间抽取的按时间抽取的FFT算法算法7-2 按按时间抽取的FFT算法一、按时间抽取的算法原理二、按时间抽取的算法特点三、按时间抽取FFT算法的其他形式22023/12/4一、按时间抽取的算法原理设序列点数 N=2L，L 为整数。若不满足，则补零N为2的整数幂的FFT算法称基-2FFT算法。将序列x(n)按n的奇偶分成两组：32023/12/44则则x(n)的的DFT:2023/12/45再利用周期性求再利用周期性求X(k)的后半部分的后半部分2023/12/46一个一个“蝶形运算蝶形运算”包含包含1次乘法，次乘法，2次加法次加法2023/12/472023/12/4复数乘法复数乘法复数加法复数加法一个一个N/2点点DFT(N/2)2N/2(N/2 1)两个两个N/2点点DFTN 2/2N(N/2 1)一个蝶形一个蝶形12N/2个蝶形个蝶形N/2N总计总计8分解后的运算量：分解后的运算量：运算量减少了近一半运算量减少了近一半2023/12/4N/2仍为偶数，进一步分解：N/2 N/492023/12/41010同理同理：其中：其中：这样逐级分解，直到这样逐级分解，直到2点点DFT基2时间抽取FFT算法流图11N=2xk=x0,x12023/12/44点基2时间抽取FFT算法流图12x0 x2x1x3X10X11X20X212点DFT2点DFT-1-1-1-1X 0X 1X 2X 32023/12/4132023/12/44点基2时间抽取FFT算法流图8点基2时间抽取FFT算法流图144点DFT4点DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7-1-1-1-12023/12/4154点DFT4点DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7-1-1-1-18点基2时间抽取FFT算法流图2023/12/4基基2时间抽取时间抽取FFT算法算法16第一级第一级第二级第二级第三级第三级2023/12/4二、按时间抽取的算法特点171.计算速度 当N=2L时，共有L级蝶形，每级N/2个蝶形，每个蝶形有1次复数乘法2次复数加法。复数乘法复数乘法：复数加法复数加法：比较比较DFT 2023/12/4182023/12/4算法的计算复杂度算法的计算复杂度19复乘次数NN 22023/12/4例.如果一台通用计算机的速度为平均每次复乘 ，每次复加 ，用它来计算512点的 ，问直接计算需要多少时间，用 运算需要多少时间。解：(1)直接利用 计算：复乘次数为 ，复加次数为 。复乘所需时间 复加所需时间 所以直接利用DFT 计算所需时间：2023/12/420复乘所需时间 复加所需时间 所以用 FFT 计算所需时间(2)利用 计算：复乘次数为 ，复加次数为 。2023/12/421222.倒序排列n0n1n200011011001101倒位序倒位序 自然序自然序00000000100410010102201011063011001141001015510101136110111771112223倒序倒序k0k1k2xk2 k1k0 x000 x100 x0100101112 xk k0 xk2 k101x110 x001x101x011x111010101012023/12/424 3.同址运算 在同一级蝶形运算中，两信号只参与一次运算。4.蝶距规律24三、按时间抽取FFT算法的其它形式252023/12/4262023/12/4272023/12/4282023/12/49、静夜四无邻，荒居旧业贫。12月-2312月-23Monday,December 4,202310、雨中黄叶树，灯下白头人。21:18:1521:18:1521:1812/4/2023 9:18:15 PM11、以我独沈久，愧君相见频。12月-2321:18:1521:18Dec-2304-Dec-2312、故人江海别，几度隔山川。21:18:1521:18:1521:18Monday,December 4,202313、乍见翻疑梦，相悲各问年。12月-2312月-2321:18:1521:18:16December 4,202314、他乡生白发，旧国见青山。04 十二月 20239:18:16 下午21:18:1612月-2315、比不了得就不比，得不到的就不要。十二月 239:18 下午12月-2321:18December 4,202316、行动出成果，工作出财富。2023/12/4 21:18:1621:18:1604 December 202317、做前，能够环视四周；做时，你只能或者最好沿着以脚为起点的射线向前。9:18:16 下午9:18 下午21:18:1612月-239、没有失败，只有暂时停止成功！。12月-2312月-23Monday,December 4,202310、很多事情努力了未必有结果，但是不努力却什么改变也没有。21:18:1621:18:1621:1812/4/2023 9:18:16 PM11、成功就是日复一日那一点点小小努力的积累。12月-2321:18:1621:18Dec-2304-Dec-2312、世间成事，不求其绝对圆满，留一份不足，可得无限完美。21:18:1621:18:1621:18Monday,December 4,202313、不知香积寺，数里入云峰。12月-2312月-2321:18:1621:18:16December 4,202314、意志坚强的人能把世界放在手中像泥块一样任意揉捏。04 十二月 20239:18:16 下午21:18:1612月-2315、楚塞三湘接，荆门九派通。十二月 239:18 下午12月-2321:18December 4,202316、少年十五二十时，步行夺得胡马骑。2023/12/4 21:18:1621:18:1604 December 202317、空山新雨后，天气晚来秋。9:18:16 下午9:18 下午21:18:1612月-239、杨柳散和风，青山澹吾虑。12月-2312月-23Monday,December 4,202310、阅读一切好书如同和过去最杰出的人谈话。21:18:1621:18:1621:1812/4/2023 9:18:16 PM11、越是没有本领的就越加自命不凡。12月-2321:18:1621:18Dec-2304-Dec-2312、越是无能的人，越喜欢挑剔别人的错儿。21:18:1621:18:1621:18Monday,December 4,202313、知人者智，自知者明。胜人者有力，自胜者强。12月-2312月-2321:18:1621:18:16December 4,202314、意志坚强的人能把世界放在手中像泥块一样任意揉捏。04 十二月 20239:18:16 下午21:18:1612月-2315、最具挑战性的挑战莫过于提升自我。十二月 239:18 下午12月-2321:18December 4,202316、业余生活要有意义，不要越轨。2023/12/4 21:18:1621:18:1604 December 202317、一个人即使已登上顶峰，也仍要自强不息。9:18:16 下午9:18 下午21:18:1612月-23MOMODA POWERPOINTLorem ipsum dolor sit,eleifend nulla ac,fringilla purus.Nulla iaculis tempor felis amet,consectetur adipiscing elit.Fusce id urna blanditut cursus.感感 谢谢 您您 的的 下下 载载 观观 看看专家告诉
