《fft.docVIP

快速傅立叶变换 学号：0502214019 姓名：高翔 快速傅氏变换，是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。 设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的优越性. 傅里叶变换（Transformée de Fourier）是一种积分变换。因其基本思想首先由法国学者傅里叶系统地提出，所以以其名字来命名以示纪念。 应用 傅里叶变换在物理学、数论、组合数学、信号处理、概率论、统计学、密码学、声学、光学、海洋学、结构动力学等领域都有着广泛的应用（例如在信号处理中，傅里叶变换的典型用途是将信号分解成幅值分量和频率分量）。 概要介绍 傅里叶变换能将满足一定条件的某个函数表示成三角函数（正弦和/或余弦函数）或者它们的积分的线性组合。在不同的研究领域，傅里叶变换具有多种不同的变体形式，如连续傅里叶变换和离散傅里叶变换。最初傅里叶分析是作为热过程的解析分析的工具被提出的（参见：林家翘、西格尔著《自然科学中确定性问题的应用数学》，科学出版社，北京。原版书名为 C. C. Lin L. A. Segel, Mathematics Applied to Deterministic Problems in the Natural Sciences, Macmillan Inc., New York, 1974）。 傅里叶变换属于谐波分析。 傅里叶变换的逆变换容易求出,而且形式与正变换非常类似; 正弦基函数是微分运算的本征函数,从而使得线性微分方程的求解可以转化为常系数的代数方程的求解.在线性时不变的物理系统内,频率是个不变的性质,从而系统对于复杂激励的响应可以通过组合其对不同频率正弦信号的响应来获取; 卷积定理指出:傅里叶变换可以化复杂的卷积运算为简单的乘积运算,从而提供了计算卷积的一种简单手段; 离散形式的傅里叶变换可以利用数字计算机快速的算出(其算法称为快速傅里叶变换算法(FFT)). 离散傅立叶变换(DFT)是对信号作数字频谱分析及实现数字滤波的基本方法。它在频谱分析、数字通信、语音信号分析、图象处理、雷达、声纳、地震、生物医学工程等各个领域都有着日益广泛的应用。直接计算DFT，工作量相当大，当数据点数为N时，大约需要N2次乘法和N2次加法。1965年，美国的Cooley和Tukey提出了快速傅立叶变换(FFT)的算法［1］。这种算法将DFT的计算速度提高了N/log2N倍，使许多信号的处理工作能与整个系统的运行速度协调。傅立叶变换的应用也就从某些数据的事后处理及系统的模拟研究，而进入数据的实时处理。现在已经有了一些更好的算法，例如Winograd快速傅立叶变换，这些算法是利用抽象代数和初等数论等数学工具建立起来的，因而接受程度和应用范围就受到了很大的限制，工程上使用的也较少。表1列出了几种傅立叶变换算法计算量的比较［2］，新算法的优越性是显而易见的。 2小数组Winograd快速傅立叶变换算法??? 所谓小数组Winograd快速傅立叶变换算法是指针对信号长度N＝2，3，4，5，6，7，8，9，16这8种短DFT，Winograd所提出的独特算法。他应用域的理论证明了这些算法的乘法次数接近于N，而加法次数与Cooley-Tukey FFT相近。这些小数组Winograd算法之所以重要还在于所有信号长度N很大的Winograd算法，都可以由几个互素的小数组Winogr