资源描述：
《按频率抽取的快速傅里叶变换》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、《数字信号处理》课程设计报告按频率抽取的DFT快速算法分析及MATLAB实现专业：通信工程班级：组次：姓名：学号：目录摘要……………………………………………………………………1关键字……………………………………………………………………10引言……………………………………………………………………11按频率抽取的DFT快速算法原理……………………………………12DIF-FFT的运算规律及编程思想……………………………………22.1原位计算…………………………………………………………22.2序列的倒序………………………………………
2、………………22.3旋转因子的变换规律……………………………………………22.4蝶形运算规律……………………………………………………42.5编程思想及程序框图……………………………………………43DIF-FFT算法运算量分析……………………………………………54MATLAB程序实现……………………………………………………55结束语…………………………………………………………………7参考文献…………………………………………………………………7按频率抽取的DFT快速算法分析及MATLAB实现摘要：DFT是数字信号分析与处理中的一
3、种重要变换。但直接计算DFT的计算量与变换区间长度N的平方成正比，计算量非常大。DFT的快速算法使运算效率提高了1~2个数量级，为数字信号处理技术应用于各种信号的实时处理创造了条件。为了对FFT有更加深入的了解，本文对DIF-FFT的原理进行了分析，并给出MATLAB程序实现的方法与步骤。关键词：DFT;DIF-FFT;MATLAB;0引言DFT是数字信号分析与处理中的一种重要变换。但直接计算DFT的计算量与变换区间长度N的平方成正比，计算量非常大。DFT的快速算法使运算效率提高了1~2个数量级，为数字信号处理技术应用于各种
4、信号的实时处理创造了条件。本文通过对按频率抽取的DFT快速算法原理介绍与MATLAB实现以期使我们对傅里叶快速算法有更全面的理解，为我们以后更复杂的快速算法学习打下基础。1按频率抽取的DFT快速算法原理设序列x(n)的长度为,将序列前后对半分开，得到两个子序列，如下：式中：将x(k)分解成偶数组与奇数组，当k取偶数（k=2m,m=0,1,…，N/2-1）时：（1）当k取奇数（k=2m+1,m=0,1,…,N/2-1）时，（2）令：其中，n=0,1,2,…，N/2-1将分别代入（1）、（2）式，可得：（3）（3）式表明，X(k
5、)按奇偶k值分为两组，其偶数组是的N/2点DFT，奇数组则是的N/2点DFT。、和x（n）之间的关系可以用图1所示的蝶形运算流图符号表示。图2表示N=8的DIF-FFT运算流图。图1DTF-FFT蝶形运算流图符号图2DIF-FFT的运算流图（N=8）2DIF-FFT的运算规律及编程思想2.1原位计算点的FFT共进行M级运算，每级由N/2个蝶形运算组成。同一级中，每个蝶形的两个输入数据只对计算本蝶形有用，而且每个蝶形的输入、输出数据结点又同在一条水平线上，这就意味着计算完一个蝶形后，所得输出数据可立即存入原输入数据所占用的存储
6、单元。这样，经过M级运算后，原来存放输入序列数据的N个存储单元中便依次存放X（k）的N个值。原位计算可节省大量内存，从而使设备陈本降低。2.2序列的倒序由图2可知，DIF-FFT算法输入序列为自然序列，而输出为倒序排列。因此M级运算完后，要对输出数据进行倒序才能得到自然顺序的X(k)。图3为顺序与倒序二进制对照图。顺序倒序十进制数I二进制数二进制数十进制数J0000000010011004201001023011110641000011510110156110011371111117图3顺序与倒序二进制对照图2.3旋转因子的
7、变换规律N点的DFT快速傅里叶运算流图中，每级都有N/2个蝶形。每个蝶形都要乘以因子，称其为旋转因子，P为旋转因子的指数。但各级的旋转因子和循环方式都有所不同。为了编写计算程序，下面列出旋转因子与运算级数的关系。用L表示从左到右的运算级数（L=1,2,…，M），第L级共有个不同的旋转因子。对N=的一般情况，第L级的旋转因子为：J=0,1,2，…，-1因为所以J=0,1,2,-12.4蝶形运算规律对点FFT，输入倒位序，输出自然序，设第L级运算每个蝶形的两节点距离为B行，则第L级运算：2.5编程思想及程序框图计算x的长度n,不
8、到2的数幂，补0开始读入x(n)补零，使蝶形运算序列倒序输出结束观察图2可以归纳出一些对编程有用的运算规律：第L级中，每个蝶形的两个输入数据相距B=个点；每级有B个不同的因子；同一旋转因子对应着间隔为点的个蝶形。频率抽取法输入为自然顺序，输出为倒序。图4为大致流程图。图5为DIF-FFT运
