武汉理工大学8点基于DIFFFT

1、武汉理工大学8点基于DIFFFT课程设计任务书学生姓名：李嘉辛专业班级:电信1206指导教师：黄朝兵工作单位:信息工程学院题 目：8点基于DIF的FFT的实现初始条件：具备Mat lab编程能力；熟悉基于DIF的FFT的实现原理；提供编程所需要的计算机-台要求完成的主要任务：（包括课程设计工作量及其技术要求，以及说明书 撰写等具体要求）1、独立编写一个8点的基于DIF的FFT实现程序，不能使用mat lab自 带的FFT实现函数2、并调用该函数实现16点的FFT运算，用mat lab自带函数对运行结 果结果进行验证3、完成符合学校要求的设计说明书时间安排：一周，其屮3天程序设计，2天程序调试指

2、导教师签名：年 月 日系主任（或责任教师）签名:目录摘要11概述11.1数字信号处理定义11.2数字信号处理的特点及实现方法22理论分析22. 1 DFT的定义22. 2直接计算DFT的问题及FFT思想22. 3基2按时间抽取（DIT）的FFT算法32.4基2按频率抽取（DIF）的FFT算法42. 5按频率抽取的FFT的特点62.5.1原位运算62.5.2蝶形运算两节点之间的“距离” 72.5.3旋转因子的变化规律73程序设计73. 1变址83.2 L级递推计算84结果及分析105心得体会13参考文献14武汉理工大学8点基于DIFFFT摘要快速傅里叶变换(FFT)是离散傅里叶变换(DFT)的快

3、速算法，FFT 算法通过利用旋转因子的性质,将一个大点数DFT化成几个小点数DFT, 就可以大大减少运算量oDIF-FFT是利用频率抽选的FFT算法，在Mat lab 中可以通过三重循环语句实现。关键词：FFT,蝶形运算，倒序排列1概述1. 1数字信号处理定义数字信号是用数字序列表示的信号，数字信号处理就是通过计算机 或专用处理设备，用数值计算等数字方式对数字序列进行各种处理，将 数字信号变换成符合要求的某种形式。数字信号处理主要包括数字滤波 和数字频谱分析两大部分。例如，对数字信号进行滤波，限制其频带或 滤除噪声和干扰，以提取和增强信号的有用分量；对信号进行频谱分析 或功率分析，了解信号的频

4、谱组成，以对信号进行识别。当然，凡是用 数字方式对信号进行滤波，变换，增强，压缩，估计和识别等都是数字 信号处理的研究范畴。数字信号处理在理论上所涉及的范围及其广泛。数字领域中的微积 分，概率统计，随机过程，高等代数，数值分析，复变函数和各种变换 (如傅里叶变换，Z变换，离散傅里叶变换，小波变换等)都是它的基 本工具，网络理论，信号及系统等则是它的理论基础。在科学发展上， 数字信号处理又和最优控制，通信理论等紧密相连，目前已成为人工智 能，模式识别，神经网络等新兴学科的重要理论基础，其实现技术又和 计算机科学和微电子技术密不可分。因此，数字信号处理是把经典的理 论基础体系作为自身的理论基础，同

5、时又使自己成为一系列新兴学科的 理论基础。1. 2数字信号处理的特点及实现方法及模拟信号处理相比，数字信号处理具有高精度、高稳定性、灵活性 好、易于大规模集成等显著的优点。数字信号处理的主要研究对象是数字信号，且采用数值运算的方法达 到处理的目的。数字信号处理的实现方法基本上可以分为软件实现方法、 硬件实现方法和软硬件想结合的实现方法。数字信号处理的理论、算法 和实现方法三者是密不可分的。2理论分析2. 1DFT的定义对于有限长离散数字信号xn,0 n N-1,其离散谱Xk可以 由离散付氏变换(DFT)求得。DFT的定义为：,k=0, 1, N-1(2. 1)通常令汽称为旋转因子。2. 2直接

6、计算DFT的问题及FFT思想由DFT的定义可以看出，在xn为复数序列的情况下，完全直接运 算N点DFT需要N-1的2次方复数乘法和N (N-1)次加法。因此，对于 一些相当大的N值(如1024)来说，直接计算它的DFT所作的计算量是 很大的。FFT的基本思想在于，将原有的N点序列分成两个较短的序列，这些# / 179 / 17武汉理工大学8点基于DIFFFT序列的DFT可以很简单的组合起来得到原序列的DFT。例如，若N为偶 数，将原有的N点序列分成两个(N/2)点序列，那么计算N点DFT将只 需要约(N/2)22二N?/2次复数乘法。即比直接计算少做一半乘法。因子 (N/b表示直接计算(N/2

