资源描述：
《傅里叶和互相关算法及c程序》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、1．快速傅里叶变换（FFT）1.1叶变换简介快速傅里有限长序列可以通过离散傅里叶变换(DFT)将其频域也离散化成有限长序列.但其计算量太大,很难实时地处理问题,因此引出了快速傅里叶变换(FFT).1965年，Cooley和Tukey提出了计算离散傅里叶变换（DFT）的快速算法，将DFT的运算量减少了几个数量级。从此，对快速傅里叶变换（FFT）算法的研究便不断深入，数字信号处理这门新兴学科也随FFT的出现和发展而迅速发展。根据对序列分解与选取方法的不同而产生了FFT的多种算法，基本算法是基-2DIT和基-2D
2、IF。FFT在离散傅里叶反变换、线性卷积和线性相关等方面也有重要应用。快速傅氏变换（FFT），是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。快速傅立叶变换作为一种数学方法，已经广泛地应用在几乎所有领域的频谱分析中，而且经久不衰，因为信号处理方法没有先进和落后之分，只有经典和现代之别，在实际系统中用得最好的方法就是管用的方法。换句话说，信号
3、处理方法与应用背景和目的的贴近程度是衡量信号处理方法优劣的唯一标准。FFT是快速傅利叶变换(FastFourierTransform简称FFT)的英文缩写,它在当今科技世界中的应用相当活跃,无论是在时间序列分析领域中,还是在我国刚刚兴起的生物频谱治疗的研究与应用中,都有着重要的作用。同时,它又是软件实现数字滤波器的必备组成部分之一。FFT算法的基本思想：利用DFT系数的特性，合并DFT运算中的某些项，把长序列的DFT—>短序列的DFT，从而减少其运算量。FFT算法分类:时间抽选法DIT:Decimation
4、-In-Time；频率抽选法DIF:Decimation-In-Frequency。在此以按时间抽选的基-2FFT算法为例进行说明。1.2算法原理N为2的整数幂的FFT算法称基-2FFT算法。设N点序列，=0,1,2,…N-1按n的奇偶分成两个长为N/2的序列=0,1,2,…,-1由于则的DFT：为偶数为奇数====0,1,2,…，N-1（1）其中：==（2）==（3）按式（1）计算得到的只是的前一半项数的结果，即（0≤≤—1）。由系数的周期性可推出的后一半值，即（≤≤N—1）：.（=—1）又因为，是以为周
5、期的，可推出：（4）同理可得，=（5）由此可得N点对应的DFT的计算式子：=0,1,2,…,-1（6）上一式计算的前一半值，下一式计算的后一半值。因此只要求出0～—1区间内各个整数值所对应的和，便可求出0到N-1点全部的值。明显节约了运算量。式中因子在复数乘法中起一个旋转的作用，称为旋转因子。公式（6）的运算可以归结为两个复数a、b求得复数和。用信号流程图的方法可以简单的表示为如图2所示。这样的运算称为蝶形运算，在FFT算法中占有核心的地位。图2时间抽选蝶形运算流图显然，每个蝶形运算对应于一次复数乘法和两次
6、复数加法运算。如果用DFT方法直接计算出和，共需次复数乘法运算，再作N/2次蝶形运算，又需N/2次复数乘法和N次复数加法。这样算出N点DFT共需要（+N）/2次复数乘法和(/2)+N次复数加法。当N较大时，同直接计算N点DFT所需的次复数乘加次数相比，几乎减少了一半的计算量。假设N/2还是偶数，则和这两个N/2点的DTF计算，又分别可以通过计算N/4点DFT和蝶形运算而得到。这时蝶形有两组，每组N/4个，总数也是N/2个，所以也需要N/2次复数乘法和N次复数加法。如果N=，则分解过程一直可以进行下去，共分解
7、M次，到2点DFT为止。以上所述就是FFT算法的核心思想。可以看出，这种罪基本形式的快速傅里叶算法要求点数是2的幂次。当序列长度不具有的形式时，可以补上一段0，使总长度为。1.3时间抽取过程的流图表示现在就N=8的情况对算法结构，即计算流图作详细的说明，由此可以直接得到关于N=的情况下得一些一般性结论。图3是8点DFT欧诺个两个4点DFT和4个蝶形运算实现的图示，图4中进一步将4点DFT作类似的分解，最后将图4中的2点DFT也画成蝶形运算流图，如图5所示。整个运算有3轮蝶形运算构成，每一轮有4个蝶形，但它们
8、的旋转因子和循环方式各轮有所不同。G(0)-14点DFT4点DFTG(1)G(2)G(3)H(0)H(1)H(2)H(3)-1-1-1图38点DFT时间抽选分解2点DFT-1-1-1-1-12点DFT2点DFT2点DFT-1-1-1图48点DFT时间抽选分解（续）-1-1-1-1-1-1-1-1-1-1-1-1图5反序输入顺序输出时间抽选FFT算法流图图5那样的结构对任何N=的序列都是适用的。整个N点DFT的计算
