实验二(快速傅里叶变换)实验指导.doc

实验二(快速傅里叶变换)实验指导————————————————————————————————作者：————————————————————————————————日期：个人收集整理勿做商业用途个人收集整理勿做商业用途--个人收集整理勿做商业用途[实验2]快速傅里叶变换（FFT)实现一、实验目的1、掌握FFT算法和卷积运算的基本原理；2、掌握用C语言编写DSP程序的方法；3、了解利用FFT算法在数字信号处理中的应用。二、实验设备1。一台装有CCS软件的计算机；2.DSP实验箱的TMS320C5410主控板；3.DSP硬件仿真器。三、实验原理（一）快速傅里叶变换傅里叶变换是一种将信号从时域变换到频域的变换形式，是信号处理的重要分析工具。离散傅里叶变换（DFT）是傅里叶变换在离散系统中的表示形式。但是DFT的计算量非常大，FFT就是DFT的一种快速算法，FFT将DFT的N2步运算减少至（N/2)log2N步.离散信号x（n）的傅里叶变换可以表示为，式中的WN称为蝶形因子，利用它的对称性和周期性可以减少运算量。一般而言,FFT算法分为时间抽取（DIT）和频率抽取(DIF）两大类。两者的区别是蝶形因子出现的位置不同,前者中蝶形因子出现在输入端,后者中出现在输出端。本实验以时间抽取方法为例。时间抽取FFT是将N点输入序列x(n）按照偶数项和奇数项分解为偶序列和奇序列。偶序列为:x（0)，x（2),x（4）,…，x（N—2)；奇序列为：x(1),x（3）,x(5）,…,x（N-1)。这样x(n)的N点DFT可写成:考虑到WN的性质,即因此有：或者写成：由于X1（k)与X2(k)的周期为N/2，并且利用WN的对称性和周期性，即:可得:对X1(k)与X2(k)继续以同样的方式分解下去,就可以使一个N点的DFT最终用一组2点的DFT来计算。在基数为2的FFT中，总共有log2(N）级运算,每级中有N/2个2点FFT蝶形运算.单个蝶形运算示意图如下：以N＝8为例，时间抽取FFT的信号流图如下：从上图可以看出，输出序列是按自然顺序排列的,而输入序列的顺序则是“比特反转"方式排列的。也就是说，将序号用二进制表示，然后将二进制数以相反方向排列，再以这个数作为序号。如011变成110，那么第3个输入值和第六个输入值就要交换位置了。一种比较常用有效的方法就是雷德算法。（二)卷积运算卷积是数字信号处理中经常用到的运算。其基本的表达式为：编写实现程序时需要注意两点：(1）序列数组长度的分配，尤其是输出数组y(n)要有足够的长度；（2）循环体中变量的位置，即n和m的关系。（三）IDFT的FFT实现IDFT与DFT的关系为即那么直接调用FFT子程序计算IDFT的方法是:（四）线性卷积的FFT实现当有限长序列x（n)与h(n)的圆周卷积长度L≥N+M时,其中N、M分别为x（n)和h（n）的长度，L点的圆周卷积能够代表它们的线性卷积,即x(n）eq\o\ac(○，L）h(n）=x（n)＊h(n)。再利用DFT的圆周卷积性质x（n)eq\o\ac(○，L)h（n)=IDFT{X（k)H(k)}就可以利用FFT计算两个有限长序列的线性卷积.（五）分段卷积直接利用DFT计算的缺点是：(1）信号要全部输入后才能进行计算，延迟太多；(2）内存要求大；(3)算法效率不高。解决问题方法是采用分段卷积，分段卷积可采用重叠相加法和重叠保留法来实现。1。重叠相加（overlapadd)将长序列x［k]分为若干段长度为L的序列其中记，那么，y0［k]的非零范围为，y1[k-L］的非零范围为。序列y0［k］、y1[k]的重叠部分为,重叠的点数L+M-2-L+1=M—1。依次将相邻两段的M—1个重叠点相加，即得到最终的线性卷积结果。2.重叠保留法（overlapsave）方法：（1)将x[n］长序列分段，每段长度为L；（2)各段序列xn［k]与M点短序列h［k]循环卷积；(3）从各段循环卷积中提取线性卷积结果。因yn[k]=xn[k]Lh［k]前M-1个点不是线性卷积的点，故分段时每段与其前一段有M—1个点重叠。记yn[k］=xn[k]eq\o\ac（○，L）h［k］，y0［k]中的［M-1,L—1]点对应于线性卷积x［k]＊h[k]中的[0，L-M］点，y1[k]中的［M-1,L—1］点对应于线性卷积x［k]*h［k]中的[L-(M-1),2L—M—（M—1)］点。依次处理即得到最终的线性卷积结果.四、实验步骤（以实验1。1为例，参照§2。3CCS的使用中的介绍进行实验操作)1.在CCS环境中新建本实验的工程；2.将相关代码文件添加工程中；3。编译并重建。out输出文件,然后通过仿真器把执行代码（.out的文件)下载到DSP