快速Fourier变换FFT.ppt

《快速Fourier变换FFT.ppt》由会员分享，可在线阅读，更多相关《快速Fourier变换FFT.ppt（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1第四章 离散序列 4.2 快速 Fourier 变换(FFT)快速Fourier变换FFT Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望2第四章 离散序列 4.2 快速 Fourier 变换(FFT)一、一、引言引言 FFT 不不 是一种是一种 新的新的 Fourier 变变 换，而换，而 是是 有限离散有限离散 Fourier 变换变换(DFT)的一种快速算法。的一种快速算法。事事 实实 上，在上，在“任何任何”工工 程领程领 域，人们都在不断地域，人们都在

2、不断地 追追 求更高求更高 的计算效率。的计算效率。以及石油勘探等许多领域，由于其大规模的计算和实时性以及石油勘探等许多领域，由于其大规模的计算和实时性 的要求，使得计算效率问题更为突出。的要求，使得计算效率问题更为突出。提高计算效率的途径有两条。提高计算效率的途径有两条。快速算法；快速算法；的巨型机以及超级计算机。的巨型机以及超级计算机。特别是在军事、气象、航空航天、生物医学特别是在军事、气象、航空航天、生物医学 其一是算法的改进，即设计其一是算法的改进，即设计 其二是计算机的改进，即设计制造出速度更快其二是计算机的改进，即设计制造出速度更快 两者有时是相互依赖的。两者有时是相互依赖的。3第

3、四章 离散序列 4.2 快速 Fourier 变换(FFT)一、一、引言引言 现代快速算法的发展主要经历了三个阶段。现代快速算法的发展主要经历了三个阶段。50 年代年代 外推加速技术外推加速技术(Richardson外推法外推法)；二分技术二分技术(FFT,1965 年年,Cooley,Tukey)；60 年代年代 70 年代年代 并行技术；并行技术；基于并行技术的快速算法需要并行机的支撑。基于并行技术的快速算法需要并行机的支撑。二二 十十 世世 纪纪 我国第一台巨型机我国第一台巨型机 银河银河 1(向量机向量机)诞生；诞生；1983 年年 -我国的我国的天河一号天河一号名列榜首；名列榜首；2

4、010 年年 国际国际 TOP500 组织组织公布计算机第公布计算机第 36 版排行榜：版排行榜：我国的我国的曙光曙光星云星云名列第三。名列第三。(超级计算机超级计算机)4第四章 离散序列 4.2 快速 Fourier 变换(FFT)一、一、引言引言 曾几何时，我国在快速算法设计方面也值得曾几何时，我国在快速算法设计方面也值得“骄傲骄傲”！引例引例1 关于多项式的计算关于多项式的计算 (1)直接计算：直接计算：乘法计算量乘法计算量 (2)秦九韶算法：秦九韶算法：乘法计算量乘法计算量 编程编程 秦九韶 (12021261)5第四章 离散序列 4.2 快速 Fourier 变换(FFT)一、一、引

5、言引言 曾几何时，我国在快速算法设计方面也值得曾几何时，我国在快速算法设计方面也值得“骄傲骄傲”！逼近术逼近术963.14希腊希腊阿基米德阿基米德(前三世纪前三世纪)缀术缀术245763.1415926中国中国祖冲之祖冲之(五世纪五世纪)组合术组合术割圆术割圆术30723.1416中国中国刘刘 徽徽(三世纪三世纪)6径一周三径一周三中国中国周髀算经周髀算经(前二世纪前二世纪)引例引例2 关于圆周率关于圆周率 的计算的计算 古古代代上上古古方法方法正多边形正多边形国家国家年代年代16位位阿拉伯阿拉伯阿拉阿拉 卡希卡希(十五世纪十五世纪).刘 徽 (公元公元250年左右年左右)祖冲之 (429 5

6、00)6第四章 离散序列 4.2 快速 Fourier 变换(FFT)二二、方法与方法与问题描述问题描述 1.二分技术二分技术 思想思想 将一个问题经过简单加工变成规模减半的同样问题。将一个问题经过简单加工变成规模减半的同样问题。关键关键 (1)简单加工：相对于原问题而言，加工是简单的；简单加工：相对于原问题而言，加工是简单的；(2)规模减半：由规模为规模减半：由规模为 N 降到规模为降到规模为 N/2；(3)同样问题：同样问题：一个或者两个同样的问题。一个或者两个同样的问题。前提前提 当规模为当规模为 1 时，问题的解很容易得到。时，问题的解很容易得到。第第 步就得到问题的解。步就得到问题的

