快速傅里叶变换程序设计.doc

1、 中 文 摘 要数字信号处理 (Digital Signal Processing，DSP)是一门应用十分广泛的学科。数字信号处理是指利用计算机技术，以数字形式对信号进行采集、变换、滤波、估值、增强、压缩、识别等处理，以得到符合人们需要的信号形式。数字信号处理器(Digital Signal Processing，DSP)也称为DSP芯片，是一种用于进行数字信号处理运算的微处理器，其主要功能是实时快速地实现各种数字信号处理算法及各种复杂控制算法。TMS320C2000系列DSP集微控制器和高性能DSP的特点于一身，具有强大的控制和信号处理能力，能够实现复杂的控制算法。TMS320C2000系列

2、DSP片上整合了Flash存储器、快速的A/D转换器、增强的CAN模块、事件管理器、正交编码电路接口、多通道缓冲串口等外设，此种整合使用户能够以很便宜的价格开发高性能数字控制系统。傅立叶变换是一种将信号从时域变换到频域的变换方式,是声学、语音、电信和信号处理等领域中一种重要的分析工具。离散傅里叶变换（DFT）是连续傅里叶变换在离散系统中的表现形式，但由于DFT的计算量很大，因此在很长一段时间内其应用受到很大的限制。快速傅里叶变换（FFT）是离散傅里叶变换的一种快速高效运算方法，是数字信号处理中最为重要的工具之一。FFT使DFT的运算大大化简，运算时间一般可以缩短1至2个数量级，FFT的出现大大

3、提高了DFT的运算速度，从而使DFT得到广泛的应用。本次DSP课程设计我所设计的课题为：“快速傅里叶变换程序设计” 。该课程设计题目的基本要求是：基于DSP实现快速傅里叶变换。本次课程设计是基于Code Computer Studio这一软件所设计的。采用的是SEEKDTK2812实验箱。 关键词：数字信号处理（DSP）、快速傅里叶变换（FFT）、离散傅里叶变换（DFT） 目录快速傅里叶变换程序设计 课程设计成绩评定表III中 文 摘 要V一 设计任务描述11.1 设计题目11.2 设计要求11.2.1设计目的11.2.2基本要求1二 设计思路22.1 FFT算法简介22.2 FFT算法原理2

4、2.3 快速傅立叶变换算法32.4 功能实现72.4.1位置倒码72.4.2蝶距72.4.3旋转因子72.5 FFT算法的DSP的实现方法82.6 FFT运算中应注意的问题8三 设计方框图9四 各部分程序设计及参数计算104.1 ADC采样104.2 FFT转换11五 工作过程分析135.1在CCS下调试程序步骤135.2 程序的初始化135.3 FFT计算135.4 输入信号及输出波形145.4.1 正弦波145.4.2 方波155.4.3 三角波16六 实验系统介绍176.1 DSP简介176.1.1 DSP微处理器176.1.2 DSP的开发工具176.1.3 DSP算法及芯片分类186

5、.1.4 DSP技术的应用186.2 CCS开发环境简介196.2.1 驱动程序的配置196.2.2 创建工程文件216.2.3 CCS窗口介绍及文件简介216.2.4 CCS软件仿真226.3 SEED-DTK2812实验系统236.3.1 SEED-DTK2812原理框图236.3.2实验箱整体配置246.3.3实验箱特点25小 结26致 谢27参考文献28附录1 源程序清单29附录2 程序运行图34III 快速傅里叶变换程序设计一 设计任务描述1.1 设计题目快速傅里叶变换程序设计。1.2 设计要求1.2.1设计目的1）理解FFT的算法以及利用DSP实现的方法。2）能熟练的调试程序并能观

6、察其结果。3）熟悉TMS320F2812系列DSP芯片的软件设计方法。1.2.2基本要求1）掌握DSP A/D转换器使用方法。2）研究FFT原理以及利用DSP实现的方法。3）编写A/D采样和FFT程序，调试，观察结果。二 设计思路2.1 FFT算法简介快速傅里叶变换（FFT）是一种高效实现离散傅里叶变换（DFT）的快速算法，是数字信号处理中最重要的工具之一，它在声学，语音，信号处理等领域有着广泛的应用。是将信号从时域变换到频域的一种变换形式，是信号处理领域中一种重要的分析工具。离散傅里叶变换（DFT）是连续傅里叶变换在离散系统中的表现形式。傅里叶变换分为连续傅里叶变换和离散傅里叶变换。离散傅里

