快速傅里叶变换FFT算法及其应用.doc

《快速傅里叶变换FFT算法及其应用.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、快速傅里叶变换FFT算法及其应用快速傅里叶变换FFT算法及其应用摘要本文较为系统地阐述了快速傅里叶变换的算法原理及其在数字信号处理等工程技术中的应用。根据抽取方法的不同，一维基2FFT算法分为两种：频域抽取的FFT算法和时频域抽取的FFT算法。第1节阐述了这两种FFT算法的原理。第2节给出了两种算法的编程思想和步骤。第3节阐述了一维非基2FFT的两种算法：Cooley-tukeyFFT算法和素因子算法(PrimeFactorAlgorithm)的思想原理，给出了在把一维非基2DFT的多层分解式转化为二层分解的过程中，如何综

2、合运用这两种算法以达到总运算次数最少的方案；并以20点DFT为例描述了非基2FFT算法实现的一般步骤。第4节介绍了一维FFT算法在计算连续时间信号的傅里叶变换、离散信号的线性卷积、离散信号压缩和滤波等数字信号处理中的典型应用。第5节把一维FFT变换推广到二维FFT变换，并在一维FFT算法的基础上，给出了二维FFT算法的原理和实现过程。最后在附录中给出了一维DFT的基2FFT算法（包括频域抽取的FFT和IFFT算法、时域抽取的FFT和IFFT算法），一维任意非基2FFT算法，二维DFT的基2FFT算法以及二维DFT的任意非基

3、2FFT算法的详细的VisualC++程序。本文通过各种流程图和表格，较为深入系统地阐述了FFT的算法原理；运用Matlab编程，通过大量生动的实例，图文并茂地列举出了FFT算法的各种应用，并在每个实例中都附上了完整的Matlab程序，可供读者参考。由于篇幅所限，本文未涉及FFT变换以及其应用的数学理论背景知识。关键词：FFT算法的应用，一维基2FFT算法，频域抽取，时域抽取，非基2FFT算法，Cooley-Tukey算法，素因子算法，线形卷积，信号压缩和滤波，二维FFT算法67快速傅里叶变换FFT算法及其应用67快速傅里

4、叶变换FFT算法及其应用目录摘要1目录21一维DFT的快速算法—FFT41.1频域抽取的基2算法41.1.1正变换的计算41.1.2逆变换的计算71.2时域抽取的基2算法82一维基2FFT算法编程103一维任意非基2FFT算法143.1Cooley-TukeyFFT算法143.2素因子算法（PFA）143.3一维任意非基2FFT算法164一维FFT算法的应用204.1利用FFT计算连续时间信号的傅里叶变换204.2利用FFT计算离散信号的线性卷积234.3利用FFT进行离散信号压缩254.4利用FFT对离散信号进行滤波28

5、4.5利用FFT提取离散信号中的最强正弦分量315二维DFT的快速变换算法及应用简介365.1二维FFT变换及其算法介绍365.2二维FFT变换算法的应用37参考文献38附录391．一维DFT的基2FFT算法VisualC++程序39（1）频域抽取的FFT和IFFT算法39（2）时域抽取的FFT和IFFT算法442．一维任意非基2FFT算法VisualC++程序4967快速傅里叶变换FFT算法及其应用3．二维DFT的基2FFT算法VisualC++程序544．二维DFT的任意非基2FFT算法VisualC++程序621一维

6、DFT的快速算法—FFT当序列的点数不超过时，它的点定义为（1）反变换定义为（2）二者形式相似，快速算法的原理一样，这里先就其正变换进行讨论。令，当依次取为时，可表示为如下的方程组：（3）由上式可见，直接按照定义计算点序列的点时，每行含个复乘和个加，从而直接按定义计算点的总计算量为个复乘和个加。当较大时，很大，计算量过大不仅耗时长，还会因字长有限而产生较大的误差，甚至造成计算结果不收敛。所谓快速傅里叶变换就是能大大减少计算量而完成全部点计算的算法。下面介绍两种经典的的快速算法：频域抽取的算法和时域抽取的算法。1.1频域抽取

7、的基2算法1.1.1正变换的计算这里仅介绍基2算法，即是2的整次幂的情况。由定义（4）67快速傅里叶变换FFT算法及其应用把分成两半，即和，代入（4）式得（5）由于（5）式两项又可合并为（6）当为偶数时，注意到，，（6）式变为（7）当为奇数时，，（6）式变为（8）这样就把一个点序列（）的点（）计算化成了两个点序列（和）的点（和）计算。由划分成和的计算量为个加，即和和个乘，即由于算出的点，是的点（）中为偶数的那一半，由算出的则是为偶数的那一半，故需要把偶数的抽出来放在一起作为的（）输出，同时把奇数的抽出来放在一起作为的（）输

8、出。由于是频域变量，故这种算法称为频域抽取的算法。67快速傅里叶变换FFT算法及其应用接着，两个点仍可用上述方法各经个乘个加划分成两个点（同时还要做相应的频域抽取），从而共划分成4个点，总划分计算量仍是个加和个乘。这样的划分可一步步做下去，不难看出，每步的总划分计算量都是个加和个乘。经过步的划分后就划成