快速傅里叶变换FFT算法源码经典

快速傅里叶变换FFT算法及其应用摘要本文较为系统地阐述了快速傅里叶变换的算法原理及其在数字信号处理等工程技术中的应用。根据抽取方法的不同，一维基2FFT算法分为两种：频域抽取的FFT算法和时频域抽取的FFT算法。第1节阐述了这两种FFT算法的原理。第2节给出了两种算法的编程思想和步骤。第3节阐述了一维非基2FFT的两种算法：Cooley-tukeyFFT算法和素因子算法(PrimeFactorAlgorithm)的思想原理，给出了在把一维非基2DFT的多层分解式转化为二层分解的过程中，如何综合运用这两种算法以达到总运算次数最少的方案；并以20点DFT为例描述了非基2FFT算法实现的一般步骤。第4节介绍了一维FFT算法在计算连续时间信号的傅里叶变换、离散信号的线性卷积、离散信号压缩和滤波等数字信号处理中的典型应用。第5节把一维FFT变换推广到二维FFT变换，并在一维FFT算法的基础上，给出了二维FFT算法的原理和实现过程。最后在附录中给出了一维DFT的基2FFT算法（包括频域抽取的FFT和IFFT算法、时域抽取的FFT和IFFT算法），一维任意非基2FFT算法，二维DFT的基2FFT算法以及二维DFT的任意非基2FFT算法的详细的VisualC++程序。本文通过各种流程图和表格，较为深入系统地阐述了FFT的算法原理；运用Matlab编程，通过大量生动的实例，图文并茂地列举出了FFT算法的各种应用，并在每个实例中都附上了完整的Matlab程序，可供读者参考。由于篇幅所限，本文未涉及FFT变换以及其应用的数学理论背景知识。关键词：FFT算法的应用，一维基2FFT算法，频域抽取，时域抽取，非基2FFT算法，Cooley-Tukey算法，素因子算法，线形卷积，信号压缩和滤波，二维FFT算法快速傅里叶变换FFT算法及其应用1目录1一维DFT的快速算法—FFT.................................................................................11.1频域抽取的基2算法......................................................................................11.1.1正变换的计算.......................................................................................................................11.1.2逆变换的计算.......................................................................................................................41.2时域抽取的基2算法.......................................................................................52一维基2FFT算法编程..........................................................................................63一维任意非基2FFT算法....................................................................................103.1COOLEY-TUKEYFFT算法..............................................................................103.2素因子算法(PRIMEFACTORALGORITHM,PFA)..............................................113.3一维任意非基2FFT算法..............................................................................134一维FFT算法的应用...........................................................................................164.1利用FFT计算连续时间信号的傅里叶变换................................................164.2利用FFT计算离散信号的线性卷积............................................................194.3利用FFT进行离散信号压缩........................................................................214.4利用FFT对离散信号进行滤波....................................................................244.5利用FFT提取离散信号中的最强正弦分量................................................275二维DFT的快速变换算法及应用简介..............................................................325.1二维FFT变换及其算法介绍........................................................................325.2二维FFT变换算法的应用............................................................................33参考文献......................................................................................................................33附录............................................................................................................................341．一维DFT的基2FFT算法VISUALC++程序...............................................34（1）频域抽取的FFT和IFFT算法.......................................................................................34（2）时域抽取的FFT和IFFT算法.......................................................................................392．一维任意非基2FFT算法VISUALC++程序.................................................443．二维DFT的基2FFT算法VISUALC++程序...............................................494．二维DFT的任意非基2FFT算法VISUALC++程序...................................5711一维DFT的快速算法—FFT当序列[]fn的点数不超过N时，它的N点DFT定义为210[][]01NiknNnFkfnekNπ−−==≤≤−∑（1）反变换IDFT定义为2101[][]01NiknNkfnFkenNNπ−==≤≤−∑（2）二者形式相似，快速算法的原理一样，这里先就其正变换进行讨论。令2/iNNWeπ−=，当k依次取为0,1,2,,1N−L时，可表示为如下的方程组：0001020(1)1011121(1)2021222(1)(1)0(1)1(1)(1)[0][0][1][2][1][1][0][1][2][1][2][0][1][2][1][1][0][1][1]NNNNNNNNNNNNNNNNNNNNNNFfWfWfWfNWFfWfWfWfNWFfWfWfWfNWFNfWfWfNW−−−−−−−⎧=++++−=++++−=++++−⎨−=+++−LLLML⎪⎪⎪⎪⎪⎪⎩（3）由上式可见，直接按照定义计算N点序列的N点DFT时，每行含N个复乘和N个加，从而直接按定义计算点的总计算量为2N个复乘和2N个加。当N较大时，2N很大，计算量过大不仅耗时长，还会因字长有限而产生较大的误差，甚至造成计算结果不收敛。所谓快速傅里叶变换就是能大大减少计算量而完成全部点计算的算法。下面介绍两种经典的DFT的快速算法：频域抽取的FFT算法和时域抽取的FFT算法。1.1频域抽取的基2算法1.1.1正变换的计算这里仅介绍基2算法，即是2的整次幂的情况。由定义10[][]01NknNnFkfnWkN−==≤≤−∑（4）把[]fn分成两半，即[]fn和[/2]fnN+(0/21)nN≤≤−，代入（4）式得/21/21(/2)00[][][/2]01NNknknNNNnnFkfnWfnNWkN−−+===++≤≤−∑∑（5）1一维DFT的快速算法—FFT2由于(/2)/2(1)knNknkNkknNNNN==−（5）式两项又可合并为/210[]{[](1)[/2]}01NkknNnFkfnfnNWkN−==+−+≤≤−∑（6）当2kr=为偶数时，注意到(1)1k−=，222/knrnirnNNNWWeπ−==/2rnNW=，（6）式变为/21/20/21/20[2]([][/2])()()0/21NrnNnNrnNnFrfnfnNWgnWGrrN−=−==++==≤≤−∑∑（7）当21kr=+为奇数时，(21)2(21)//2knrnirnNnrnNNNNWWeWWπ+−+===，（6）式变为/21/20/21/20[21]{([][/2])}()()0/21NnrnNNnNrnNnFrfnfnNWWpnWPrrN−=−=+=−+==≤≤−∑∑（8）这样就把一个N点序列（[]fn）的N点DFT（[]Fk）计算化成了两个/2N点序列（[]gn和[]pn）的/2N点DFT（[]Gr和[]Pr）计算。由[]fn划分成[]gn和[]pn的计算量为N个加，即[][/2]fnfnN++和[][/2],0/21fnfnNnN−+≤≤−和/2N个乘，即([][/2]),0/21nNfnfnNWnN−+≤≤−由于[]gn算出的/2N点DFT，是[]fn的N点DFT（[]Fk）中k为偶数的那一半，由[]pn算出的则是k为偶数的那一半，故需要把偶数k的[]Fk抽出来放在一起作为[]gn的DFT（()Gr）输出，同时把奇数k的[]Fk抽出来放在一起作为[]pn的DFT（()Pr）输出。由于k是频域变量，故这种算法称为频域抽取的FFT算法。接着，两个/2N点DFT仍可用上述方法各经/4N个乘/2N个加划分成两个/4N点DFT（同时还要做相应的频域抽取），从而共划分成4个/2N点DFT，总划分计算量仍是N个加和/2N个乘。这样的划分可一步步做下去，不难看出，快速傅里叶变换FFT算法及其应用3每步的总划分计算量都是N个加和/2N个乘。经过1M−步的划分后就划成了/2N个如下两点DFT的计算问题00