武汉理工大学8点基于DIF的FFT

课程设计任务书学生姓名：李嘉辛专业班级：电信1206指导教师：黄朝兵工作单位：信息工程学院题目：8点基于DIF的FFT的实现初始条件：具备Matlab编程能力；熟悉基于DIF的FFT的实现原理；提供编程所需要的计算机一台要求完成的主要任务：（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1、独立编写一个8点的基于DIF的FFT实现程序，不能使用matlab自带的FFT实现函数2、并调用该函数实现16点的FFT运算，用matlab自带函数对运行结果结果进行验证3、完成符合学校要求的设计说明书时间安排：一周，其中3天程序设计，2天程序调试指导教师签名：年月日系主任（或责任教师）签名：年月日目录摘要........................................................................11概述......................................................................11.1数字信号处理定义............................................................................................................................11.2数字信号处理的特点及实现方法...................................................................................................12理论分析..................................................................22.1DFT的定义.......................................................................................................................................22.2直接计算DFT的问题及FFT思想..................................................................................................22.3基2按时间抽取（DIT）的FFT算法..............................................................................................22.4基2按频率抽取（DIF）的FFT算法..............................................................................................42.5按频率抽取的FFT的特点.............................................................................................................62.5.1原位运算..................................................................................................................................62.5.2蝶形运算两节点之间的“距离”..........................................................................................62.5.3旋转因子的变化规律..............................................................................................................63程序设计..................................................................73.1变址...................................................................................................................................................73.2L级递推计算...................................................................................................................................74结果及分析................................................................95心得体会.................................................................12参考文献...................................................................13武汉理工大学《数字信号处理》课程设计说明书1摘要快速傅里叶变换（FFT）是离散傅里叶变换（DFT）的快速算法，FFT算法通过利用旋转因子的性质，将一个大点数DFT化成几个小点数DFT，就可以大大减少运算量。DIF-FFT是利用频率抽选的FFT算法，在Matlab中可以通过三重循环语句实现。关键词：FFT，蝶形运算，倒序排列武汉理工大学《数字信号处理》课程设计说明书11概述1.1数字信号处理定义数字信号是用数字序列表示的信号，数字信号处理就是通过计算机或专用处理设备，用数值计算等数字方式对数字序列进行各种处理，将数字信号变换成符合要求的某种形式。数字信号处理主要包括数字滤波和数字频谱分析两大部分。例如，对数字信号进行滤波，限制其频带或滤除噪声和干扰，以提取和增强信号的有用分量；对信号进行频谱分析或功率分析，了解信号的频谱组成，以对信号进行识别。当然，凡是用数字方式对信号进行滤波，变换，增强，压缩，估计和识别等都是数字信号处理的研究范畴。数字信号处理在理论上所涉及的范围及其广泛。数字领域中的微积分，概率统计，随机过程，高等代数，数值分析，复变函数和各种变换（如傅里叶变换，Z变换，离散傅里叶变换，小波变换等）都是它的基本工具，网络理论，信号与系统等则是它的理论基础。在科学发展上，数字信号处理又和最优控制，通信理论等紧密相连，目前已成为人工智能，模式识别，神经网络等新兴学科的重要理论基础，其实现技术又和计算机科学和微电子技术密不可分。因此，数字信号处理是把经典的理论基础体系作为自身的理论基础，同时又使自己成为一系列新兴学科的理论基础。1.2数字信号处理的特点及实现方法与模拟信号处理相比，数字信号处理具有高精度、高稳定性、灵活性好、易于大规模集成等显著的优点。数字信号处理的主要研究对象是数字信号，且采用数值运算的方法达到处理的目的。数字信号处理的实现方法基本上可以分为软件实现方法、硬件实现方法和软硬件想结合的实现方法。数字信号处理的理论、算法和实现方法三者是密不可分的。武汉理工大学《数字信号处理》课程设计说明书22理论分析2.1DFT的定义对于有限长离散数字信号{x[n]}，0nN-1，其离散谱{X[k]}可以由离散付氏变换（DFT）求得。DFT的定义为：210[][]NjnkNnXkxne，k=0,1,…N-1（2.1）通常令2jNNeW，称为旋转因子。2.2直接计算DFT的问题及FFT思想由DFT的定义可以看出，在x[n]为复数序列的情况下，完全直接运算N点DFT需要N-1的2次方复数乘法和N（N-1）次加法。因此，对于一些相当大的N值（如1024）来说，直接计算它的DFT所作的计算量是很大的。FFT的基本思想在于，将原有的N点序列分成两个较短的序列，这些序列的DFT可以很简单的组合起来得到原序列的DFT。例如，若N为偶数，将原有的N点序列分成两个（N/2）点序列，那么计算N点DFT将只需要约[(N/2)2∙2]=N2/2次复数乘法。即比直接计算少做一半乘法。因子(N/2)2表示直接计算（N/2）点DFT所需要的乘法次数，而乘数2代表必须完成两个DFT。上述处理方法可以反复使用，即（N/2）点的DFT计算也可以化成两个（N/4）点的DFT（假定N/2为偶数），从而又少做一半的乘法。这样每一级的划分下去一直到最后就划分成两点的FFT运算的情况。2.3基2按时间抽取（DIT）的FFT算法设序列长度为2LN，L为整数（如果序列长度不满足此条件，通过在后面补零使其满足）。将长度为2LN的序列[](0,1,...,1)xnnN，先按n的奇偶分成两组：12[2][][21][]xrxrxrxr（r=0,1,…,N/2-1）（2.2）DFT化为：武汉理工大学《数字信号处理》课程设计说明书31/21/212(21)000/21/21221200/21/211/22/200[]{[]}[][2][21][][][][]NNNnkrkrkNNNnrrNNrkkrkNNNrrNNrkkrkNNNrrXkDFTxnxnWxrWxrWxrWWxrWxrWWxrW(2.3)上式中利用了旋转因子的可约性，即：2/2rkrkNNWW。又令/21/2111/222/200[][],[][]NNrkrkNNrrXkxrWXkxrW，则上式可以写成：12[][][]kNXkXkWXk(k=0,1,…,N/2-1)(2.4)可以看出，12[],[]XkXk分别为从[]Xk中取出的N/2点偶数点和奇数点序列的N/2点DFT值，所以，一个N点序列的DFT可以用两个N/2点序列的DFT组合而成。但是，从上式可以看出，这样的组合仅表示出了[]Xk前N/2点的DFT值，还需要继续利用12[],[]XkXk表示[]Xk的后半段本算法推导才完整。利用旋转因子的周期性，有：(/2)/2/2rkrkNNNWW，则后半段的DFT值表达式：/21/21()211/21/2100[][][][]2NNNrkrkNNrrNXkxrWxrWXk(2.5)22[][]2NXkXk（k=0,1,…,N/2-1）(2.6)所以后半段（k=N/2,…,N-1）的DFT值可以用前半段k值表达式获得，中间还利用到()22NNkkkNN，得到后半段的[]Xk值表达式为：12[][][]kNXkXkWXk（k=0,1,…,N/2-1）。这样，通过计算两个N/2点序列12[],[]xnxn的N/2点DFT12[],[]XkXk，可以组合得到N点序列的DFT值[]Xk，其组合过程如下图所示：1[]Xk12[][]kNXkWXk2[]XknkNW-112[][]kNXkWXk图2.1FFT形成过程武汉理工大学《数字信号处理》课程设计说明书42.4基2按频率抽取（DIF）的FFT算法设序列长度为2LN，L为整数（如果序列长度不满足此条件，通过在后面补零使其满足）。在把[]Xk按k的奇偶分组之前，把输入按n的顺序分成前后两半：(2.7)因为21NNW，则有2(1)NkkNW，所以：X[k]=∑[x[n]+(−1)kx[n+N2]]N/2−1n=0WNnk,k=0,1,…,N−1(2.8)按k的奇偶来讨论，k为