【毕业设计】快速傅里叶变换FFT算法及其应用㊣精品文档值得下载

按照二进制位从左向右依次排列的，和普通二进制数从右向左依次排列的的规律正好相反，所以称为倒位序。

在计算出之后要把倒位序变成顺序。

逆变换的计算所谓逆变换是指由求的计算，若直接按定义做计算，则除了求和号和正变换相同的计算量外，每算个都还需再多做个乘的乘法运算。

故按定义完成全部点的总计算量是个加和个乘。

下面从图导出它的快速算法，先讨论第列的点的逆运算如何完成。

由式得，由上式不难解出图频域抽取的点计算流图此计算过程如图所示，可以看出左边各列的划分计算也都是由个碟形运算来完成的，只是各碟形运算所乘的相移因子不同。

把每个碟形运算都用图的办法变成对应的逆运算，并把它们按输入在左输出在右重新排列，就得到了全部点的计算流图。

给出了的示例，图中先对顺序输入的做次的频域抽取，并把个乘的运算合成了个乘的运算放在了最前边，然后就开始做求逆的碟形运算。

时域抽取的基算法比较正变换和反变换的定义式可见，去掉乘的运算，把换成，交换和，反变换定义式就变成了正变换的定义式。

对图做这些变换，则得到图的流程图。

这就是时域抽取的算法流图。

进行碟形运算之前，先要对顺序的时域输入序列进行次的奇偶抽取，故称为时域抽取的算法。

图时域抽取的点计算流图维基算法编程比较图和图不难看出，两种算法的计算量是完全样的。

这里先算出个两点的图时域抽取的点计算流图然后把个两点的组合成个点的，再把个点的组合成个点的，经过次的组合之后，就得到了顺序点计算结果。

算法原理参考文献。

维基算法编程以频域抽取的基正变换为例，对的信号流图进行讨论，以找到算法的规律。

分级在进行变换的过程中，从点到两点共分了级，如图所示，从左到右依次为级，级，„，级。

倒位序在频域抽取的基算法中，输出数据不是按照序列的先后顺序排列的，这是由于变换过程中，输出按奇偶抽取的缘故。

如果将序列中标号用二进制值表示，那么在信号流图输入端，位于处，称为倒序。

以点为例，顺序和倒序的关系如表所示。

表顺序和倒序对照表顺序倒序十进制数二进制数二进制数十进制数从表可以看出，个自然顺序二进制数，是在最低位加，逢向左移位而倒序数的顺序是在最高位加，逢向右移位。

用表示顺序数，表示倒序数，表示位权重。

对于个倒序数来说，下个倒序数可以按下面的方法求先对最高位加，相当于十进制运算。

如果，说明二进制最高位为，则直接由得到下个倒序值如果，说明二进制最高位为，则将的最高位变为，通过实现，同时令，接着判断次高位是否为，直到位为时，令。

归结起来算法流程图如图所示。

维基算法编程图倒位序程序流程图图频域抽取程序流程图蝶形运算单元和同址计算频域抽取的信号流图中，基本的运算结构如图所示，该运算结构的形状像蝴蝶，故称为蝶形运算单元。

在这结构中，和运算关系分别为进行第层变换附录为临时数组，存放变换前数据进行第二层变换乘以相移因子进行第三层变换将三维数组还原为维数组二维任意非基算法逐行进行维变换维任意非基算法将信号乘以将维数组映射为三维数组进行第层变换为临时数组，存放变换前数据附录进行第二层变换乘以相移因子进行第三层变换将三维数组还原为维数组逐列进行维变换维任意非基算法将信号乘以将维数组映射为三维数组进行第层变换为临时数组，存放变换前数据进行第二层变换附录乘以相移因子进行第三层变换将三维数组还原为维数组显示信号数据，主函数原始二维信号，原信号二维变换后的信号二维变换后的信号运行结果略。

快速傅里叶变换算法及其应用摘要本文较为系统地阐述了快速傅里叶变换的算法原理及其在数字信号处理等工程技术中的应用。