7、叶变换简称DFT，是对离散信号进行傅里叶变换的方法，其运算量大、复杂度与变换点数的二次方成正比，因而不适用于进行实时信号处理。20世纪60年代由Cooley和Tukey提出了快速傅里叶变换（FFT）算法，它是快速计算DFT的一种高效方法，可以明显地降低运算量，大大地提高DFT的运算速度，从而使DFT在实际中得到了广泛的应用，已成为数字信号处理最为重要的工具之一。DSP芯片的出现使FFT的实现变得更加方便。由于多数的DSP芯片都能在单指令周期内完成乘法累加运算，而且还提供了专门的FFT指令（如实现FFT算法所必需的比特反转等），使得FFT算法在DSP芯片上实现的速度更快。本节首先简要介绍FFT算

8、法的基本原理，然后介绍FFT算法的DSP实现。2.2 FFT算法原理快速傅氏变换（FFT）是离散傅氏变换的快速算法，根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅里叶变换算法进行改进获得的。对傅氏变换的理论并没有新的发现，但是对在计算机系统或者数字系统中应用离散傅里叶变换，可以说进了一大步。设为N项的复数序列，由DFT变换，任一X(M)的计算需要N次复数乘法和N-1次复数加法，而一次复数乘法等于四次实数乘法和两次实数加法，一次复数加法等于两次实数加法，即使把一次复数乘法和一次复数加法定义成一次“运算”（四次实数乘法和四次实数加法），则求出N项复数序列的X(M)，即N点DFT变换大约需要次运算

9、。当N=1024点甚至更多的时候，需要次运算，在FFT中，利用的周期性和对称性，把一个N项序列（设N=2k，k为正整数），分为两个项的子序列，每个点DFT变换需要次运算，再N次运算把两个点的DFT变换组合成一个N点DFT变换。这样变换以后，总运算次数变成。继续上面的例子，N=1024时，总的运算次数就变成了525312次，节省了大约50%的运算量。如果将这种“一分为二”思想不断进行下去，直到分成两两一组DFT运算单元，则N点DFT变换只需要次运算，N在1024时，运算量仅有10240次，是先前直接算法的1%，点数越多，运算量节约就越大，这就是FFT的优越性。2.3 快速傅立叶变换算法FFT的基

10、本思想：将大点数的DFT分解为若干个小点数DFT组合，从而减少运算量。根据对序列分解与选取方法的不同而产生了FFT的多种算法。算法分类如图2-1所示：FFT算法基-2FFT算法基-4FFT算法混合基算法分裂基算法线性调频Z变换算法按时间抽取按频率抽取图2-1 FFT的几种算法在这次设计中，采用最基础的按时间抽取的基-2FFT算法来实现快速傅里叶变换。为了将大点数的DFT分解为小点数的DFT运算，要求序列的长度N为复合数，最常用的是的情况（M为正整数）。该情况下的变换称为基-2FFT算法。下面讨论基-2FFT情况的算法。先将序列x(n)按奇偶项分解为两组： （2-1）将DFT运算也相应分为两组:

11、 （2-3）至此，一个点DFT被分解为两个点的DFT。由式（2-3）能否将全部的点的解求出来？分析： （2-4）和只有个点，则由式（2-4）只能求出X(k)的前个点的DFT。要求出全部点的，需要找出、和的关系，其中k=0,1,2.(N/2)-1。由式子（2-4）可得化简得 （2-5）这样N点DFT可全部由下式确定出来： （2-6）上式可用一个专用的蝶形符号表示，如图2-2所示，对应一次复乘和两次复加运算。-1图2-2 蝶形运算符号通过这样的分解以后，每一个点的DFT只需要次复数乘法，两个点的DFT需要次复乘，再加上将两个点DFT合并成N点的DFT时，有次与因子相乘，一共需要次复乘。可见，通过这