7、解。由此，当问题的规模为由此，当问题的规模为 (即即 2 的幂的幂)时，时，7第四章 离散序列 4.2 快速 Fourier 变换(FFT)(1)对半二分对半二分 (2)奇偶二分奇偶二分 二二、方法与方法与问题描述问题描述 2.两种二分方式两种二分方式 例如例如 (规模为规模为 N)(规模为规模为 N/2)令令 (奇偶二分，奇偶二分，“简单简单”加工加工)(原问题本身太简单原问题本身太简单)8第四章 离散序列 4.2 快速 Fourier 变换(FFT)二二、方法与方法与问题描述问题描述 3.问题描述问题描述 问题问题 有限离散有限离散 Fourier 正变换正变换(DFT):):其中，其中，

8、(即即 2 的幂的幂)。目标目标 对长度为对长度为 N 的离散序列的离散序列 进行进行简单加工简单加工，将上述问题，将上述问题 变为长度为变为长度为 N/2 的离散序列的离散序列 的的 DFT，即即 9第四章 离散序列 4.2 快速 Fourier 变换(FFT)二二、方法与方法与问题描述问题描述 3.问题描述问题描述 注：注：几个要用到的结论几个要用到的结论:(1)当规模当规模 时，有时，有 DFT 即即 长度为长度为 1 的离散序列的离散序列 的的 DFT 就是自身。就是自身。(2)即即 即即 (3)10第四章 离散序列 4.2 快速 Fourier 变换(FFT)三三、DFT 的二分手续

9、的二分手续 推导推导 (1)对半二分对半二分 11第四章 离散序列 4.2 快速 Fourier 变换(FFT)三三、DFT 的二分手续的二分手续 推导推导 (1)(2)当当 k 为偶数，即为偶数，即 时，时，记记 则有则有 对半二分，对半二分，对应相加对应相加 12第四章 离散序列 4.2 快速 Fourier 变换(FFT)三三、DFT 的二分手续的二分手续 推导推导 (1)当当 k 为奇数，即为奇数，即 时，时，(3)记记 则有则有 13第四章 离散序列 4.2 快速 Fourier 变换(FFT)三三、DFT 的二分手续的二分手续 原始问题原始问题 二分手续的结果二分手续的结果 规模为

10、规模为 N 的的 DFT：简单加工简单加工 令令 同样问题同样问题 规模为规模为 N/2 的两个的两个 DFT：(对半二分对半二分)奇奇 偶偶 二二 分分 14第四章 离散序列 4.2 快速 Fourier 变换(FFT)四四、FFT 算法一算法一(结果结果要要调序调序)1.具体步骤具体步骤 算法算法 (1)二分加工手续二分加工手续：将规模为将规模为 的离散序列的离散序列 对半二分，对半二分，令令 (2)对对 和和 再分别进行再分别进行二分加工手续二分加工手续,如此反复进行，到第如此反复进行，到第 步时，即得步时，即得 (3)对对 调序，得到结果调序，得到结果 二进制码二进制码 (反写码反写码

11、)反写码反写码 15第四章 离散序列 4.2 快速 Fourier 变换(FFT)四四、FFT 算法一算法一(结果结果要要调序调序)2.蝶形图蝶形图(以以 N=8 为例为例)0 1 2 4 3 5 6 7 规规 则则 16第四章 离散序列 4.2 快速 Fourier 变换(FFT)直接计算：直接计算：次乘法；次乘法；快速算法：快速算法：次乘法。次乘法。加速比加速比为为:(倍倍)6 5 4 3 6432168 21.33 12.80 8.00 5.33 (倍倍)10 9 8 7 1024512256128 204.80 113.78 64.00 36.57 (倍倍)四四、FFT 算法一算法一(

12、结果结果要要调序调序)3.效能分析效能分析 加速比加速比 (乘法乘法)17第四章 离散序列 4.2 快速 Fourier 变换(FFT)五五、FFT 算法二算法二(结果结果不不调序调序)蝶形图蝶形图(以以 N=8 为例为例)0 1 2 4 3 5 6 7 规规 则则 18第四章 离散序列 4.2 快速 Fourier 变换(FFT)六六、关于编程的几点说明关于编程的几点说明 1.关于变量类型关于变量类型 输入的序列直接为复数序列，应注意采用复数运算。输入的序列直接为复数序列，应注意采用复数运算。2.关于序列长度不是关于序列长度不是 2 的幂的幂 将输入的序列直接用零扩充，使其长度变为将输入的序

