《快速傅里叶变换FFT算法及其应用》由会员分享，可在线阅读，更多相关《快速傅里叶变换FFT算法及其应用（120页珍藏版）》请在金锄头文库上搜索。
1、快速傅里叶变换 FFT 算法及其应用摘 要本文较为系统地阐述了快速傅里叶变换的算法原理及其在数字信号处理等工程技术中的应用。根据抽取方法的不同，一维基 2 FFT 算法分为两种：频域抽取的 FFT 算法和时频域抽取的 FFT 算法。第 1 节阐述了这两种 FFT 算法的原理。第 2 节给出了两种算法的编程思想和步骤。第 3 节阐述了一维非基 2 FFT 的两种算法：Cooley-tukey FFT 算法 和 素因子算法(Prime Factor Algorithm)的思想原理，给出了在把一维非基 2 DFT 的多层分解式转化为二层分解的过程中，如何综合运用这两种算法以达到总运算次数最少的方案；
2、并以 20点 DFT 为例描述了非基 2 FFT 算法实现的一般步骤。第 4 节介绍了一维 FFT 算法在计算连续时间信号的傅里叶变换、离散信号的线性卷积、离散信号压缩和滤波等数字信号处理中的典型应用。第 5 节把一维 FFT 变换推广到二维 FFT 变换，并在一维 FFT 算法的基础上，给出了二维 FFT 算法的原理和实现过程。最后在附录中给出了一维DFT 的基 2 FFT 算法 （包括频域抽取的 FFT 和 IFFT 算法、时域抽取的 FFT 和 IFFT 算法） ，一维任意非基 2 FFT 算法，二维 DFT 的基2 FFT 算法以及二维 DFT 的任意非基 2 FFT 算法的详细的 V
3、isual C+程序。本文通过各种流程图和表格，较为深入系统地阐述了 FFT 的算法原理；运用 Matlab 编程，通过大量生动的实例，图文并茂地列举快速傅里叶变换 FFT 算法及其应用1出了 FFT 算法的各种应用，并在每个实例中都附上了完整的 Matlab程序，可供读者参考。由于篇幅所限，本文未涉及 FFT 变换以及其应用的数学理论背景知识。关键词：FFT 算法的应用，一维基 2 FFT 算法，频域抽取，时域抽取，非基 2 FFT 算法， Cooley-Tukey 算法 ，素因子算法，线形卷积，信号压缩和滤波，二维 FFT 算法摘 要2目 录摘 要 .0目 录 .21 一维 DFT 的快速
4、算法 FFT.31.1 频域抽取的基 2 算法 .41.1.1 正变换的计算 .41.1.2 逆变换的计算 .71.2 时域抽取的基 2 算法 .82 一维基 2 FFT 算法编程 .103 一维任意非基 2 FFT 算法 .143.1 COOLEY-TUKEY FFT 算法 .143.2 素因子算法（PFA） .153.3 一维任意非基 2 FFT 算法 .184 一维 FFT 算法的应用 .214.1 利用 FFT 计算连续时间信号的傅里叶变换 .214.2 利用 FFT 计算离散信号的线性卷积 .254.3 利用 FFT 进行离散信号压缩 .284.4 利用 FFT 对离散信号进行滤波
5、.334.5 利用 FFT 提取离散信号中的最强正弦分量 .37快速傅里叶变换 FFT 算法及其应用35 二维 DFT 的快速变换算法及应用简介 .435.1 二维 FFT 变换及其算法介绍 .435.2 二维 FFT 变换算法的应用 .44参考文献 .45附 录 .461一维 DFT 的基 2 FFT 算法 VISUAL C+程序 .46（1） 频域抽取的 FFT 和 IFFT 算法 .46（2） 时域抽取的 FFT 和 IFFT 算法 .592一维任意非基 2 FFT 算法 VISUAL C+程序 .723二维 DFT 的基 2 FFT 算法 VISUAL C+程序 .834二维 DFT
6、的任意非基 2 FFT 算法 VISUAL C+程序 .1021 一维 DFT 的快速算法FFT当序列 的点数不超过 时，它的 点 定义为fnNDFT21001iknNnFkfe（1）反变换 定义为IDFT21001NiknkfnFeN（2）二者形式相似，快速算法的原理一样，这里先就其正变换进行1 一维 DFT 的快速算法FFT4讨论。令 ，当 依次取为 时，可表示为如下的2/iNWek0,12,NL方程组：001020(1)11202122(1)(1)0(1) (1)NNNNNNNFffWffWfffffffLM（3）由上式可见，直接按照定义计算 点序列的 点 时，每行DFT含 个复乘和 个
7、加，从而直接按定义计算点的总计算量为 个复N 2N乘和 个加。当 较大时， 很大，计算量过大不仅耗时长，还会2N2因字长有限而产生较大的误差，甚至造成计算结果不收敛。所谓快速傅里叶变换就是能大大减少计算量而完成全部点计算的算法。下面介绍两种经典的 的快速算法：频域抽取的 算法和时域抽DFTFT取的 算法。FT1.1 频域抽取的基 2 算法1.1.1 正变换的计算这里仅介绍基 2 算法，即是 2 的整次幂的情况。由定义101NknnFkfWN（4）把 分成两半，即 和 ，代入（4）fnf/2f(/21)式得/21/21(/2)00/0NNknknNnFkfWfWk （5）由于快速傅里叶变换 FF
8、T 算法及其应用5(/2)/2(1)knNknNknNWW（5）式两项又可合并为/210()/201NkknNnFkff（6）当 为偶数时，注意到 ，2kr(1)k， （6）式变为/ninNNWe/2rnW/21 /20/2()(1NrnNnrnNFrfWgG（7）当 为奇数时， ， （6）式21kr(21)2(1)/2knrnirnNnrNWeW变为/21 /20/2(/)(01nrNnNrnNFrfpP（8）这样就把一个 点序列（ ）的 点 （ ）计算化成了NfnDFTk两个 点序列（ 和 ）的 点 （ 和 ）计算。/2gnp/2NGrP由 划分成fn和 的计算量为 个加，即p和/2fn/
9、2,0/21fnnN和 个乘，即/2N(/),/nNfW由于 算出的 点 ，是 的 点 （ ）中 为gn/2NDFTfDFTk偶数的那一半，由 算出的则是 为偶数的那一半，故需要把偶数pk的 抽出来放在一起作为 的 （ ）输出，同时把奇数kFgn()Gr1 一维 DFT 的快速算法FFT6的 抽出来放在一起作为 的 （ ）输出。由于 是频kFpnDFT()Prk域变量，故这种算法称为频域抽取的 算法。接着，两个 点 仍可用上述方法各经 个乘 个加/2NT/4N/2划分成两个 点 （同时还要做相应的频域抽取） ，从而共划分4DF成 4 个 点 ，总划分计算量仍是 个加和 个乘。这样的/ /划分可
10、一步步做下去，不难看出，每步的总划分计算量都是 个加和 个乘。/2N经过 步的划分后就划成了 个如下两点 的计算问题1M/2NDFT00121022()AaWbaB （9）上式所需计算量是 2 个加和 1 个乘，于是完成 个两点/N的总计算量仍是 个加和 个乘。从而完成全部 点 的DFTN/ DFT总计算量 个加和 个乘，这比直接2logM22(/)logM按定义计算所需的 个乘和加要少得多。例如， ，104，用 算法计算所需的乘法个数为 ，而直10 /N5接按定义计算所需的乘法个数为 ，二者相差2104N倍。若直接计算需半小时，而用 计算只需 9s 即可完24/5 FT成，可见其效率之高，而且 越大， 的效率提高越明显。f0 F0000 F0 F0000f1
