fft的发展、现状、典型算法.docx

数字信号处理期末大作业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变换大约就需要N2次运算。当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+（N2）/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才开始大规模应用。那个年代，有个肯尼迪总统科学咨询委员会。其中有项研究主题是，对苏联核测试进行检测，Tukey就是其中一员。美国/苏联核测试提案的批准，主要取决于不实地访问核测试设施而做出检测的方法的发展。其中一个想法是，分析离海岸的地震计情况，这种计算需要快速算法来计算DFT。其它应用是国家安全，如用声学探测远距离的核潜艇。所以在军事上，迫切需要一种快速的傅立叶变换算法，这也促进了FFT的正式提出。FFT的这种方法充分利用了DFT运算中的对称性和周期性，从而将DFT运算量从N2减少到N*log2N。当N比较小时，FFT优势并不明显。但当N大于32开始，点数越大，FFT对运算量的改善越明显。比如当N为1024时，FFT的运算效率比DFT提高了100倍。在库利和图基提出的FFT算法中，其基本原理是先将一个N点时域序列的DFT分解为N个1点序列的DFT，然后将这样计算出来的N个1点序列DFT的结果进行组合，得到最初的N点时域序列的DFT值。实际上，这种基本的思想很早就由德国伟大的数学家高斯提出过，在某种情况下，天文学计算（也是现在FFT应用的领域之一）与等距观察的有限集中的行星轨道的内插值有关。由于当时计算都是靠手工，所以产生一种快速算法的迫切需要。 而且，更少的计算量同时也代表着错误的机会更少，正确性更高。高斯发现，一个富氏级数有宽度N=N1*N2，可以分成几个部分。计算N2子样本DFT的N1长度和N1子样本DFT的N2长度。只是由于当时尚欠东风计算机还没发明。在20世纪60年代，伴随着计算机的发展和成熟，库利和图基的成果掀起了数字信号处理的革命，因而FFT发明者的桂冠才落在他们头上。之后，桑德-图基等快速算法相继出现，几经改进，很快形成了一套高效运算方法，这就是现在的快速傅立叶变换（FFT）。这种算法使DFT的运算效率提高1到2个数量级，为数字信号处理技术应用于各种信号的实时处理创造了良好的条件，大大推进了数学信号处理技术。1984年，法国的杜哈梅和霍尔曼提出的分裂基块快速算法，使运算效率进一步提高。库利和图基的FFT算法的最基本运算为蝶形运算，每个蝶形运算包括两个输入点，因而也称为基-2算法。在这之后，又有一些新的算法，进一步提高了FFT的运算效率，比如基-4算法，分裂基算法等。这些新算法对FFT运算效率的提高一般在50%以内，远远不如FFT对DFT运算的提高幅度。从这个意义上说，FFT算法是里程碑式的。可以说，正是计算机技术的发展和FFT的出现，才使得数字信号处理迎来了一个崭新的时代。除了运算效率的大幅度提高外，FFT还大大降低了DFT运算带来的累计量化误差，这点常为人们所忽略。以上为FFT的发展史，在整个发展历程中，傅里叶的发明作用尤为重要，后人的推动，改良在发展史上也起到了至关重要的作用。四FFT的现状、发展热度对于傅里叶变换的现状，我们分为国内国外两部分进行讨论：首先介绍国外现状，国外围绕快速傅立叶变换的并行计算进行了多项研究和开发。美国新墨西哥大学Vasilios Georgitsis等人设计了2-DFFT程序，可处理512*512个点的图像，其底层通信基于PVM，将2-DFFT转化成1-DFFT并行计算，完成了二维图像的变换。目前最新的研究成果是由麻省理工学院计算机科学实验室超级计算技术组开发的FFTW。FFTW是计算离散傅里叶变换DFT的快速C程序的一个完整集合，它可计算一维或多维、实数据和复数据以及任意规模的DFT。 在FFTW中，DFT的计算由执行器完成。执行器是由许多高度优化的、可组装的子代码模块组成的。FFTW有一个规划器。规划器用以根据具体机器的体系结构特点和具体的DFT宽度N。在运行时寻找一种有效的子代码块组装方式，因此使得FFTW具有很好的自适应性和很快的运行速度。FFTW还包含对共享和分布式存储系统的并行变换。 对于国内现状，在我国80年代初就开展了并行算法研究。快速傅立叶变换的并行算法主要包括基于SIMD-MC2、SIMD-BF、SIMD-CC、MIMD-DM四种体系结构上的FFT算法，它们都是基-2FFT算法，算法各有利弊，受体系结构影响较大。 SIMD-MC2上的FFT算法是按频率抽取的快速傅立叶变换在网孔结构上的具体实现。假设将n个处理器P0，P1，PN-1排成的方阵。初始序列开始时已处于阵列的各处理器中，即ak处于Pk中。算法结束时，Pk保存bk。SIMD-BF上FFT算法是在一个n=2k的蝶形网络，简记为BF。将(k+1)、2k个节点布局成(k+1)行，每行有n个节点。令(r，i)表示第r行和第i列的坐标，0，i，n-1，exp(r，i)表示在BF中坐标点(r，i)处的w的指数，它等于字长为k的整数j，即exp(r，i)=j。使得如果i的二进制表示为a1，a2，ar-1，ar，ak，则j的二进制为ar，ar-1a1，000。也就是说将i的前r位取位反，即倒序，后面其余位补零就可以得到j。因为蝶形网络第r-1行和第r行之间的连接，正好能满足直接将dr-1，i和dr-1，j传到P(r，j)和P(r，j)，所以无需考虑选路时间。算法时间除计算w、exp(r，i)的时间外，主要是算法第2步进行复数运算的时间。它等于0( )，显然优于SIMD-MC2上的FFT算法，这也说明算法和体系结构的密切关系。西安电子科技大学信息科学研究所提出了一种基于共享存储的多机系统并行计算FFT算法。中国科学院计算技术研究所利用星型互联网的递归可分解性的多样性，提出了一种基于星型互联网络的并行快速傅立叶变换算法。星图具有层次型结构，可由许多低维的子星图组成。国防科大就向量机上的FFT并行算法作了系统的研究，并就离散变换、卷积和滤波的并行算法，用多项式变换计算离散卷积以及短卷积嵌套计算长卷积的并行算法，并研究了离散卷积的并行计算下界，对一维和二维滤波给出了用变换法及递推公式计算的并行算法。可见无论在与国内还是国外，FFT算法都是研究的热点，有着广阔的发展前景。五基4FFT算法原理及介绍基4FFT算法是把长度N=4的序列一分为四，将N点DFT表示为4个N/4点DFT的线性组合。然后再把N/4点DFT一分为四，表示为四个N /16点的DFT。如此重复下去直至分解成两点DFT的运算。多基时分蝶式运算定理在形式上比基2时分碟式运算定理复杂，但在本质上是一致的。前者表明,对N=p，q的情形，若按xm(i)=x(ip+m)将原N点序列分解成p个q点的子序列，则原序列x(n)的DFT可由各子序列xm(i)的DFT的线性组合得到。基4时分FFT算法是多基算法的特例，因此从多基时分FFT的蝶式运算定理即可推导出基4时分FFT算法的蝶式运算公式。具体算法如下：设p=4,q=N/4,这时由多基时分蝶式运算定理,输入序列x(n)可以分解成如下的4个子序列:子序列均为N/4点序列，设它们的N/4点DFT为，则其中，k,s,r均为整数。将s=0,1，2,3代入上式，则：,其中，上式就是基4FFT蝶形运算公式。其具体算法和基2算法相近。将式中的序列整理为4个序列，然后继续拆分，即可得最后结果。相比于基2FFT算法，基4FFT算法运算量较小，但是相应的变换长度更少，灵活性不如基2FFT算法。六实际应用中的FFT典型算法描述及介绍（1）余弦窗插值FFT算法加窗插值FFT算法是一种异步采样方法，它是以固定不变的采样频率对信号进行采样，利用窗函数截断信号时产生的泄漏频剖来得到信号的实际频谱值。通过对信号加窗可以减小由频谱泄漏现象引起的误差，通过插值算法可以减小由栅栏效应引起的误差。用FFT计算电力系统谐波时需要将被测信号截断，这样就会产生截断效应，即产生频谱泄漏，信号的基波和高次谐波谱线向附近展宽，形成主瓣和旁瓣。泄漏的频谱主瓣可能淹没主谱附近的谐波分量，影响是短范围的。旁瓣的影响是长范围(谱间干扰)的，它对相邻的基波和高次谐波分量影响较大。当采样频率是信号基波频率的整倍数时，可以得到精确的计算结果，但是当采样频率不是信号频率的整倍数时，由于栅栏效应，只能测得泄漏的频谱，计算产生误差。加窗插值FFT算法可以计算出信号的频率偏移量，再对测得的泄漏频谱进行修正，从而得到实际信号的频谱。实际信号的频谱的计算精度取决于所加窗函数的特性，选择主瓣窄的窗函数可以减小短范围的影响；选择旁瓣峰值小、衰减速度快的窗函数，可以减小长范围的影响。一个理想的窗函数应具有主瓣宽度窄、最大旁瓣峰值小和旁瓣衰减速度快的特点。但最大旁瓣峰值小且旁瓣衰减速度快的窗函数，其主瓣较宽，因此，要寻找主瓣窄且旁瓣峰值又小的窗函数是很困难的。泄漏频谱主瓣的影响在实际应用中可以通过增加观测时间来消除，但这又影响了算法的实时性。实际上，观测的基波周期数就是相邻两频谱主谱线之间的谱线间隔数，例如加汉宁窗截断的正弦信号的频谱泄漏主瓣的宽度为4个谱线间隔，要分辨出相邻的谐波(消除主瓣的影响)，加汉宁窗插值FFT算法至少需要两个基波周期的采样点 (相邻两频谱主谱线间隔两个谱线间隔)；加Blackman-harris窗截断的正弦信号的频谱泄漏主瓣的宽度为8个谱线间隔，要分辨出相邻谐波(消除主瓣的影响)，加Blackman-harris窗插值FFT算法至少需要4个基波周期的采样点(相邻两频谱主谱线间隔4个谱线间隔)。对旁瓣峰值高且衰减快的窗函数可再适当增加观测时间(采样的基波周期数)来消除临近主瓣的峰值较高的几个旁瓣对相邻谐波的影响21，例如加汉宁窗插值FFT算法采用4个基波周期的采样点进行FFT变换还能提高计算精度。对旁瓣峰值不衰减的窗函数即使增加再多的观测时间(采样的基波周期数)也无法消除旁瓣对相邻谐波计算精度的影响。余弦窗的一般表达式5项余弦窗主瓣宽10/N，6项余弦窗主瓣宽12/N，7项余弦窗主瓣宽14/N，8项余弦窗主瓣宽16/N。5项余弦窗最大旁瓣峰值-89.69 db，6、7、8项余弦窗最大旁瓣峰值依次减小。从旁瓣衰减速度来看，7项余弦窗旁瓣衰减速度很慢，5、6、7项余弦窗旁瓣衰减依次加快，8项余弦窗旁瓣衰减速度最快，频率为0.5时旁瓣峰值下降到-220db以下。7项余弦窗旁瓣基本不衰减，故加7项余弦窗插值FFT算法计算精度通过增加观测时间不能有效提高，精度甚至低于加5、6项余弦窗插值FFT算法。根据图1中的频谱特性可以看出，8项余弦窗主瓣虽宽，但最大旁瓣峰值最小，旁瓣衰减速度最快，考虑到泄漏频谱主瓣的影响可以通过增加观测时间来消除，加8项余弦窗插值FFT算法在这4种加余弦窗插值FFT算法中具有最高的计算精度。考虑到余弦窗项数越多，加余弦窗FFT算法计算量越大。下面以单频率信号为例进行分析，设复振幅Am一般为复数，反映了初相角，实际频率fr= (l+r)*F，它在频率lF和(l+1)*F之间，l 为整数，其中频率分辨率F=1/(NTs)，Ts为采样时间间隔，r为频率偏移量，0r1时，有以下关系成立： 考虑到，当K=3时，可以得到加余弦窗DFT的通用形式为代入，可以得到Nuttall窗截断后的信号频谱为设定幅值比为由上式联立解出r值为：由于频率偏移量r的变化范围为0-1，所以幅值比的变化范围为0.75-4/3。将r代入式子中，解得修正后的复振幅：所以谐波相位也可以求得为到这步为止，已求得了信号的所需参数。插值算法的幅值比是频率偏移量r的一次多项式，r的计算容易且计算量很小，这在加4项(及以上)窗插值FFT算法中是很难找到的。另外其窗函数频谱旁瓣的衰减速率快，通过增加观测时间，能有效地提高计算精度，计算精度优于加Blackman-harris窗插值FFT算法。利用三次样条插值函数计算复振幅的修正系数，能更好地提高加4项余弦窗Nuttall(I)窗插值FFT算法的计算速度。七FFT发展展望及启示（1）快速变换算法的每一次突破都是找到一种数学工具以揭示变换的内在关系,从而推动了快速算法的发展构造各种离散正交变换最小实数乘法次数的算法途径已经给出,但尚无法证明是最佳的。如果循环卷积找到乘法和加法次数均