7、)点DFT所需要的乘法次数，而乘数2代表必 须完成两个DFT。上述处理方法可以反复使用，即(N/2)点的DFT计算 也可以化成两个(N/4)点的DFT (假定N/2为偶数)，从而又少做一半 的乘法。这样每一级的划分下去一直到最后就划分成两点的FFT运算的 情况。2. 3基2按时间抽取(DIT)的FFT算法设序列长度为N = 2丄，L为整数(如果序列长度不满足此条件，通过 在后面补零使其满足)。将长度为N = 2啲序列血(“ =0,1,.,2-1),先按n的奇偶分成两组：(r=0, 1,，N/2-1)(2.2)DFT化为：Af/2-1Af/2-1X幻二 DFTx川川 x2r + lWl)kw=0

8、r=0r=0N/2-1N/2-1=工rW +叭工吃血尸r=0r=0Af/2-1A72-1=工W陀2+昭工费卩哺2i(2. 3)上式屮利用了旋转因子的可约性，即：比严=叱爲。又令则上式可以写成:A72-1AT/2-1乙幻= x.rWX2k= 花刃昭2，r-0r-0xk = xlk+wx2k(k=0, 1,，N/2-1) (2. 4)可以看出，xixk分别为从x幻中取出的N/2点偶数点和奇数点序 列的N/2点DFT值，所以，一个N点序列的DFT可以用两个N/2点序列 的DFT组合而成。但是，从上式可以看出，这样的组合仅表示出了 X幻前3 / 173 / 17武汉理工大学8点基于DIFFFTN/2点

9、的DFT值，还需要继续利用兀幻,兀幻表示X幻的后半段本算法推导才完整。利用旋转因子的周期性，有：叱2=叱黑也），则后半段的DFT值表达式:NAT/2-川上+灯 N引于+幻=s 皿咛 =E西叱2 = X|幻(2.5)厶r-0r-0(k二0, 1，: N/2T) (2. 6)所以后半段（k二N/2,N-1）的DFT值可以用前半段k值表达式获得， 中间还利用到wfi+k，=wwk =-wk ,得到后半段的X幻值表达式为： Xk = Xk-WX2k （k=0, 1,，N/2T）。这样，通过计算两个N/2点序列初,*的N/2点DFTX|R,X2幻,可 以组合得到N点序列的DFT值X幻,其组合过程如下图所

10、示：图2. 1 FFT形成过程9 / 179 / 172. 4基2按频率抽取（DIF）的FFT算法设序列长度为N =严，L为整数（如果序列长度不满足此条件，通过 在后面补零使其满足）。在把X幻按k的奇偶分组之前，把输入按n的顺序分成前后两半：V-lr/2-lT_1= DFTxn = 5： E 刈町卩十 Z 刈刃？2=0m=O皆 卜 Q N （n-）i =I 址可卩；+ 2 4-Fy 2 n=O=0厶N/2-1N-k=Z -4xH + -7 W,k = OA,N -1(2.7)n=O丄NNk因为w =-1,则有wj =（-i）S所以:Xk=Sno_1xn + （-l）kxn +k = 0,1，,

11、N-l（2. 8）按k的奇偶来讨论，k为偶数时：X2r=So_1xn + xn + 弓W砰,k = 0,1,.,N 1（2. 9）k为奇数时：X2r+l=So_1xM-xn + WJ时，就不需要再变址了，否则变址两次等于不变。其屮 本程序使用的“反向进位加法”。也可用bin2dec函数可以实现倒以位序。3. 2L级递推计算整个L级递推过程由三个嵌套循环构成。外层的一个循环控制L (L二 1隅屮)级的顺序运算；内层的两个循环控制同一级(M相同)各蝶形结 的运算，其屮最内层循环控制同一种(即叭屮的r相同)蝶形结的运算。 其循环变量为I, I用来控制同一种蝶形结运算。其步进值为蝶形结的间 距值LE二

