快速Fourier变换FFT.ppt
《快速Fourier变换FFT.ppt》由会员分享,可在线阅读,更多相关《快速Fourier变换FFT.ppt(27页珍藏版)》请在三一文库上搜索。
1、4.2 快速 Fourier 变换(FFT),一、引言,FFT 不 是一种 新的 Fourier 变 换,而 是 有限离散 Fourier,变换(DFT)的一种快速算法。,事 实 上,在 “任何” 工 程领 域,人们都在不断地 追 求更高,的计算效率。,以及石油勘探等许多领域,由于其大规模的计算和实时性,的要求,使得计算效率问题更为突出。,提高计算效率的途径有两条。,快速算法;,的巨型机以及超级计算机。,特别是在军事、气象、航空航天、生物医学,其一是算法的改进,即设计,其二是计算机的改进,即设计制造出速度更快,两者有时是相互依赖的。,一、引言,现代快速算法的发展主要经历了三个阶段。,基于并行技
2、术的快速算法需要并行机的支撑。,我国的天河一号名列榜首;,我国的曙光星云名列第三。,一、引言,曾几何时,我国在快速算法设计方面也值得“骄傲”!,(1) 直接计算:,乘法计算量,(2) 秦九韶算法:,乘法计算量,一、引言,曾几何时,我国在快速算法设计方面也值得“骄傲”!,二、方法与问题描述,1. 二分技术,(2) 规模减半:由规模为 N 降到规模为 N / 2 ;,(3) 同样问题: 一个或者两个同样的问题。,(1) 对半二分,(2) 奇偶二分,二、方法与问题描述,2. 两种二分方式,(规模为 N / 2 ),令,二、方法与问题描述,3. 问题描述,变为长度为 N / 2 的离散序列 的 DFT
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 快速 Fourier 变换 FFT
链接地址:https://www.31doc.com/p-2606733.html