第四章 快速傅里叶变换(FFT)
35页1、第四 章 快速傅里叶变换( FFT)通信 1402班 肖太龙Contents从 DFT到 FFTFFT的基本概念FFT算法的实现原理FFT的物理意义 DFT与 FFT时间复杂度比较从 DFT到 FFT的缘由 依次 类 推, N/2个点的 时间 复 杂 度 为多少呢? N/4呢?从哪个方面减少运算量呢? 周期性表现为: 对称性表现为: 1965年库利和图基提出一种 DFT的快速算法,以此来解决 DFT变换的效率问题。 算法的提出的初衷主要是为了减少乘法次数,又因为旋转因子的对称性和周期性能达到这一目标,因此在理论上是可以实现的。 FFT算法就是不断地把长序列的 DFT分解为短序列的DFT的算法。最常用的是基2FFT算法。浅谈 FFT实现原理lFT算法基本上分为两大类 :l时域抽取法 FFT(DecimationInTimeFFT,简称 DIT-FFT)。l频域 抽取法 FFT(DecimationInFrequencyFFT,简称DIFFFT)。l我们主要来分析 DIF-FFT算法。A 算法理论推导B 一个简单的算例 8点 DFT一次时域抽取分解C Matlab绘制图像DIF-FFT与
2、DIT-FFT算法有什么异同 ?算法理 论 推 导 :设 序列 的 长 度 为 N,且 满 足 N=2M , M为 自然数。按 n奇偶把 分解 为 两个 N/2点的子序列则 x(n)的 DFT为 因 为所以 其中 X1(k)和 X2(k)分 别为 x1(r)和 x2(r)的 N/2点 DFT, 即由于 X1(k)和 X2(k)均以 N/2为 周期, 且所以 X(k)又可表示 为至此,一次 时 域抽取法的理 论 推 导 就完成了。从上面的两个式子中,我 们 定 义 一种新的运算符 蝶形运算符。8点 DFT一 次 时 域抽取分解运算流 图完成一次蝶形运算需要一次复数乘法和两次复数加法运算。因此在 8点 DFT一 次 时 域抽取分解中,共需要 计算两个 N/2点 DFT运算和 N/2个蝶形运算。所以按照上 图 的 计 算 DFT时 , 总 的复数乘法次数为复数加法次数 为类 似地,我 们 将 按奇偶分解成两个 N/4点子序列,其表达式分 别 如下:那么 , 又 可表示 为式中同理, 由 的 周期性 和 的 对 称性最后 得到:用同 样 的方法可以 计 算出其中8点 DFT二次 时 域抽取分解
3、运算8点 DIT-FFT运算流 图从上面的蝶形算法,当 时 ,其运算 应该 有M级 蝶形,每一 级 都由 N/2个蝶形运算构成。因此每一 级 运算都需要 N/2次复数乘法和 N次复数加法,所以 M级 蝶形运算的乘法次数 为 :加法次数:一个 简单 的算例 计 算序列 的 8点 DFT。分 别用基本的 DFT算法和 FFT算法 实现 ,体会 计 算 过 程中的 时间 复 杂 度。 当然 针对计 算机来 说 , 计 算乘法所需要的 时间远 大于加法。一般的 计 算机,差不多相差十倍左右。 用 计 算机 产 生随机的 1024个点构成序列,然后取N=1024.此 时计 算 时间 差距就会加大。 N=2048时 , 时间 差距会更大。为 了更 进 一步的体会 FFT的物理意 义 ,引入一个算例:假 设对 某信号 经过 ADC之后,得到一个序列 ,此 时 我们 不知道其具体的函数表达式。但是我 们 可以 对 其做 FFT运算。 现 在我 们 做一个 验证 : 假 设 我 们 有一个信号,它含有 2V的直流分量, 频 率 为 50Hz、相位 为 -30度、幅度 为 3V的交流信号,以及一个 频 率
《第四章 快速傅里叶变换(FFT)》由会员油条分享,可在线阅读,更多相关《第四章 快速傅里叶变换(FFT)》请在金锄头文库上搜索。
最新学校新冠肺炎疫情突发事件应急处置办法和流程
最新疫情防控期间学校用餐与食堂管理规定和师生一日流程图
最新Xx省xx区返学师生员工健康登记表
诊所简介
高中英语-第二单元-《the-United-Kingdom》课件-新必修5
新版新目标英语七年级下unit4--Don't-eat-in-class课件
新版PEP六年级英语unit6-how-do-you-feel-A-Let's-talk
安徽专版2018秋八年级英语上册Unit5Doyouwanttowatchagameshow第6课时习题课件新人教目标版
酸的和甜的教学课件.doc
Lesson-1-Where-do-we-go-from-here概要
Docker技术与实践
七年级英语下册-Unit-9-What-does-he-look-like(第3课时)(Grammar-Focus-3d)同步语法精讲精练课件-(新版
《I'm-going-to-do-the-high-jump》PPT课件3
高二英语外研版-必修5-Module-2-A-Job-Worth-Doing-Reading课件
英语片段教学-I-can-do-it
Adobe公司简介
安徽专版2018秋八年级英语上册Unit5Doyouwanttowatchagameshow第2课时习题课件新人教目标版
第二单元全课件Unit2-What-time-do-you-go-to-school-全课件
第18课-Windows的磁盘管理与安全
第12章--Windows-Server-2008路由及远程访问
2023-11-20 52页
2023-09-09 54页
2023-09-09 98页
2023-09-09 101页
2023-09-09 95页
2023-09-09 127页
2023-09-09 59页
2023-09-09 50页
2023-09-09 139页
2023-09-09 131页