快速Fourier变换FFT.ppt

§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. 关于旋转因子的计算,应预先计算好所有的旋转因子，可以避免重复计算。,由于 因此只需预先计算好下列旋转因子:,附：超级计算机(部分),附：超级计算机(部分),附：超级计算机(部分),附：超级计算机(部分),附：超级计算机(部分),附：超级计算机(部分),附：超级计算机(部分),附：非负整数的二进制反写码,在§8.1 节中还会有较详细的介绍。,