数字信号处理期末大作业FFT的发展史、现状及典型算法班级学号：姓名：FFT的发展史、现状及典型算法傅里叶分析已有200多年的历史，目前FFT及其校正算法在工程实际中仍在广泛应用，展现了其不竭的生命力。本次作业我们论述FFT的现状，发展史以及一些算法，去详细了解、扩展这一算法，巩固所学知识。一．FFT的简介傅里叶变换是一种将信号从时域变换到频域的变换形式，然而当N很大的时候，求一个N点的DFT要完成N*N次复数乘法和N*（N-1）次复数加法，计算量非常大，所以人们开始探索一种简便的算法对于一个较大的N进行傅里叶变换。在20世纪60年代由Cooley和Tukey提出了快速傅里叶变换算法，它是快速计算DFT的一种简单高效的方法。关于何为FFT，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。举个例子，设x(n)为N项的复数序列，由DFT变换，任一X（m）的计算都需要N次复数乘法和N-1次复数加法，而一次复数乘法等于四次实数乘法和两次实数加法，一次复数加法等于两次实数加法，即使把一次复数乘法和一次复数加法定义成一次“运算”（四次实数乘法和四次实数加法），那么求出N项复数序列的X（m）,即N点DFT变换大约就需要N^2次运算。当N=1024点甚至更多的时候，需要N2=1048576次运算，在FFT中，利用WN的周期性和对称性，把一个N项序列（设N=2k,k为正整数），分为两个N/2项的子序列，每个N/2点DFT变换需要（N/2）2次运算，再用N次运算把两个N/2点的DFT变换组合成一个N点的DFT变换。这样变换以后，总的运算次数就变成N+2*（N/2)^2=N+（N^2）/2。继续上面的例子，N=1024时，总的运算次数就变成了525312次，节省了大约50%的运算量。而如果我们将这种“一分为二”的思想不断进行下去，直到分成两两一组的DFT运算单元，那么N点的DFT变换就只需要Nlog2N次的运算，N在1024点时，运算量仅有10240次，是先前的直接算法的1%，点数越多，运算量的节约就越大，这就是FFT的优越性。所以使用FFT算法，可以大大提高傅里叶变换的运算速度，运算时间缩短一到两个数量级，从而使DFT变换应用迅速普及，不仅在频谱分析，而且在线性卷积、线性相关等方面得到广泛应用。二．FFT的现实意义随着计算机技术的发展，离散傅里叶变化的出现使得傅里叶变换在工程中进入实际应用阶段。在信号处理中，DFT的计算具有举足轻重的作用，信号的相关、滤波、谱估计等都要通过DFT来实现，但必须减少它的运算量，DFT才能在工程计算中具有实用价值。所以，FFT的出现提高了它的实用价值。而FFT成为数字信号处理的关键技术，在信号处理领域扮演的角色越来越重要。高效率的快速傅立叶变换(FFT)算法是雷达信号处理、卫星通讯、生物医学和多媒体信号处理等基础和核心算法。提高FFT处理速度满足对雷达信号处理实时性的，要求在EW接收机高速数据处理方面将有广泛的应用前景。随着科学技术的不断进步，相控阵体制已广泛应用于各种星载、机载、舰载和地面雷达。对于电尺寸较大几十甚至几百个波长的相控阵天线，(如高分辨率星载，SAR天线、大型稀布阵天线等)，用公式按级数求和计算阵列天线方向图的方法效率甚低。FFT的引入将从根本上解决这一难题。平面近场测量方法是天线测量的常规手段而FFT技术加快了天线参数评估的速度。三．傅里叶变换的发展历程对于发展史，我们由记载可知，离散傅里叶变换DFT是数字信号处理最重要的基石之一，也是对信号进行分析和处理时最常用的工具之一。在200多年前法国数学家、物理学家傅里叶提出后来以他名字命名的傅里叶级数之后，用DFT这个工具来分析信号就已经为人们所知。历史上最伟大的数学家之一。欧拉是第一个使用“函数”一词来描述包含各种参数的表达式的人，例如：y=f(x)。他是把微积分应用于物理学的先驱者之一。给出了一个用实变量函数表示傅立叶级数系数的方程；用三角级数来描述离散声音在弹性媒介中传播发现某些函数可以通过余弦函数之和来表达。但在很长时间内，这种分析方法并没有引起更多的重视，最主要的原因在于这种方法运算量比较大。直到1965年，Cooley和Tukey在《计算机科学》发表著名的《机器计算傅立叶级数的一种算法》论文，FFT才开始大规模应用。...