12、样的分解，运算量节省了近一半。因为，仍然是偶数，因此可以对两个点的DFT分别作进一步的分解，将两个的DFT分解成两个点的DFT。例如对，可以再按其偶数部分及奇数部分进行分解： （2-7）则运算可相应分为两组：将系数统一为以N为周期，即，可得 （2-8）同样，对也可以进行类似的分解。一直分解下去，最后是2点的DFT，2点的DTF的运算也可以用蝶形符号来表示。这样，对于一个的DFT运算，最终结如图2-3图2-3蝶形图这种方法，由于每一步分解都是按输入序列在时域上的次序是属于偶数还是奇数来抽取的，故称为“时间抽取法”。分析上面的流图，一共要进行M次分解，构成了从到的M级运算过程。每一级运算都是由个蝶

13、形运算构成，因此每一级运算都需要次复乘和M次复加，则按时间抽取的M级运算后总用需要：复数乘法次数： 复数加法次数： 根据上面过程，分析FFT算法的两个特点，它们对FFT的软硬件构成产生很大的影响。原位运算：也成为同址运算，当数据输入到存储器中以后，每一级运算的结果仍然存储在原来的存储器中，直到最后输出，中间无需其它的存储器。根据运算流图分析原位运算是如何进行的。原位运算的结构可以节省存储单元，降低设备成本。变址：分析运算流图中的输入输出序列的顺序，输出按顺序，输入是“码位倒置”的顺序，见表2-1所示。自然顺序 二进制表示 码位倒置 码位倒置顺序 0 000 000 0 1 001 100 4

14、2 010 010 2 3 011 110 6 4 100 001 1 5 101 101 5 6 110 011 3 7 111 111 7 表2-1 码位倒置顺序实际运算中，直接将输入数据按码位倒置的顺序排好输入很方便，一般总是先按自然顺序输入存储单元，然后通过变址运算将自然顺序的存储换成码位倒置顺序的存储，这样就可以进行FFT的原位运算。用软件实现是通用采用雷德（Rader）算法，算出的倒序以后立即将输入数据和对换。尽管变址运算所占运算量的比例很小，但对某些 高要求的应用（尤其在实时信号处理中），也可设法用适当的电路结构直接实现变址。例如单片数字信号处理器TMS320C25就有专用于FF

15、T的二进制码变址模式。2.4 功能实现2.4.1位置倒码 当进行原位运算时，发现当运算完成后，FFT的输出X(k)按正常顺序排列在存储单元中，即按X(0)，X(1)，X(7)的顺序排列，但是这时输入x(n)却不是按自然顺序存储的，而是按x(0)，x(4)， ， x(7)的顺序存入存储单元，看起来好像是“混乱无序”的，实际上是有规律的，称之为倒位序。当用二进制表示顺序时，它正好是“位码倒置”的顺序。例如，原来的自然顺序应是x(1)的地方，现在放着x(4)，用二进制码表示这一规律时，则是在x(0 0 1)处放着x(1 0 0)，x(0 1 1) 处放着x(1 1 0)，即将自然循序的二进制码位倒置

16、过来，第一位码变成最末位码，这样倒置以后的顺序正是输入所需要的顺序，其结果与按时间抽样算法FFT流程图中的输入顺序是一致的。需要注意当进行原位运算时，输入输出序列为倒位序的关系，若不为原位运算，则这种关系不一定成立。在实际运算中，一般直接将输入数据x(n)按码位倒置的顺序排好输入很不方便，总是先按自然顺序的存储，然后进行FFT的原位计算。自然顺序二进码表示码位倒置倒位序0000000010011004201001023011110641000011510110156110011371111117表2-1 码位倒置顺序2.4.2蝶距设N=，则整个运算流图中包含L级蝶形运算，每一级则有N/2个蝶形

17、单元。蝶距等于每个蝶形单元两个输入（出）节点的序列号，即第m级蝶形单元的蝶距为：。2.4.3旋转因子由FFT算法原理过程可知，若=，则共有级蝶形运算，各级蝶形运算中旋转因子分别如下：第级的旋转因子为（=0,1，）；第-1级的旋转因子为（=0,1，）；第一级的旋转因子为（=0,1，）。由此可见， 第级蝶形运算中旋转因子为，=0，1，。2.5 FFT算法的DSP的实现方法设FFT运算的输入数据为实数，则2点实数FFT算法的实现步骤为：第一步，把2实数输入序列组合成点的复数序列。然后把该复数序列进行位倒序操作后存储在输入区。第二步，进行的FFT运算。第三步，把点FFT输出拆成2的复数序列，这2的复数

