三角插值快速傅立叶变换-同济大学数学系.PDFVIP

三角插值快速傅立叶变换 学生姓名：邵文婷 学 号：053523 任课教师：吴雄华 专 业：应用数学 年 级：大三 学 校：同济大学 邮 编：200092 摘要 离散傅立叶变换(Discrete Fourier Transform 简称DFT)广泛应用于信号分析，光谱和 声谱分析，全息技术等各个领域。 本文先从对周期为 连续函数构造插值指数多项式着手引入了离散傅立叶变换的基 2 本概念和变换公式。然后主要研究实现由Cooley-Tukey 率先提出的快速傅立叶变换(FFT)的 两种算法：基2-时域抽取法和基2-频率域抽取法，分别对两种方法给予了matlab 程序实现， 其次介绍了改进型 FFT 算法以及提出了基为合数的快速傅立叶变换的简单原理。然后结合 matlab 提供的相关库程序，着重讨论了 DFT 与基 2-快速算法的运算量和运算效果比较。得 到结论快速傅立叶变换在保证一定运算精度的同时将离散傅立叶变换的运算量由O( N 2 ) 降到 了合理的数量O( N log N ) ，从而大大提高了运算效率。最后以典型例题给出了快速傅立叶 2 变换在计算数学和信号处理上的基本应用。 关键词： 三角插值离散傅立叶变换，基2-时域抽取FFT，基2-频率域抽取FFT,蝶形图，运算量比较 I 目 录 中文摘要 I 1 引言 1 1.1 问题的提出与研究 1 1.1.1 问题的提出和难点 1 1.1.2 问题研究的意义 1 1.2 国内外研究简介 2 1.3 本文研究的内容和贡献 2 1.3.1 研究的内容 2 1.3.2 贡献 2 2 三角插值原理 4 2.1 傅立叶级数 4 2.2 复傅立叶级数 4 2.3 复内积，伪内积 5 2.4 三角插值指数多项式 6 3 快速傅立叶变换的原理及数值算法 8 3.1 离散傅立叶变换(DFT) 8 3.1.1DFT 定义及公式 8 3.1.2DFT 运算特点 9 3.2 快速傅立叶变换(FFT)10 3.2.1 基2-时域抽取法(Decimation- In-Time,简称DIT-FFT) 10 3.2.1.1 模型与基本原理10 3.2.1.2 蝶形运算与分解流程图11 3.2.1.3 运算量分析 14 3.2.1.4 旋转因子14 3.2.2 基2-频率域抽取法(Decimation- In-Frequency,简称DIF-FFT)15 3.2.2.1 模型与基本原理15 3.2.2.2 蝶形运算与分解流程图16 3.2.3 DIT-FFT 和DIF-FFT 程序实现17 3.2.3.1 DIT-FFT 和DIF-FFT 运算规律及异同比较17 3.2.3.2 DIT-FFT 和DIF-FFT 程序设计思想18 3.2.3.3 改进的FFT 算法 23 3.2.4 混合基FFT 原理简介26 3.3 DFT 与各种FFT 算法的数值算例及数值结果比较27 II 4 典型例题32 4.1 构造三角插值多项式系数 32 4.2 频谱分析32 5 小结与展望34 5.1 小结34 5.2 展望34 致谢35 参考文献36 附录37