根据抽取方法的不同，维基算法分为两种频域抽取的算法和时频域抽取的算法。

第节阐述了这两种算法的原理。

第节给出了两种算法的编程思想和步骤。

第节阐述了维非基的两种算法算法和素因子算法的思想原理，给出了在把维非基的多层分解式转化为二层分解的过程中，如何综合运用这两种算法以达到总运算次数最少的方案并以点为例描述了非基算法实现的般步骤。

第节介绍了维算法在计算连续时间信号的傅里叶变换离散信号的线性卷积离散信号压缩和滤波等数字信号处理中的典型应用。

第节把维变换推广到二维变换，并在维算法的基础上，给出了二维算法的原理和实现过程。

最后在附录中给出了维的基算法包括频域抽取的和算法时域抽取的和算法，维任意非基算法，二维的基算法以及二维的任意非基算法的详细的程序。

本文通过各种流程图和表格，较为深入系统地阐述了的算法原理运用编程，通过大量生动的实例，图文并茂地列举出了算法的各种应用，并在每个实例中都附上了完整的程序，可供读者参考。

由于篇幅所限，本文未涉及变换以及其应用的数学理论背景知识。

关键词算法的应用，维基算法，频域抽取，时域抽取，非基算法，算法，素因子算法，线形卷积，信号压缩和滤波，二维算法摘要目录摘要目录维的快速算法频域抽取的基算法正变换的计算逆变换的计算时域抽取的基算法维基算法编程维任意非基算法算法素因子算法维任意非基算法维算法的应用利用计算连续时间信号的傅里叶变换利用计算离散信号的线性卷积利用进行离散信号压缩利用对离散信号进行滤波利用提取离散信号中的最强正弦分量二维的快速变换算法及应用简介二维变换及其算法介绍二维变换算法的应用参考文献附录维的基算法程序频域抽取的和算法时域抽取的和算法维任意非基算法程序二维的基算法程序二维的任意非基算法程序维的快速算法当序列的点数不超过时，它的点定义为反变换定义为二者形式相似，快速算法的原理样，这里先就其正变换进行讨论。

令，当依次取为时，可表示为如下的方程组由上式可见，直接按照定义计算点序列的点时，每行含个复乘和个加，从而直接按定义计算点的总计算量为个复乘和个加。

当较大时，很大，计算量过大不仅耗时长，还会因字长有限而产生较大的误差，甚至造成计算结果不收敛。

所谓快速傅里叶变换就是能大大减少计算量而完成全部点计算的算法。

下面介绍两种经典的的快速算法频域抽取的算法和时域抽取的算法。

频域抽取的基算法正变换的计算这里仅介绍基算法，即是的整次幂的情况。

由定义维的快速算法把分成两半，即和，代入式得由于式两项又可合并为当为偶数时，注意到，，式变为当为奇数时，，式变为这样就把个点序列的点计算化成了两个点序列和的点和计算。

由划分成和的计算量为个加，即和，和个乘，即，由于算出的点，是的点中为偶数的那半，由算出的则是为偶数的那半，故需要把偶数的抽出来放在起作为的输出，同时把奇数的抽出来放在起作为的输出。

由于是频域变量，故这种算法称为频域抽取的算法。

接着，两个点仍可用上述方法各经个乘个加划分成两个点同时还要做相应的频域抽取，从而共划分成个点，总划分计算量仍是个加和个乘。

这样的划分可步步做下去，不难看出，每步的总划分计算量都是个加和个乘。

经过步的划分后就划成了个如下两点的计算问题上式所需计算量是个加和个乘，于是完成个两点的总计算量仍是个加和个乘。

从而完成全部点的总计算量个加和个乘，这比直接按定义计算所需的个乘和加要少得多。

例如，，，用算法计算所需的乘法个数为，而直接按定义计算所需的乘法个数为，二者相差倍。

若直接计算需半小时，而用计算只需即可完成，可见其效率之高，而且越大，的效率提高越明显。

图频域抽取的点计算流图般情况下，由于做了次分奇偶的抽取，此算法最后的个两点计算出的不是顺序抽取的。