《物理大地测量学》课件-41_积分卷积表达式的快速计算.pptVIP

卷积与Fourier变换有着密切的关系。利用一点性质，即两函数的Fourier变换的乘积等于它们卷积后的Fourier变换，能使Fourier分析中许多问题的处理得到简化。 卷积定理：函数卷积的Fourier变换是函数Fourier变换的乘积。即，一个域中的卷积相当于另一个域中的乘积，例如时域中的卷积就对应于频域中的乘积。 卷积 这一定理对Laplace变换、双边Laplace变换、Z变换、Mellin变换和Hartley变换等各种Fourier变换的变体同样成立。 3 积分卷积表达式的快速计算 卷积定义 3 积分卷积表达式的快速计算 Stokes公式 3 积分卷积表达式的快速计算 下面以Stokes公式为例，讨论如何利用Fourier变换。 二维球面公式 3 积分卷积表达式的快速计算 球面积分公式 卷积形式 FFT计算式 二维Fourier正变换 二维Fourier逆变换 二维平面公式 3 积分卷积表达式的快速计算 FFT计算式 平面积分公式 卷积形式 二维严密的平面公式 3 积分卷积表达式的快速计算 卷积形式 FFT计算式 平面积分公式 3 积分卷积表达式的快速计算 离散傅里叶变换(DFT)缺点：直接计算DFT的计算量与变换区间长度N的平方成正比，当N较大时，计算量太大，直接用DFT算法进行谱分析和信号的实时处理是不切实际的。 快速傅里叶变换 (FFT) 解决 快速Fourier变换(Fast Fourier Transform，FFT)，是离散Fourier变换的快速算法，也可用于计算离散傅里叶变换的逆变换。 FFT 3 积分卷积表达式的快速计算 Cooley-Tukey FFT是所有FFT算法中最为通用的。 1965年，IBM的T. J. Watson研究中心的James Cooley以及普林斯顿大学和ATT贝尔实验室的John Tukey发表《一个复数Fourier级数之机械计算算法》论文，首次提出了DFT运算的一种快速算法。 此后科学界创造出了各种各样的DFT快速算法，逐渐发展完善形成了一整套行之有效的算法设计思想和方法。这就是快速Fourier变换，简称FFT。 基本思想是利用基函数WNk的周期性和对称性，改变计算次序与求和次序，利用递推步骤以减少运算量。 FFT 3 积分卷积表达式的快速计算 James Cooley 生于1926年，美国数学家，哥伦比亚大学数学博士，以他所创造的快速Fourier变换(FFT)而著名。在IBM研究中心中主要从事数字信号处理的研究，直到1992年退休。同时他还是IEEE的数字信号处理委员会的成员。1980年获ASSP的优秀服务奖，1984年获ASSP协会奖以及IEEE的百年奖章。 FFT的数学意义不光在于使大家明白了Fourier变换计算起来是多么容易，而且使得数字信号处理技术取得了突破性的进展，对于现在的网络通信，图形图像处理等等领域的发展与前进奠定了基础。 FFT Fourier变换的意义在于将电能变为了工业的命脉，而FFT的意义更是在于它推动了整个社会信息化的进程。 3 积分卷积表达式的快速计算 John Tukey(1915.6.16-2000.7.26)，美国统计学家，信息设计领域的先驱人物，以发展了FFT算子和盒形图而闻名。生于麻省新贝德福德，1936和1937年分别获得布朗大学的学士和硕士学位。之后获得数学博士学位，工作于普林斯顿大学。二战期间在消防控制研究室工作。战后回到普林斯顿，为学校和ATT工作。他还服务于美国统计协会。创造了软件(software)、比特(bit)这两个词汇。 1973年获得美国国家科学奖，1982年由于对随机过程的频谱分析和FFT算子的贡献而获得IEEE荣誉奖章。此外他还为统计学在物理学、工程学和社会科学方面的应用做出突出贡献。1985年退休。 FFT John Tukey 3 积分卷积表达式的快速计算 DFT计算复杂度 DFT的计算复杂度： 复数加法N(N-1)，复数乘法N2 如何提高DFT的运算效率? 1. 将长序列DFT分解为短序列的DFT 2. 利用旋转因子 的周期性、对称性、可约性。 解决 思路 旋转因子（翅权） 3 积分卷积表达式的快速计算 旋转因子的性质 周期性 对称性 可约性 3 积分卷积表达式的快速计算 将时域序列逐次分解为一组子序列，利用旋转因子的特性，由子序列的DFT来实现整个序列的DFT。 提高DFT运算效率的方法 频域抽取法FFT(Decimation In Frequency FFT, DIF―FFT) 时域抽取法FFT(Decimation In Time FFT, DIT-FFT) 3 积分卷积表达式的快速计算 DIF－FFT算法与DFT运算比较 N点DFT的一次时域抽取分解图(N=8) 蝶形运算