快速傅里叶变换(含详细实验过程分析)

物理与电子信息学院数信号处理实验指导书-1-[实验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)的傅里叶变换可以表示为10][)(NNnkNWnxkX，NjNeW/2式中的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可写成：12/0)12(12/02122)(NnknNNnnkNWnxWnxkX考虑到WN的性质，即2/)2//(22/)2(2][NNjNjNWeeW因此有：12/02/12/02/122)(NnnkNkNNnnkNWnxWWnxkX或者写成：12()kNXkXkWXk由于X1(k)与X2(k)的周期为N/2，并且利用WN的对称性和周期性，即：物理与电子信息学院数信号处理实验指导书-2-kNNkNWW2/可得：12(/2)kNXkNXkWXk对X1(k)与X2(k)继续以同样的方式分解下去，就可以使一个N点的DFT最终用一组2点的DFT来计算。在基数为2的FFT中，总共有log2(N)级运算，每级中有N/2个2点FFT蝶形运算。单个蝶形运算示意图如下：以N＝8为例，时间抽取FFT的信号流图如下：从上图可以看出，输出序列是按自然顺序排列的，而输入序列的顺序则是“比特反转”方式排列的。也就是说，将序号用二进制表示，然后将二进制数以相反方向排列，再以这个数作为序号。如011变成110，那么第3个输入值和第六个输入值就要交换位置了。一种比较常用有效的方法就是雷德算法。（二）卷积运算卷积是数字信号处理中经常用到的运算。其基本的表达式为：nmmnxmhny0编写实现程序时需要注意两点：（1）序列数组长度的分配，尤其是输出数组y(n)要有足够的长度；（2）循环体中变量的位置，即n和m的关系。（三）IDFT的FFT实现IDFT与DFT的关系为1***01()[()]()NknNkxnIDFTXkXkWN即物理与电子信息学院数信号处理实验指导书-3-**1()[()]xnDFTXkN那么直接调用FFT子程序计算IDFT的方法是：共轭FFT共轭乘1/N()Xk*()Xk()xn共轭FFT共轭乘1/N()Xk*()Xk()xn（四）线性卷积的FFT实现当有限长序列x(n)与h(n)的圆周卷积长度L≥N+M时，其中N、M分别为x(n)和h(n)的长度，L点的圆周卷积能够代表它们的线性卷积，即x(n)○Lh(n)=x(n)*h(n)。再利用DFT的圆周卷积性质x(n)○Lh(n)=IDFT{X(k)H(k)}就可以利用FFT计算两个有限长序列的线性卷积。补L-N个零x(n)L点DFT补L-M个零h(n)L点DFTL点IDFTy(n)=x(n)*h(n)补L-N个零x(n)L点DFT补L-M个零h(n)L点DFTL点IDFTy(n)=x(n)*h(n)（五）分段卷积直接利用DFT计算的缺点是：(1)信号要全部输入后才能进行计算，延迟太多；(2)内存要求大；(3)算法效率不高。解决问题方法是采用分段卷积，分段卷积可采用重叠相加法和重叠保留法来实现。1.重叠相加（overlapadd）将长序列x[k]分为若干段长度为L的序列][][0nLkxkxnn其中010][][其它LknLkxkxn记[][][]nnykxkhk，那么，][][][][0khnLkxkhkxnn][0nLkynny0[k]的非零范围为20MLk，y1[k-L]的非零范围为22MLkL。序列y0[k]、y1[k]的重叠部分为2MLkL，重叠的点数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个点重叠。)]1([][MLnkxkxn物理与电子信息学院数信号处理实验指导书-4-记yn[k]=xn[k]○Lh[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芯片中；4.运行程序；5.选择view-graph-time/frequency…。设置对话框中的参数:其中“StartAddress”设为“x_re”，“Acquisitionbuffersize”和“DisplayDatasize”都设为“64”，并且把“DSPDataType”设为“32-bitfloatingpoint”（如图），设置好后观察输入信号序列的波形（单边指数函数，如图）；物理与电子信息学院数信号处理实验指导书-5-同样方法观察经DFT变换后的输出序列“y_re”的波形，“StartAddress”改为“y_re”，其余参数不变（如图）；5．在Watch窗口中添加i,j,k,m,n,a,b,c等变量，在Debug菜单中先“Restart”然后“Gomain”，单步运行程序，跟踪FFT算法的过程；（可以跳过程序开始部分对各个数组的赋值代码，方法是在雷德算法的第一行代码前设置断点，然后先单击运行，待程序停在该断点后再单步执行后面的代码，见下图。）物理与电子信息学院数信号处理实验指导书-6-第一章实验平台说明本实验箱以TI公司的TMS320C5410（可选配TMS320C5416）和TMS320LF2407两种DSP芯片为中心，附加开发了多个功能模块，可以使实验者方便有效地完成各种常用的DSP开发实验。TMS320C5410是TI公司54系列DSP芯片中相当优秀的一个型号，除了有强大的运算能力外，还集成了丰富的片内资源。基于该芯片的出色性能，它在各种DSP应用场合中发挥着重要作用。本实验箱就提供了这样一个平台，使实验者能在最短的时间内了解并掌握该DSP芯片的基本开发技术。TMS320C5416是TI公司54系列DSP芯片中另一款优秀的型号，片内资源比5410丰富，HPI(主机接口)提供16BIT模式，外设与5410相近。实验者可以在5410主控板(或5416主控板)上进行各种指令实验和算法实验。把5410主控板(或5416主控板)插接在实验箱主电路板上的接口后，实验者就可以借助已设计好的外部电路进行USB接口、A/D与D/A转换等实验。本实验箱的USB模块主芯片采用功能强大的PHILIPSISP1362芯片，它支持USB2.0和最新的OTG(onTheGo点对点通信）协议，因此实验者可以充分学习到最先进的USB技术。A/D与D/A转换是传统的实验内容，本实验箱配置了两个A/D与D/A模块，它们有不同的性能和特点，适合不同的应用场合。把5410(或5416)与A/D与D/A模块配合起来，实验者甚至可以进行声音文件的MP3编解码实验。本实验箱的另一块主控板采用TMS320LF2407DSP芯片，这也是一个应用非常广泛的型号。配合实验箱主电路板上的各个模块，实验者可以进行通用异步串行口（UART）的实验，电机控制实验，以太网卡实验，液晶显示屏实验，数码管控制实验，信号灯控制实验和键盘扫描实验。另外实验箱上还有一个信号发生模块可供实验。除了已设计好的实验之外，实验者还可以发挥创造性，充分利用实验箱的资源进行其它实验。物理与电子信息学院数信号处理实验指导书-7-§1.1系统总览一、实验箱资源分布本实验箱采用模块化设计，直接与实验相关的，一共有13个模块，另有负责总线控制的CPLD模块和一个负责为各个部分供电的电源模块。每一个模块都有独立的电源开关控制。实验系统中有三个模块是采用外插形式的，在实验箱主电路板上预留了插槽，包括5410主控板(或5416主控板)，2407主控板以及电机控制模块。而其余各模块都设计在主电路板上。整个实验箱的资源分布如下图。(图1-1-1)实验箱整体说明图（1）TMS320C5410主控板(或5416主控板)位置（外插）（2）TMS320LF2407主控板位置（外插）（3）CPLD模块(复杂可编程逻辑器件)（4）A/D与D/A转换模块一（普通语音数模转换）（5）A/D与D/A转换模块二（高精度音频）物理与电子信息学院数信号处理实验指导书-8-（6）信号发生模块（7）USB2.0OTG接口模块(USB2.0点对点接口通信模块)（8）UART接口模块(通用异步收发报机接口模块)（9）以太网卡模块（10）电机控制模块插槽（11）4×4键盘模块（12）液晶显示屏模块（13）数码管模块（14）信号灯模块（15）电源模块（16）双声道扬声器模块DSPII+型模块及各部分控制图物理与电子信息学院数信号处理实验指导书-9-§1.2使用方法1.电源本实验箱内部自带变压器，使用时不需另配低压电源，可直接用普通三相插头接入220V电源。接上电源后，由电源模块输出±12V，5V，3.3V和2.5V，分别送至实验箱的各个模块。另外为方便单独使用，两个主控板上都设有独立的电源输入端口，可以接入5V的直流电源。2.仿真器接口在做实验时，需要一个DSP仿真器，把在计算机上编译并生成的执行代码下载到5410或2407芯片上。仿真器有两端接口，其中一端与计算机的并行口或USB口相连，这取决于仿真器的类型；另一端与DSP芯片的JTAG接口相连，这是一个14针的接口，在两块主控板上都可以找到。仿真器连接好后才能对主控板上的DSP芯片进行读写控制。3.外插模块的使用本实验箱有三个模块单独成板，以外插形式与主电路板连接。其中两个DSP主控板在主电路板上留有专门的位置（请见资源分布图），使用时把主控板上的接口对准主电路板上的相应插槽插牢即可。在做电机控制实验时，应先把电机控制模块的小电路板架在以太网卡模块的位置上，插好四个支脚，然后通过连接线把电机小电路板上的接口与主电路板上的电机模块插槽（请见资源分布图中的标号“10”）相连。4.计算机的配置DSP实验中的代码编写，下载仿真和程序调试都必须在计算机上完成。计算机上需要安装DSP集成开发环境软件CCS（推荐使用2.0版本）。计算机应具备最少32M内存，100M硬盘空间和奔腾处理器，显示器分辨率不能低于800*600。另外，部分模块的实验还要求计算机配有标准的USB接口，DB9串行接口