快速Fourier变换FF.ppt_第1页
快速Fourier变换FF.ppt_第2页
快速Fourier变换FF.ppt_第3页
快速Fourier变换FF.ppt_第4页
快速Fourier变换FF.ppt_第5页
已阅读5页，还剩22页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

4.2 快速 Fourier 变换(FFT),一、引言,FFT 不 是一种 新的 Fourier 变 换，而 是 有限离散 Fourier,变换(DFT)的一种快速算法。,事 实 上，在 “任何” 工 程领 域，人们都在不断地 追 求更高,的计算效率。,以及石油勘探等许多领域，由于其大规模的计算和实时性,的要求，使得计算效率问题更为突出。,提高计算效率的途径有两条。,快速算法；,的巨型机以及超级计算机。,特别是在军事、气象、航空航天、生物医学,其一是算法的改进，即设计,其二是计算机的改进，即设计制造出速度更快,两者有时是相互依赖的。,一、引言,现代快速算法的发展主要经历了三个阶段。,基于并行技术的快速算法需要并行机的支撑。,我国的天河一号名列榜首；,我国的曙光星云名列第三。,一、引言,曾几何时，我国在快速算法设计方面也值得“骄傲”！,(1) 直接计算：,乘法计算量,(2) 秦九韶算法：,乘法计算量,一、引言,曾几何时，我国在快速算法设计方面也值得“骄傲”！,二、方法与问题描述,1. 二分技术,(2) 规模减半：由规模为 N 降到规模为 N / 2 ；,(3) 同样问题： 一个或者两个同样的问题。,(1) 对半二分,(2) 奇偶二分,二、方法与问题描述,2. 两种二分方式,(规模为 N / 2 ),令,二、方法与问题描述,3. 问题描述,变为长度为 N / 2 的离散序列 的 DFT，,即,二、方法与问题描述,3. 问题描述,(2),(3),三、 DFT 的二分手续,三、 DFT 的二分手续,推导,(1),记,对应相加,三、 DFT 的二分手续,推导,(1),记,三、 DFT 的二分手续,原始问题,二分手续的结果,简单加工,令,同样问题,规模为 N / 2 的两个 DFT：,(对半二分),四、FFT 算法一 (结果要调序),1. 具体步骤,将规模为 的离散序列 对半二分，,令,(2) 对 和 再分别进行二分加工手续 ,如此反复进行，到第 步时，即得,(3) 对 调序，得到结果,二进制码,反写码,四、FFT 算法一 (结果要调序),2. 蝶形图 (以 N = 8 为例),加速比为:,四、FFT 算法一 (结果要调序),3. 效能分析,五、FFT 算法二 (结果不调序),蝶形图 (以 N = 8 为例),六、关于编程的几点说明,1. 关于变量类型,输入的序列直接为复数序列，应注意采用复数运算。,2. 关于序列长度不是 2 的幂,将输入的序列直接用零扩充，使其长度变为 2 的幂。,3. 关于旋转因子的计算,应预先计算好所有的旋转因子，可以避免重复计算。,由于 因此只需预先计算好下列旋转因子:,附：超级计算机(部分),附：超级计算机(部分),附：超级计算机(部分),附：超级计算机(部分),附：超级计算机
人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论