13、列直接用零扩充，使其长度变为 2 的幂。的幂。3.关于旋转因子的计算关于旋转因子的计算 应预先计算好所有的旋转因子，可以避免重复计算。应预先计算好所有的旋转因子，可以避免重复计算。由于由于 因此只需预先计算好下列旋转因子因此只需预先计算好下列旋转因子:(FFTW,Matlab 不需扩充不需扩充)19第四章 离散序列 4.2 快速 Fourier 变换(FFT)休息一下20第四章 离散序列 4.2 快速 Fourier 变换(FFT)附：附：超级计算机超级计算机(部分部分)39 亿亿次次Cray 21985 年年8000 万次万次Cray 11976 年年第第 36 届世界第一届世界第一4700

14、 万万亿亿次次2566 万万亿亿次次天河天河 1(2)2010 年年1206 万万亿亿次次563 万万亿亿次次天河天河 12009 年年银银河河 52007 年年银银河河 41999 年年130 亿亿次次银银河河 31997 年年国家气象局国家气象局西安西安卫卫星星测测控站控站10 亿亿次次银银河河 21992 年年石油部物探局石油部物探局工程物理研究所工程物理研究所1 亿亿次次银银河河 11983 年年其它其它峰值峰值/sLinpack/s名称名称年代年代21第四章 离散序列 4.2 快速 Fourier 变换(FFT)附：附：超级计算机超级计算机(部分部分)华华中科技大学中科技大学数学与数

15、学与统计统计学院学院2886 亿亿次次1618 亿亿次次深深腾腾 18002004 年年106 万万亿亿次次深深腾腾 70002009 年年4 万万亿亿次次深深腾腾 68002003 年年第第 35 届世界第二届世界第二第第 36 届世界第三届世界第三3000 万万亿亿次次1271 万万亿亿次次曙光曙光 星云星云2010 年年233 万万亿亿次次175 万万亿亿次次曙光曙光 50002008 年年100万万 亿亿次次曙光曙光 40002003 年年3000 亿亿次次曙光曙光 30002000 年年1000 亿亿次次曙光曙光 20001999 年年25 亿亿次次10 亿亿次次曙光曙光 10001

16、995 年年其它其它峰值峰值/sLinpack/s名称名称年代年代22第四章 离散序列 4.2 快速 Fourier 变换(FFT)Cray-2 附：附：超级计算机超级计算机(部分部分)23第四章 离散序列 4.2 快速 Fourier 变换(FFT)银河银河-1 附：附：超级计算机超级计算机(部分部分)24第四章 离散序列 4.2 快速 Fourier 变换(FFT)银河银河-2 附：附：超级计算机超级计算机(部分部分)25第四章 离散序列 4.2 快速 Fourier 变换(FFT)天河一号天河一号 附：附：超级计算机超级计算机(部分部分)26第四章 离散序列 4.2 快速 Fourier

17、 变换(FFT)曙光曙光 5000 附：附：超级计算机超级计算机(部分部分)(返回返回)27第四章 离散序列 4.2 快速 Fourier 变换(FFT)76543 2 1 0 111110101100011010001000 111011101001110010100000735162 4 0整数整数 的反写码为的反写码为:当当 时，时，例如例如 (返回返回)附：附：非负整数的二进制反写码非负整数的二进制反写码 其中，其中，k 的十进制，的十进制，k 的二进制，的二进制，k 的二进制反写码，的二进制反写码，k 的二进制反写码的二进制反写码 所对应的十进制。所对应的十进制。在在8.1 节中还会有较详细的介绍。节中还会有较详细的介绍。