18、序列对应于2点时实数输入序列的DFT输出。第四步，结果输出及功率谱计算。2.6 FFT运算中应注意的问题为了避免可能的结果溢出，在编写程序时我们应该注意对每次蝶形运算的结果都右移一位，即除以2。为了减少FFT的运算时间和充分利用C54xDSP资源，编程时应尽可能多的采用并行指令。三 设计方框图开始程序初始化南北红送入数据南北红调入系数表南北红输入数据位码倒置南北红FFT的蝶形运算南北红是否发生 溢出？N Y归一化南北红输入数据 结束？ Y各图形输出南北红N结束四 各部分程序设计及参数计算4.1 ADC采样/*初始化系统*/InitSysCtrl();#if SAMPLELONG=1Sample

19、Long =256;#endif#if SAMPLELONG=2SampleLong =512;#endif#if SAMPLELONG=3SampleLong =1024;#endif/*关中断*/DINT;IER = 0x0000;IFR = 0x0000;/*初始化PIE中断*/InitPieCtrl();/*初始化PIE中断矢量表*/InitPieVectTable();/初始化cputimer InitCpuTimers();/*设置中断服务程序入口地址*/EALLOW;/ This is needed to write to EALLOW protected registersPi

20、eVectTable.TINT2 = &ISRTimer2;PieVectTable.ADCINT = &ad;EDIS; / This is needed to disable write to EALLOW protected registers/*开中断*/IER |= M_INT1;/ADC中断EINT; / Enable Global interrupt INTMERTM;/ Enable Global realtime interrupt DBGMadconvover=0;DINT;/*设置CPU*/ConfigCpuTimer(&CpuTimer2, 150, 22); Star

