资源描述：
《快速傅里叶变换-基4时间抽取fft算法matlab实现.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、快速傅里叶变换-基4时间抽取FFT算法matlab实现作者姓名：李林摘要：(快速傅里叶变换)算法与(离散傅里叶变换)算法比较,其运算量显著减少,用计算机实现时速度大为提高。但过程所需的运算量仍较可观,常给数字信号的实时处理带来困难,理论和实践表明,若要加快算法在计算机上的实现,关键是得设法减少过程在乘法运算上的时间开销。若改进算法,减少过程中的乘法次数,则无疑能加快的实现。通常的幂法都是“基分解法”,即长度为的序列由两个长度为的序列的组合表示;而这两个长度为的序列各自又分别由两个长度为的序列的组合表示,按照这一做法对序列进行反复分解,直到每个序列的
2、长度等于为止。这个分解、组合过程如同一棵标准二叉树。按分解的逆过程进行组合运算便得到所要求的频谱序列,,)整个变换过程共需要进行次复数乘法运算。参考上述的分解、组合方法,对序列进行“基分解”,即长度为的序列由四个长度为的序列组合表示。关键词：基分解法基分解运算时间和精度目录一，前言1，实验目的2，题目要求3，考查要求二，基—4FFT算法原理1，基—4FFT定义：2，举例3,旋转因子的性质4,16点基4时间抽取FFT算法流图三，基—4FFT运算的实现1，算法分析2.算法流程图3.Matlab程序执行结果四，两种程序运算量分析和比较1，matlab自带
3、函数运算量分析2，基四FFT的运算量3，运算结果比较4，结果分析五，设计总结六，参考文献七，附录：一，前言1，实验目的:检查学生的综合应用能力。2，题目要求：已知输入信号x(t)=0.6sin(200πt)+sin(400πt)+0.3sin(800πt)。实现基4时间抽取的FFT算法的1024点，4096点变换，并与matlab自带函数进行比较，包括运算时间和精度3，考查要求（1）给出快速傅里叶变换程序；（2）对给定信号进行频谱分析；（3）给出与matlab自带函数比较结果二，基—4FFT算法原理1，基—4FFT定义：在的特殊情况下，即当时，混合
4、基算法变成基—4FFT算法。2，举例以则有因而整序后可得综上得它的基本运算有三部：(1)做X(n)的(2)将乘旋转因子后做4点的(变量为)，得到(3)由于的变量是在前，在后，是基4倒位序的序列，因此，将其变量整序后得到正常顺序输出的序列。3,旋转因子的性质(1)周期性(2)对称性(3)可约性4,16点基4时间抽取FFT算法流图三，基—4FFT运算的实现1.算法分析（1）实现输入数据的比特反转输入数据的比特反转实际上就是将输入数据进行码位倒置，以便在整个运算后输出序列是一个自然序列。在用汇编指令进行码位倒置时，使用位码倒置寻址可以大大提高程序执行速度
5、和使用存储器的效率。在这种寻址方式下，AR0存放的整数N的FFT点的一半，一个辅助寄存器指向一个数据存放单元。当使用位码倒置寻址将AR0加到辅助寄存器时，地址将以位码倒置的方式产生。（2）实现N点复数FFTN点复数FFT算法的实现可分为三个功能块，即第一级蝶形运算、第二级蝶形运算、第三级至级蝶形运算。队以任何一个4的整数幂N=4^M，总可以通过M次分解后最后成为四点的DFT运算。通过这样的M次分解，可以构成M级迭代计算，每级由N/4个蝶形运算完成。2.算法流程图如下for(L=1;L<=M;L++)for(J=0;J<=B-1;J++)·for(k
6、=J;k<=N-1;k=k+2L)3.Matlab程序执行结果如下基四FFT自编函数1024点的频谱图，程序见附录基四FFT自编函数1024点的频谱图，程序见附录四，两种程序运算量分析和比较1，matlab自带函数运算量分析计算机运算是计算方式如下由以上表达是知计算一个N点DFT，共需次复乘，对于本题的点计算的次数为：，对于4096点计算的次数为2，基四FFT的运算量由于计算量大，且要求相当大的内存，难以实现实时处理，限制了DFT的应用。长期以来，人们一直在寻求一种能提高DFT运算速度的方法FFT便是Cooley&Tukey在1965年提出的的快速
7、算法，它可以使运算速度提高几百倍，从而使数字信号处理学科成为一个新兴的应用学科。1）、DIT―FFT算法与直接计算DFT运算量的比较；1)、N=的DFT运算可分成M级，每一级有N/4个蝶形，每个蝶形有一次复乘两次复加。2)、所以M级共有次复乘和次复加3)、若直接计算DFT，需次复乘和N(N-1)次复加3，运算结果比较自带函数运算量结果表格N1024点4096点复乘次数1048576次16777216复加次数1047552次16773120运算时间1.047552s16.773120s假设计算机每运行一次需时1us基四FFT函数运算量结果表格N102
8、4点4096点复乘次数1280次6144复加次数2560次12288次运算时间0.00256s0.012288s假设计算机
