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

[实验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)h(n)=x(n)*h(n)。再利用DFT的圆周卷积性质 x(n)h(n)=IDFT{X(k)H(k)} 就可以利用FFT计算两个有限长序列的线性卷积。 （五）分段卷积 直接利用DFT计算的缺点是：(1) 信号要全部输入后才能进行计算，延迟太多；(2) 内存要求大；(3) 算法效率不高。解决问题方法是采用分段卷积，分段卷积可采用重叠相加法和重叠保留法来实现。 1. 重叠相加（overlap add） 将长序列x[k] 分为若干段长度为L的序列 其中 记 ，那么， y0[k]的非零范围为，y1[k-L]的非零范围为。序列y0[k]、y1[k]的重叠部分为，重叠的点数L+M-2-L+1=M-1。依次将相邻两段的M-1个重叠点相加，即得到最终的线性卷积结果。 2.重叠保留法(overlap save) 方法： (1) 将x[n]长序列分段，每段长度为L； (2) 各段序列xn[k]与 M点短序列h[k]循环卷积； (3) 从各段循环卷积中提取线性卷积结果。 因 yn[k]=xn [k] L h[k] 前M-1个点不是线性卷积的点，故分段时每段与其前一段有M-1个点重叠。 记yn[k] =xn [k]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.3 CCS的使用 中的介绍进行实验操作） 1.　在CCS环境中新建本实验的工程； 2. 将相关代码文件添加工程中； 3.编译并重建 .out 输出文件，然后通过仿真器把执行代码(.out的文