




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、FFT算法分类:时间抽选法DIT: Decimation-In-Time频率抽选法DIF: Decimation-In-Frequency7-2 按时间抽取的FFT算法7-2 按时间抽取的FFT算法一、按时间抽取的算法原理二、按时间抽取的算法特点三、按时间抽取FFT算法的其他形式22022/9/18一、按时间抽取的算法原理设序列点数 N = 2L,L 为整数。若不满足,则补零N为2的整数幂的FFT算法称基-2FFT算法。将序列x(n)按n的奇偶分成两组:32022/9/184则x(n)的DFT:2022/9/185再利用周期性求X(k)的后半部分2022/9/186一个“蝶形运算”包含1次乘法
2、,2次加法2022/9/1872022/9/18复数乘法复数加法一个N / 2点DFT(N / 2)2N / 2 (N / 2 1)两个N / 2点DFTN 2 / 2N (N / 2 1)一个蝶形12N / 2个蝶形N / 2N总计8分解后的运算量:运算量减少了近一半2022/9/18N / 2仍为偶数,进一步分解:N / 2 N / 492022/9/1810同理:其中:这样逐级分解,直到2点DFT基2时间抽取FFT算法流图11N=2xk=x0, x12022/9/184点基2时间抽取FFT算法流图12x0 x2x1x3X10X11X20X212点DFT2点DFT-1-1-1-1X 0X
3、1X 2X 32022/9/18132022/9/184点基2时间抽取FFT算法流图8点基2时间抽取FFT算法流图144点DFT4点DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7-1-1-1-12022/9/18154点DFT4点DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7-1-1-1-18点基2时间抽取FFT算法流图2022/9/18基2时间抽取FFT算法16第一级第二级第三级2022/9/18二、按时间抽取的算
4、法特点171.计算速度 当N = 2L时,共有L级蝶形,每级N / 2个蝶形,每个蝶形有1次复数乘法2次复数加法。复数乘法:复数加法:比较DFT 2022/9/18182022/9/18算法的计算复杂度19复乘次数NN 22022/9/18例 .如果一台通用计算机的速度为平均每次复乘 ,每次复加 ,用它来计算512点的 ,问直接计算需要多少时间,用 运算需要多少时间。 解:(1)直接利用 计算: 复乘次数为 ,复加次数为 。 复乘所需时间 复加所需时间 所以直接利用DFT 计算所需时间: 2022/9/1820复乘所需时间 复加所需时间 所以用 FFT 计算所需时间 (2) 利用 计算: 复乘
5、次数为 ,复加次数为 。 2022/9/18212.倒序排列n0n1n200011011001101倒位序 自然序00000000100410010102201011063011001141001015510101136110111771112223倒序k0k1k2xk2 k1k0 x000 x100 x0100101112 xkk0 xk2 k101x110 x001x101x011x111010101012022/9/18 3.同址运算 在同一级蝶形运算中,两信号只参与一次运算。 4.蝶距规律24三、按时间抽取FFT算法的其它形式252022/9/18262022/9/18272022/9
6、/18282022/9/189、静夜四无邻,荒居旧业贫。9月-229月-22Sunday, September 18, 202210、雨中黄叶树,灯下白头人。21:15:2921:15:2921:159/18/2022 9:15:29 PM11、以我独沈久,愧君相见频。9月-2221:15:2921:15Sep-2218-Sep-2212、故人江海别,几度隔山川。21:15:2921:15:2921:15Sunday, September 18, 202213、乍见翻疑梦,相悲各问年。9月-229月-2221:15:2921:15:29September 18, 202214、他乡生白发,旧国
7、见青山。18 九月 20229:15:29 下午21:15:299月-2215、比不了得就不比,得不到的就不要。九月 229:15 下午9月-2221:15September 18, 202216、行动出成果,工作出财富。2022/9/18 21:15:2921:15:2918 September 202217、做前,能够环视四周;做时,你只能或者最好沿着以脚为起点的射线向前。9:15:29 下午9:15 下午21:15:299月-229、没有失败,只有暂时停止成功!。9月-229月-22Sunday, September 18, 202210、很多事情努力了未必有结果,但是不努力却什么改变也
8、没有。21:15:2921:15:2921:159/18/2022 9:15:29 PM11、成功就是日复一日那一点点小小努力的积累。9月-2221:15:2921:15Sep-2218-Sep-2212、世间成事,不求其绝对圆满,留一份不足,可得无限完美。21:15:2921:15:2921:15Sunday, September 18, 202213、不知香积寺,数里入云峰。9月-229月-2221:15:2921:15:29September 18, 202214、意志坚强的人能把世界放在手中像泥块一样任意揉捏。18 九月 20229:15:29 下午21:15:299月-2215、楚塞
9、三湘接,荆门九派通。九月 229:15 下午9月-2221:15September 18, 202216、少年十五二十时,步行夺得胡马骑。2022/9/18 21:15:2921:15:2918 September 202217、空山新雨后,天气晚来秋。9:15:29 下午9:15 下午21:15:299月-229、杨柳散和风,青山澹吾虑。9月-229月-22Sunday, September 18, 202210、阅读一切好书如同和过去最杰出的人谈话。21:15:2921:15:2921:159/18/2022 9:15:29 PM11、越是没有本领的就越加自命不凡。9月-2221:15:2
10、921:15Sep-2218-Sep-2212、越是无能的人,越喜欢挑剔别人的错儿。21:15:2921:15:2921:15Sunday, September 18, 202213、知人者智,自知者明。胜人者有力,自胜者强。9月-229月-2221:15:2921:15:29September 18, 202214、意志坚强的人能把世界放在手中像泥块一样任意揉捏。18 九月 20229:15:29 下午21:15:299月-2215、最具挑战性的挑战莫过于提升自我。九月 229:15 下午9月-2221:15September 18, 202216、业余生活要有意义,不要越轨。2022/9/18 21:15:2921:15:2918 September 202217、一个人即使已登上顶峰,也仍要自强不息。9:15:29 下午9:15 下午21:15:299月-22MOMODA POWERPOINTLo
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 公司校车安全管理制度
- 公司组织夜校管理制度
- 环卫工人个人工作总结20篇
- 广东省深圳市2025届高三下册2月标准学术能力诊断性测试数学试卷附解析
- 2025年中考语文(长沙用)课件:主题15 探寻时间的印记系列活动
- 2025届湖北省襄阳市襄城区中考适应性考试数学试卷
- 酒店业大数据分析框架构建-洞察阐释
- 2024年平顶山汝州市万基高级中学招聘教师真题
- 2024年黄冈市医疗卫生机构专项招聘中医药专业技术人员真题
- 社区社区服务创新研究管理基础知识点归纳
- 国开2025年《资源与运营管理》形考任务1-4答案
- 学习解读《水利水电建设工程验收规程》SLT223-2025课件
- 【MOOC】《电工技术》(北京科技大学)中国大学MOOC慕课答案
- 上海市2023-2024学年八年级下学期期末数学练习卷(解析版)
- 应急第一响应人理论考试试卷(含答案)
- 基于微信小程序的连连看小游戏的设计与实现
- 国际汽车贸易检验、检疫、索赔、仲裁与不可抗力
- (完整版)详细化学物质及其CAS注册号清单
- 智障儿童的家庭教育(课堂PPT)
- 《电路分析基础》试题及答案
- 日本文学概论1
评论
0/150
提交评论