快速Fourier变换FFT

27,第四章 离散序列,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),秦九韶算法,：,乘法计算量,编程,秦九韶,(12021261),一、,引言,曾几何时，我国在快速算法设计方面也值得“骄傲”！,逼近术,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,为奇数，即 时，,(3),记,则有,三、 DFT 的二分手续,原始问题,二分手续的结果,规模为,N,的,DFT：,简单加工,令,同样问题,规模为,N,/,2,的两个,DFT：,(对半二分),奇,偶,二,分,四、,FFT 算法一,(结果,要,调序),1. 具体步骤,算法,(1),二分加工手续,：,将规模为,的离散序列 对半二分，,令,(2) 对 和 再分别进行,二分加工手续,如此反复进行，到第 步时，即得,(3) 对 调序，得到结果,二进制码,(反写码),反写码,四、,FFT 算法一,(结果,要,调序),2.,蝶形图,(,以,N,= 8 为例,),0,1,2,4,3,5,6,7,规 则,直接计算：,次乘法；,快速算法：,次乘法。,加速比,为:,(倍),6,5,4,3,64,32,16,8,21.33,12.80,8.00,5.33,(倍),10,9,8,7,1024,512,256,128,204.80,113.78,64.00,36.57,(倍),四、,FFT 算法一,(结果,要,调序),3.,效能分析,加速比,(乘法),五、,FFT 算法二,(结果,不,调序),蝶形图,(,以,N,= 8 为例,),0,1,2,4,3,5,6,7,规 则,六、关于编程的几点说明,1. 关于变量类型,输入的序列直接为复数序列，应注意采用复数运算。,2. 关于序列长度不是 2 的幂,将输入的序列直接用零扩充，使其长度变为,2,的幂。,3. 关于旋转因子的计算,应预先计算好所有的旋转因子，可以避免重复计算。,由于 因此只需预先计算好下列旋转因子,:,(,FFTW, Matlab 不需扩充,),休息一下,附：,超级计算机(部分),39,亿次,Cray,2,1985,年,8000,万次,Cray,1,1976,年,第,36,届世界第一,4700,万亿次,2566,万亿次,天河,1,(2),2010,年,1206,万亿次,563,万亿次,天河,1,2009,年,银河,5,2007,年,银河,4,1999,年,130,亿次,银河,3,1997,年,国家气象局,西安卫星测控站,10,亿次,银河,2,1992,年,石油部物探局,工程物理研究所,1,亿次,银河,1,1983,年,其它,峰值 /s,Linpack /s,名称,年代,附：,超级计算机(部分),华中科技大学,数学与统计学院,2886,亿次,1618,亿次,深腾,1800,2004,年,106,万亿次,深腾,7000,2009,年,4,万亿次,深腾,6800,2003,年,第,35,届世界第二,第,36,届世界第三,3000,万亿次,1271,万亿次,曙光,星云,2010,年,233,万亿次,175,万亿次,曙光,5000,2008,年,100万,亿次,曙光,4000,2003,年,3000,亿次,曙光,3000,2000,年,1000,亿次,曙光,2000,1999,年,25,亿次,10,亿次,曙光,1000,1995,年,其它,峰值 /s,Linpack /s,名称,年代,Cray,-,2,附：,超级计算机(部分),银河,-,1,附：,超级计算机(部分),银河,-,2,附：,超级计算机(部分),天河一号,附：,超级计算机(部分),曙光,5000,附：,超级计算机(部分),(,返回,),7,6,5,4,3,2,1,0,111,110,101,100,011,010,001,000,111,011,101,001,110,010,100,000,7,3,5,1,6,2,4,0,整数 的反写码为:,当 时，,例如,(,返回,),附：,非负整数的二进制反写码,其中，,k,的十进制，,k,的二进制，,k,的二进制反写码，,k,的二进制反写码,所对应的十进制。,在,8.1,节中还会有较详细的介绍。,