快速Fourier变换FFT.pptVIP

* 第四章 离散序列 §4.2 快速 Fourier 变换(FFT) §4.2 快速 Fourier 变换(FFT) 一、引言 二、方法与问题描述 三、DFT 的二分手续 四、FFT 算法一 五、FFT 算法二 六、关于编程的几点说明 一、引言 FFT 不 是一种 新的 Fourier 变 换，而 是 有限离散 Fourier 变换(DFT)的一种快速算法。 事 实 上，在 “任何” 工 程领 域，人们都在不断地 追 求更高 的计算效率。 以及石油勘探等许多领域，由于其大规模的计算和实时性 的要求，使得计算效率问题更为突出。 提高计算效率的途径有两条。 快速算法； 的巨型机以及超级计算机。 特别是在军事、气象、航空航天、生物医学 其一是算法的改进，即设计 其二是计算机的改进，即设计制造出速度更快 两者有时是相互依赖的。 一、引言 现代快速算法的发展主要经历了三个阶段。 50 年代 外推加速技术(Richardson外推法)； 二分技术(FFT, 1965 年, Cooley, Tukey)； 60 年代 70 年代 并行技术； 基于并行技术的快速算法需要并行机的支撑。 二 十 世 纪 我国第一台巨型机 银河 1(向量机)诞生； 1983 年 — - 我国的天河一号名列榜首； 2010 年 国际 TOP500 组织公布计算机第 36 版排行榜： 我国的曙光星云名列第三。 ( 超级计算机) 一、引言 曾几何时，我国在快速算法设计方面也值得“骄傲”！ 引例1 关于多项式的计算 (1) 直接计算： 乘法计算量 (2) 秦九韶算法： 乘法计算量 编程 秦九韶 (1202～1261) 一、引言 曾几何时，我国在快速算法设计方面也值得“骄傲”！ 逼近术 96 3.14 希腊 阿基米德 (前三世纪) 缀术 24576 3.1415926 中国 祖冲之 (五世纪) 组合术 割圆术 3072 3.1416 中国 刘 徽 (三世纪) 6 径一周三 中国 周髀算经 (前二世纪) 引例2 关于圆周率 的计算 古 代 上 古 方法 正多边形 国家 年代 16位 阿拉伯 阿拉 卡希 (十五世纪) . 刘 徽 (公元250年左右) 祖冲之 (429 ～ 500) 二、方法与问题描述 1. 二分技术 思想 将一个问题经过简单加工变成规模减半的同样问题。 关键 (1) 简单加工：相对于原问题而言，加工是简单的； (2) 规模减半：由规模为 N 降到规模为 N / 2 ； (3) 同样问题： 一个或者两个同样的问题。 前提 当规模为 1 时，问题的解很容易得到。 第 步就得到问题的解。 由此，当问题的规模为 (即 2 的幂)时， (1) 对半二分 (2) 奇偶二分 二、方法与问题描述 2. 两种二分方式 例如 (规模为 N ) (规模为 N / 2 ) 令 (奇偶二分，“简单”加工) (原问题本身太简单) 二、方法与问题描述 3. 问题描述 问题 有限离散 Fourier 正变换(DFT ): 其中， (即 2 的幂)。 目标 对长度为 N 的离散序列 进行简单加工，将上述问题 变为长度为 N / 2 的离散序列 的 DFT， 即 二、方法与问题描述 3. 问题描述 注： 几个要用到的结论: (1) 当规模 时，有 DFT 即 长度为 1 的离散序列 的 DFT 就是自身。 (2) 即 即 (3) 三、 DFT 的二分手续 推导 (1) 对半二分 三、 DFT 的二分手续 推导 (1) (2) 当 k 为偶数，即 时， 记 则有 对半二分， 对应相加 三、 DFT 的二分手续 推导 (1) 当 k 为奇数，即