12、2,同一种蝶形结中参加运算的两节点的间距为LE1二点。 第二层循环，其循环变量J用来控制计算不同种(系数不同)的碟形结， J的步进值为1。也可以看出，最内层循环完成每级的蝶形结运算，第二 层循环则完成系数W；的运算。最外层循环，用循环变量M来控制运算的 级数，M为1到L,步进值为1,当M改变时，则LEI, LE和系数U都会 改变。MATLAB实现的代码： function Xk二DIF_FFT(xn, N);%实现对输入序列的DIF-FFT的基2算法，点数小于等于2的次幕 n=nextpow2 (length (xn) ;%取最小的满足2次幕的nN二2n;if length(xn)Nxn二xn

13、, zeros(1, N-length(xn);end%蝶形运算算法M二log2(N) ;%M=3 或 4%第一层循环分解步骤for m=0:M-lNum_Group=2 m;%每一次分解屮组的个数I n t V_Gr oup二N/ 2 F;%每一次分解中组之间的间距IntV_Unit二N/2八（m+l） ; %每一组运算单元的间距Count=IntV_Unit-l;%运算单元循环次数第三次循环次数Wn=exp(-j*2*pi/IntV_Group) :%旋转因子%第二层循环组的循环for g=l:Num_Groupdxl二(gl)*IntV_Group;的偏移量dx2二(gl)*IntV_G

14、roup+IntV_Unit;的偏移量%第三层循环组内运算的循环for r=0:Countk=r+l;标%第g组屮运算量1%第g组屮运算量2% “组内”序列的下xn(k+dxl)=b+xn(k+dx2);xn (k+dx2)二bxn(k+dx2)*Wnr;%第皿级，第g组的蝶形运算式1%第皿级，第g组的蝶形运算式2b=xn(k+dxl);end end end%序列排序开始%码位倒置十进制转二%倒序后二进制转十进制nl=f liplr (dec2bin (0:Nl);进制并倒序n2二bin2dec(nl);%倒序循环输出for i=l:N武汉理工大学8点基于DIFFFTXk (i) =xn (

15、n2 (i) +1);end4结果及分析编写主函数，在主函数中输入一个16点的序列分别调用自己编写的 FFT函数，和MATLAB本身系统的FFT函数并比较两个结果是否相等，以 判断自己编写的FFT程序是否正确xn=O:15;m=l:16； N二16xl二DIF_FFT(xn, N)x2二fft(xn)x3二abs(xl);x4=abs(x2);x5二angle(xl);x6=angle (x2):figure (，NumberTitle，, * off，, Name,电信 1206 李嘉辛);subpl ot (3, 1, 1)stem(m, xn) ; title (输入的离散序列)subp

16、lot (3, 1, 2)stem(m, x3) ; title (经过DIF_FFT后得到的频谱的幅度)subplot (3, 1, 3)stem(m, x5) ; title (经过DIF_FFT后得到的频谱的相位)figure (* NumberTitle，, J off，, Name,电信 1206 李嘉辛); subpl ot (3, 1, 1)stem(m, xn) ; title (输入的离散序列)subplot (3, 1, 2)stem(m, x4); titleC经过库函数fft后得到的频谱的幅度)subplot (3, 1, 3)stem(m, x6); titleC经过

17、库函数fft后得到的频谱的相位)图4. 1 DIF-FFT结果图4. 2库函数FFT结果通过观察比较，得到的序列各点的值以及直观的通过图形，可以得到 自己编写的DIF.FFT函数实现对序列进行FFT变换得到的结果及库函数 FFT得到的结果是一样的。说明DIF_FFT子程序是正确的。从图中也可 以看出有限长序列通过FFT后得到的频域为离散的。从理论讲，有限长 序列经过离散傅里叶变换后，得到的频谱为离散的，从而也说明了 FFT 是DFT的优化方法，也属于DFT。这个程序可以实现基2-FFT,但是如果想在运行时直接输入要变换的 点数就不行，必须在调用FFT函数前现将要算的序列定义好，这是这个 程序的

18、不足之处。但是该程序可以计算不是2的整数次幕的序列。所以 在主程序中，输入序列必须给出才能进行FFT变换。当使用编写的程序进行16点的DIF-FFT计算时结果如下：xn二1 2 3 4 5 6 7 8;N二8;DIF_FFT(xn, N) xn二0:15;N二16;DIF_FFT(xn,N)ans 二1. 0e+02 *Columns 1 through 41. 2000 + 0. OOOOi -0. 0800 + 0. 4022i-0. 0800 + 0. 1931i-0. 0800 + 0. 1197i# / 1711 / 17武汉理工大学8点基于DIFFFTColumns 5 throu

19、gh 8-0.0800 + 0.0800i-0.0800 + 0.0535i-0. 0800 + 0.0331i-0. 0800 + 0. 0159iColumns 9 through 12-0.0800 + 0.OOOOi -0. 0800 - 0.0159i-0.0800 - 0.0331i-0. 0800 - 0. 0535iColumns 13 through 16-0. 0800 - 0. 0800i-0. 0800 - 0. U97i -0. 0800 - 0. 1931i-0. 0800 - 0. 4022i当调用mat lab自带的FFT程序进行相同的16点的FFT计算时结果如

20、下: xn二0:15;fft(xn) ans 二1. 0e+02 *Columns 1 through 41. 2000 + 0. OOOOi -0. 0800 + 0. 4022i-0. 0800 + 0. 1197iColumns 5 through 8-0.0800 + 0.0800i-0. 0800 + 0.0535i-0. 0800 + 0. 0159iColumns 9 through 12-0. 0800 + 0. OOOOi -0. 0800 - 0. 0159i-0. 0800 - 0. 0535iColumns 13 through 16-0.0800 - 0.0800i-0. 0800 - 0.1197i-0. 0800 - 0. 4022i-0.0800 + 0. 1931i-0.0800 + 0.0331i-0.0800 - 0.0331i-0.0800 - 0. 19311两者结果相同，故编写的程序正确。5心得体会通过做这次程序设计，我对MATLAB编程有了进一步的掌握，对数字 信号处理在MATLAB中的实现有了