21、tCpuTimer2();/*开中断*/IER |= M_INT14;EINT;4.2 FFT转换switch(SampleLong/2) case128:fft128.ipcbptr=ipcb;fft128.init(&fft128);for(i=0;iSampleLong/2;i+)ipcbi = Ad_data1i;delay(5000);RFFT32_brev(ipcb,ipcb,FFTN128);fft128.calc(&fft128);fft128.split(&fft128);break;case256:fft256.ipcbptr=ipcb;fft256.init(&fft25

22、6);for(i=0;iSampleLong/2;i+)ipcbi = Ad_data1i; delay(5000);RFFT32_brev(ipcb,ipcb,FFTN256);fft256.calc(&fft256);fft256.split(&fft256);break;case512:fft512.ipcbptr=ipcb;fft512.init(&fft512);for(i=0;iNew（3）在Project Name框里输入工程名：(例如:1)（4）在Location框里输入或者浏览创建的文件夹。（5）在第三步的创建的文件夹里添加命令脚本2812.cmd和编辑好的.c文件（6）在c

23、cs里打开编好的.c文件，依次点击编译、连接、运行，执行File-Load Program加载程序。加载过程是将上述构建成功，生成的可执行文件加载到目标板，目标板可以是软件仿真环境，也可以是硬件目标板。默认情况下，CCS集成开发环境将会在你的工程路径下创建一个Debug子目录，把生成的.out文件放在里面。点击Open加载。6.2.3 CCS窗口介绍及文件简介CCS窗口介绍如图6-4所示图6-4CCS窗口使用CCS常遇见的文件简介：program,c：C程序源文件program.asm：汇编程序源文件filename.h：C程序的头文件，包含DSP/BIOSAPI模块的头文件filename.

24、lib：库文件project.cmd：连接命令文件program.obj：由源文件编译或汇编而得的目标文件program.out：经完整的编译、汇编以及连接都生成可执行文件program.map：经完整的编译、汇编以及连接后生成空间分配文件project.pjt：存储环境设置信息的工作区文件programcfg.cmd：连接器命令文件programcfg.h54：汇编头文件programcfg.s54：汇编源文件6.2.4 CCS软件仿真CCS软件仿真如图6-5所示图6-5CCS软件仿真6.3 SEED-DTK2812实验系统 为了更好地配合学校的理论教学，达到理论与实践完美的结合，合众达公司

25、总结了 10 多年在 DSP 领域中的开发与应用经验，推出了双 DSP 教学系统 SEED-DTK 教学实验箱系列产品。它设计新颖、独特，为师生提供了一个完整的教学实验平台，为学生加速学习与系统掌握DSP 的开发与应用提供了强有力的手段。SEED-DTK 教学实验箱采用模块化设计理念，涵盖了 TI 所有的主流 DSP 系列：C2000、C3X、C5000 和 C6000 系列。其中 SEED-DTK实验箱中的主控板 SEED-DECxxxx 采用统一的系统结构、模块结构、机械结构和标准的总线接口以及相同的物理尺寸，实验箱上的主控板可以替换为不同系列 SEED-DECxxxx，以适应不同院系在同

26、一实验箱上开展不同的实验内容，大大节省了校方的设备经费。SEED-DTK（DSP Teaching Kit）是一套可以满足大学本科、研究生和教师科研工作的综合实验设备。SEED-DTK 是合众达在总结以往产品的基础上，以独特的多 DSP结构、强大的 DSP 主板功能、丰富的外围实验电路、精心设计的实验程序、精湛的产品工艺形成的高性能产品。6.3.1 SEED-DTK2812原理框图SEED-DTK2812原理框图如图6-6所示图6-6SEED-DTK2812原理框图6.3.2实验箱整体配置SEED-DTK2812 实验箱由以下几部分构成： 1. SEED-DEC2812 实验箱 DSP 基本系

27、统 u 高性能 DSP：TMS320F2812，主频 150MHz u 外扩 SRAM，最大容量为 512K16 位，基本配置为 256K16 位 u 512 字节的 EEPROM+RTC 实时时钟 u 16 路 AD 输入 u 4 路 DA 输出 u 12 路 PWM 输出，6 路捕捉输入 u 双路 URAT 接口，接口标准为 RS232RS422RS485，可配置 u 符合 USB2.0 标准的高速 Host 端接口 u 1 路 CAN 总线接口，符合 CAN2.0 协议 2. SEED-Mboard 实验箱人机接口模块 u 处理器为 TMS320C5402 u SRAM：64K16-位（

28、可扩展至 256K16 位） u Flash：256K16-位（用于存放二级标准汉字库及驻留实验程序） u 提供手动复位 u 1 路 RS232 接口 u 2 路 8 位 0+5.5V 输出 D/A u 17 键薄膜键盘 u 240*128 大屏幕液晶显示 u 交通灯演示模块6.3.3实验箱特点模块化的产品结构： SEED-DEC2812 实验箱的 DSP 基本系统 可替换其它系列的 DSP SEED-DECxxxx 产品 SEED-Mboard 人机接口模块、处理器为 TMS320C5402 DSP SEED-DTK_PWMDRV 电机驱动模块 实验箱特点： u 独具匠心设计的双 DSP 结

29、构，可以完成 DSP 间的通讯实验； u 各模块丰富的资源，最大化满足实验要求； u 全数字化实验过程，包括高精度信号发生器； u 丰富多彩的实验，可以满足多种专业的教学要求； u 内容详实的实验手册和实验报告； u 公开的底层函数，提供实验可扩展性； u 精湛的产品设计和加工工艺，体现出的专业产品制造。 小 结 为期一周的DSP课程设计已经结束，可以这样说在这次DSP课程设计中我的收获非常的丰富。 通过本学期对DSP控制器原理与应用这一门课程的学习，我学会了许多关于DSP的知识，当然这些均是理论知识。而这些理论知识在这次的课程设计中起到了关键性作用，这些知识为本次课程设计的进行做好了充分的理

30、论准备。在课程设计的第一天，老师向我们认真的讲解了每一个设计题目所要实现的功能及大体的设计方向。本次课程设计采用分组进行的方式，但我们只是做同一个课题，老师要求我们每一个人都要亲自调试完成一个程序。刚开始时我还有些不理解这是为什么，但当我开始正式进行课程设计时我就明白这其中的意义了。几个人一组让我们有了互相学习讨论的伙伴，而自己调试自己的程序又提高了我们自己的独立思考与动手的能力。在今后的课程设计中，我们每个人都认真的研究自己的课题，遇到不会的问题我们先在小组中讨论，小组成员间认真积极的学习态度，深深感染了我，使我深刻的体会到了团队的力量，也被这种氛围深深的感染，更加积极投身于工作之中。然而人多并不代表一定能成功，我们还是遇到了一些我们无法解决的问题，每到此时我们都会去请教老师，而老师对于我们的每一次提问都是很耐心细致的讲解，这样我们学到了许许多多在课堂上学不到的东西，也培养了我们遇问题先通过查找资料、讨论等方式自我解决的良好习惯。 开始刚