毕业论文:快速傅里叶变换FFT算法及其应用68页极速下载
1、手机端页面文档仅支持阅读 15 页,超过 15 页的文档需使用电脑才能全文阅读。
对图做这些变换,则得到图的流程图。
对图做这些变换,则得到图的流程图。
维的快速算法都是把偶数项放在前左边,把奇数项放在后右边,从而抽取以后若直接计算需半小时,而用计算只需即可完成,可见其效率之高,而且越大,的效率提高越明显。
图频域抽取的点计算流图般情况下,由于做了次分奇偶的抽取,此算法最后的个两点计算出的不是顺序抽取的。
次序的变化可用二进码来说明第次抽取所分的奇偶是由二进码第位是或来区分的,该位为时为偶数,该位为时为奇数,第二次抽奇偶是由二进码第位是或来区分的„„,每次抽取化可用二进码来说明第次抽取所分的奇偶是由二进码第位是或来区分的,该位为时为偶数,该位为时为奇数,于做了次分奇偶的抽取,此算法最后的个两点计算出的不是顺序抽取的。
次序的变部分内容简介,用算法计算所需的乘法个数为,而直接按定义计算所需的乘法个数为,二者相差倍。
若直接计算需半小时,而用计算只需即可完成,可见其效率之高,而且越大,的效率提高越明显。
图频域抽取的点计算流图般情况下,由于做了次分奇偶的抽取,此算法最后的个两点计算出的不是顺序抽取的。
次序的变化可用二进码来说明第次抽取所分的奇偶是由二进码第位是或来区分的,该位为时为偶数,该位为时为奇数,第二次抽奇偶是由二进码第位是或来区分的„„,每次抽取维的快速算法都是把偶数项放在前左边,把奇数项放在后右边,从而抽取以后数的二进码是按照二进制位从左向右依次排列的,和普通二进制数从右向左依次排列的的规律正好相反,所以称为倒位序。
在计算出之后要把倒位序变成顺序。
逆变换的计算所谓逆变换是指由求的计算,若直接按定义做计算,则除了求和号和正变换相同的计算量外,每算个都还需再多做个乘的乘法运算。
故按定义完成全部点的总计算量是个加和个乘。
下面从图导出它的快速算法,先讨论第列的点的逆运算如何完成。
由式得,由上式不难解出图频域抽取的点计算流图此计算过程如图所示,可以看出左边各列的划分计算也都是由个碟形运算来完成的,只是各碟形运算所乘的相移因子不同。
把每个碟形运算都用图的办法变成对应的逆运算,并把它们按输入在左输出在右重新排列,就得到了全部点的计算流图。
给出了的示例,图中先对顺序输入的做次的频域抽取,并把个乘的运算合成了个乘的运算放在了最前边,然后就开始做求逆的碟形运算。
时域抽取的基算法比较正变换和反变换的定义式可见,去掉乘的运算,把换成,交换和,反变换定义式就变成了正变换的定义式。
对图做这些变换,则得到图的流程图。
对图做这些变换,则得到图的流程图。
这就是时域抽取的算法流图。
进行碟形运算之前,先要对顺序的时域输入序列进行次的奇偶抽取,故称为时域抽取的算法。
图时域抽取的点计算流图维基算法编程比较图和图不难看出,两种算法的计算量是完全样的。
这里先算出个两点的图时域抽取的点计算流图然后把个两点的组合成个点的,再把个点的组合成个点的,经过次的组合之后,就得到了顺序点计算结果。
算法原理参考文献。
维基算法编程以频域抽取的基正变换为例,对的信号流图进行讨论,以找到算法的规律。
分级在进行变换的过程中,从点到两点共分了级,如图所示,从左到右依次为级,级,„,级。
倒位序在频域抽取的基算法中,输出数据不是按照序列的先后顺序排列的,这是由于变换过程中,输出按奇偶抽取的缘故。
如果将序列中标号用二进制值表示,那么在信号流图输入端,位于处,称为倒序。
以点为例,顺序和倒序的关系如表所示。
表顺序和倒序对照表顺序倒序十进制数二进制数二进制数十进制数从表可以看出,个自然顺序二进制数,是在最低位加,逢向左移位而倒序数的顺序是在最高位加,逢向右移位。
用表示顺序数,表示倒序数,表示位权重。
对于个倒序数来说,下个倒序数可以按下面的方法求先对最高位加,相当于十进制运算。
如果,说明二进制最高位为,则直接由得到下个倒序值如果,说明二进制变换后的信号变换后的信号运行结果为原信号变换后的信号变换后的信号附录维任意非基算法程序设原始信号由连续信号离散化采样获得,即,维任意非基算法将维数组映射为三维数组进行第层变换为临时数组,存放变换前数据进行第二层变换乘以相移因子进行第三层变换附录将三维数组还原为维数组维任意非基算法将信号乘以将维数组映射为三维数组进行第层变换为临时数组,存放变换前数据进行第二层变换乘以相移因子进行第三层变换将三维数组还原为维数组附录显示信号数据主函数原信号数据,原信号变换后的信号变换后的信号快速傅里叶变换算法及其应用摘要本文较为系统地阐述了快速傅里叶变换的算法原理及其在数字信号处理等工程技术中的应用。
根据抽取方法的不同,维基算法分为两种频域抽取的算法和时频域抽取的算法。
第节阐述了这两种算法的原理。
第节给出了两种算法的编程思想和步骤。
第节阐述了维非基的两种算法算法和素因子算法的思想原理,给出了在把维非基的多层分解式转化为二层分解的过程中,如何综合运用这两种算法以达到总运算次数最少的方案并以点为例描述了非基算法实现的般步骤。
第节介绍了维算法在计算连续时间信号的傅里叶变换离散信号的线性卷积离散信号压缩和滤波等数字信号处理中的典型应用。
第节把维变换推广到二维变换,并在维算法的基础上,给出了二维算法的原理和实现过程。
最后在附录中给出了维的基算法包括频域抽取的和算法时域抽取的和算法,维任意非基算法,二维的基算法以及二维的任意非基算法的详细的程序。
本文通过各种流程图和表格,较为深入系统地阐述了的算法原理运用编程,通过大量生动的实例,图文并茂地列举出了算法的各种应用,并在每个实例中都附上了完整的程序,可供读者参考。
由于篇幅所限,本文未涉及变换以及其应用的数学理论背景知识。
关键词算法的应用,维基算法,频域抽取
