快速傅里叶变换程序设计

1、 1.设计主要内容及要求；1）掌握DSP A/D转换器使用方法。2）研究FFT原理以及利用DSP实现的方法。3）编写A/D采样和FFT程序，调试，观察结果。2.对设计论文撰写内容、格式、字数的要求；（1）.课程设计论文是体现和总结课程设计成果的载体，一般不应少于3000字。（2）.学生应撰写的内容为：中文摘要和关键词、目录、正文、参考文献等。课程设计论文的结构及各部分内容要求可参照沈阳工程学院毕业设计（论文）撰写规范执行。应做到文理通顺，内容正确完整，书写工整，装订整齐。（3）.论文要求打印，打印时按沈阳工程学院毕业设计（论文）撰写规范的要求进行打印。（4）. 课程设计论文装订顺序为：封面、任

2、务书、成绩评审意见表、中文摘要和关键词、目录、正文、参考文献。3.时间进度安排；顺序阶段日期计 划 完 成 内 容备注1月 日教师讲解题目，学生查阅相关资料2月 日进行方案论证，确定程序流程，计算参数3 月 日编写程序4 月 日调试程序5 月 日撰写论文，程序验收III 一 设计任务描述1.1 设计题目快速傅里叶变换程序设计。1.2 设计要求1.2.1设计目的1）理解FFT的算法以及利用DSP实现的方法。2）能熟练的调试程序并能观察其结果。3）熟悉TMS320F2812系列DSP芯片的软件设计方法。1.2.2基本要求1）掌握DSP A/D转换器使用方法。2）研究FFT原理以及利用DSP实现的方

3、法。3）编写A/D采样和FFT程序，调试，观察结果。二 设计思路2.1 FFT算法简介快速傅里叶变换（FFT）是一种高效实现离散傅里叶变换（DFT）的快速算法，是数字信号处理中最重要的工具之一，它在声学，语音，信号处理等领域有着广泛的应用。是将信号从时域变换到频域的一种变换形式，是信号处理领域中一种重要的分析工具。离散傅里叶变换（DFT）是连续傅里叶变换在离散系统中的表现形式。傅里叶变换分为连续傅里叶变换和离散傅里叶变换。离散傅里叶变换简称DFT，是对离散信号进行傅里叶变换的方法，其运算量大、复杂度与变换点数的二次方成正比，因而不适用于进行实时信号处理。20世纪60年代由Cooley和Tuke

4、y提出了快速傅里叶变换（FFT）算法，它是快速计算DFT的一种高效方法，可以明显地降低运算量，大大地提高DFT的运算速度，从而使DFT在实际中得到了广泛的应用，已成为数字信号处理最为重要的工具之一。DSP芯片的出现使FFT的实现变得更加方便。由于多数的DSP芯片都能在单指令周期内完成乘法累加运算，而且还提供了专门的FFT指令（如实现FFT算法所必需的比特反转等），使得FFT算法在DSP芯片上实现的速度更快。本节首先简要介绍FFT算法的基本原理，然后介绍FFT算法的DSP实现。2.2 FFT算法原理快速傅氏变换（FFT）是离散傅氏变换的快速算法，根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅里

5、叶变换算法进行改进获得的。对傅氏变换的理论并没有新的发现，但是对在计算机系统或者数字系统中应用离散傅里叶变换，可以说进了一大步。设为N项的复数序列，由DFT变换，任一X(M)的计算需要N次复数乘法和N-1次复数加法，而一次复数乘法等于四次实数乘法和两次实数加法，一次复数加法等于两次实数加法，即使把一次复数乘法和一次复数加法定义成一次“运算”（四次实数乘法和四次实数加法），则求出N项复数序列的X(M)，即N点DFT变换大约需要次运算。当N=1024点甚至更多的时候，需要次运算，在FFT中，利用的周期性和对称性，把一个N项序列（设N=2k，k为正整数），分为两个项的子序列，每个点DFT变换需要次运

6、算，再N次运算把两个点的DFT变换组合成一个N点DFT变换。这样变换以后，总运算次数变成。继续上面的例子，N=1024时，总的运算次数就变成了525312次，节省了大约50%的运算量。如果将这种“一分为二”思想不断进行下去，直到分成两两一组DFT运算单元，则N点DFT变换只需要次运算，N在1024时，运算量仅有10240次，是先前直接算法的1%，点数越多，运算量节约就越大，这就是FFT的优越性。2.3 快速傅立叶变换算法FFT的基本思想：将大点数的DFT分解为若干个小点数DFT组合，从而减少运算量。根据对序列分解与选取方法的不同而产生了FFT的多种算法。算法分类如图2-1所示：FFT算法基-2

7、FFT算法基-4FFT算法混合基算法分裂基算法线性调频Z变换算法按时间抽取按频率抽取图2-1 FFT的几种算法在这次设计中，采用最基础的按时间抽取的基-2FFT算法来实现快速傅里叶变换。为了将大点数的DFT分解为小点数的DFT运算，要求序列的长度N为复合数，最常用的是的情况（M为正整数）。该情况下的变换称为基-2FFT算法。下面讨论基-2FFT情况的算法。先将序列x(n)按奇偶项分解为两组： （2-1）将DFT运算也相应分为两组: （2-3）至此，一个点DFT被分解为两个点的DFT。由式（2-3）能否将全部的点的解求出来？分析： （2-4）和只有个点，则由式（2-4）只能求出X(k)的前个点的

8、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时，有次与因子相乘，一共需要次复乘。可见，通过这样的分解，运算量节省了近一半。因为，仍然是偶数，因此可以对两个点的DFT分别作进一步的分解，将两个的DFT分解成两个点的DFT。例如对，可以再按其偶数部分及奇数部分进

9、行分解： （2-7）则运算可相应分为两组：将系数统一为以N为周期，即，可得 （2-8）同样，对也可以进行类似的分解。一直分解下去，最后是2点的DFT，2点的DTF的运算也可以用蝶形符号来表示。这样，对于一个的DFT运算，最终结如图2-3图2-3蝶形图这种方法，由于每一步分解都是按输入序列在时域上的次序是属于偶数还是奇数来抽取的，故称为“时间抽取法”。分析上面的流图，一共要进行M次分解，构成了从到的M级运算过程。每一级运算都是由个蝶形运算构成，因此每一级运算都需要次复乘和M次复加，则按时间抽取的M级运算后总用需要：复数乘法次数： 复数加法次数： 根据上面过程，分析FFT算法的两个特点，它们对FF

10、T的软硬件构成产生很大的影响。原位运算：也成为同址运算，当数据输入到存储器中以后，每一级运算的结果仍然存储在原来的存储器中，直到最后输出，中间无需其它的存储器。根据运算流图分析原位运算是如何进行的。原位运算的结构可以节省存储单元，降低设备成本。变址：分析运算流图中的输入输出序列的顺序，输出按顺序，输入是“码位倒置”的顺序，见表2-1所示。自然顺序 二进制表示 码位倒置 码位倒置顺序 0 000 000 0 1 001 100 4 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 码位倒置顺序

11、实际运算中，直接将输入数据按码位倒置的顺序排好输入很方便，一般总是先按自然顺序输入存储单元，然后通过变址运算将自然顺序的存储换成码位倒置顺序的存储，这样就可以进行FFT的原位运算。用软件实现是通用采用雷德（Rader）算法，算出的倒序以后立即将输入数据和对换。尽管变址运算所占运算量的比例很小，但对某些 高要求的应用（尤其在实时信号处理中），也可设法用适当的电路结构直接实现变址。例如单片数字信号处理器TMS320C25就有专用于FFT的二进制码变址模式。2.4 功能实现2.4.1位置倒码 当进行原位运算时，发现当运算完成后，FFT的输出X(k)按正常顺序排列在存储单元中，即按X(0)，X(1)，

12、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)，即将自然循序的二进制码位倒置过来，第一位码变成最末位码，这样倒置以后的顺序正是输入所需要的顺序，其结果与按时间抽样算法FFT流程图中的输入顺序是一致的。需要注意当进行原位运算时，输入输出序列为倒

13、位序的关系，若不为原位运算，则这种关系不一定成立。在实际运算中，一般直接将输入数据x(n)按码位倒置的顺序排好输入很不方便，总是先按自然顺序的存储，然后进行FFT的原位计算。自然顺序二进码表示码位倒置倒位序0000000010011004201001023011110641000011510110156110011371111117表2-1 码位倒置顺序2.4.2蝶距设N=，则整个运算流图中包含L级蝶形运算，每一级则有N/2个蝶形单元。蝶距等于每个蝶形单元两个输入（出）节点的序列号，即第m级蝶形单元的蝶距为：。2.4.3旋转因子由FFT算法原理过程可知，若=，则共有级蝶形运算，各级蝶形运算中旋

14、转因子分别如下：第级的旋转因子为（=0,1，）；第-1级的旋转因子为（=0,1，）；第一级的旋转因子为（=0,1，）。由此可见， 第级蝶形运算中旋转因子为，=0，1，。2.5 FFT算法的DSP的实现方法设FFT运算的输入数据为实数，则2点实数FFT算法的实现步骤为：第一步，把2实数输入序列组合成点的复数序列。然后把该复数序列进行位倒序操作后存储在输入区。第二步，进行的FFT运算。第三步，把点FFT输出拆成2的复数序列，这2的复数序列对应于2点时实数输入序列的DFT输出。第四步，结果输出及功率谱计算。2.6 FFT运算中应注意的问题为了避免可能的结果溢出，在编写程序时我们应该注意对每次蝶形运算

15、的结果都右移一位，即除以2。为了减少FFT的运算时间和充分利用C54xDSP资源，编程时应尽可能多的采用并行指令。三 设计方框图开始程序初始化南北红送入数据南北红调入系数表南北红输入数据位码倒置南北红FFT的蝶形运算南北红是否发生 溢出？N Y归一化南北红输入数据 结束？ Y各图形输出南北红N结束四 各部分程序设计及参数计算4.1 ADC采样/*初始化系统*/InitSysCtrl();#if SAMPLELONG=1SampleLong =256;#endif#if SAMPLELONG=2SampleLong =512;#endif#if SAMPLELONG=3SampleLong =1

16、024;#endif/*关中断*/DINT;IER = 0x0000;IFR = 0x0000;/*初始化PIE中断*/InitPieCtrl();/*初始化PIE中断矢量表*/InitPieVectTable();/初始化cputimer InitCpuTimers();/*设置中断服务程序入口地址*/EALLOW;/ This is needed to write to EALLOW protected registersPieVectTable.TINT2 = &ISRTimer2;PieVectTable.ADCINT = &ad;EDIS; / This is nee

17、ded 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); StartCpuTimer2();/*开中断*/IER |= M_INT14;EINT;4.2 FFT转换switch(SampleLong/2) c

18、ase128:fft128.ipcbptr=ipcb;fft128.init(&fft128);for(i=0;i<SampleLong/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(&fft256);for(i=0;i<SampleLong/2;i+)ipcbi = Ad_data1i;

19、delay(5000);RFFT32_brev(ipcb,ipcb,FFTN256);fft256.calc(&fft256);fft256.split(&fft256);break;case512:fft512.ipcbptr=ipcb;fft512.init(&fft512);for(i=0;i<SampleLong/2;i+)ipcbi = (long)Ad_data1i; iostatus = 0x288; *p_trafficaddr=iostatus; delay(5000);RFFT32_brev(ipcb,ipcb,FFTN512);fft512.

20、calc(&fft512);fft512.split(&fft512);break;default:break;五 工作过程分析 5.1在CCS下调试程序步骤（1）点击CCS图标启动CCS。（2）打开fft.pjt工程。将已编好的汇编源文件FFT.c及其他相关源文件和命令文件2812.cmd等文件添加到工程中编译，链接产生FFT.out文件。（3）下载FFT.out文件到目标板中。（4）显示示输入信号的时域波形。首先，通过设置实验箱的函数信号发生器，使AD采集波形为0通道的标准正弦波。（5）显示输入信号的频域波形。（6）显示信号功率谱。由配置文件可知，经程序计算得到的信号功率谱

21、放在DATA数组中。显示经程序计算得到的信号功率谱。（7）改变输入信号，如改为方波，三角波等等。并重复（4）（5）（6）三个步骤。5.2 程序的初始化256点实数FFT的程序主要由4部分组成，分别是位反转子程序，FFT核心计算子程序，奇偶分离及结果产生子程序，还有功率谱计算子程序。首先在程序的开始应对程序进行初始化，程序的初始化包括为输入数据和旋转因子表定义变量，还有是在此段程序中设置复数数据的个数以及FFT运算的级数，还设置了正弦表和余弦表。5.3 FFT计算当2=256时，128点复数FFT运算过程分成七级、3个阶段实现，这三个阶段是：第一级蝶形运算，第二级蝶形运算，第三级第级蝶形运算，以

22、下分别分析这三个阶段蝶形运算的工作过程。第一级和第二级蝶形运算仅含加减运算，容易实现，因此在编程时单独处理。在第三级到最后一级蝶形运算中，组内蝶形运算次数逐渐增多，而且多是乘法运算，单独处理是不可取的，因此这段运算采用相同的程序块来实现。蝶形运算主要思想是输入数据乘以旋转因子得到下一级输出，所以在运算之前要计算出这一级的旋转因子。而旋转因子又是一复数运算，因此在程序中设置了正弦表和余弦表，通过查这两个表来计算旋转因子。最后来确定FFT的输出值。正弦系数表和余弦系数表由文件给出，主程序通过.copy 汇编命令将正弦系数和余弦系数与程序代码汇编在一起。数据文件twiddle1.inc和twiddl

23、e2.inc分别给出FFT的正弦系数、余弦系数各512个。利用此系数表可以完成81024点的FFT运算。5.4 输入信号及输出波形5.4.1 正弦波输入正弦波如图5-1所示图5-1正弦波输出波形如图5-2所示图5-2正弦波FFT5.4.2 方波输入方波如图5-3所示图5-3方波输出波形如图5-4所示图5-4方波FFT5.4.3 三角波输入三角波如图5-5所示图5-5三角波输出波形如图5-6所示图5-5三角波FFT六 实验系统介绍6.1 DSP简介波形选择为“正弦波” 、频率输入为“50” 、幅值输入为“2” 、相位输入为“0” 偏移量输入为“0” 、占空比输入量为“0” 。重置开关置于“关”

24、。6.1.1 DSP微处理器DSP（digital signal processor）是一种独特的微处理器，是以数字信号来处理大量信息的器件。其工作原理是接收模拟信号，转换为0或1的数字信号。再对数字信号进行修改、删除、强化，并在其他系统芯片中把数字数据解译回模拟数据或实际环境格式。它不仅具有可编程性，而且其实时运行速度可达每秒数以千万条复杂指令程序，远远超过通用微处理器，是数字化电子世界中日益重要的电脑芯片。它的强大数据处理能力和高运行速度，是最值得称道的两大特色。 DSP微处理器（芯片）一般具有如下主要特点： （1）在一个指令周期内可完成一次乘法和一次加法； （2）程序和数据空间分开，可以

25、同时访问指令和数据； （3）片内具有快速RAM，通常可通过独立的数据总线在两块中同时访问； （4）具有低开销或无开销循环及跳转的硬件支持； （5）快速的中断处理和硬件I/O支持； （6）具有在单周期内操作的多个硬件地址产生器； （7）可以并行执行多个操作； （8）支持流水线操作，使取指、译码和执行等操作可以重叠执行。 当然，与通用微处理器相比，DSP微处理器（芯片）的其他通用功能相对较弱些。6.1.2 DSP的开发工具数字信号处理器（DSP）作为一种可编程专用芯片，是数字信号处理理论实用化过程的重要技术工具，在语音处理、图像处理等技术领域得到了广泛的应用。但对于算法设计人员来讲，利用汇编语言或

26、C 语言进行DSP 功能开发，具有周期长、效率低的缺点，不利于算法验证和产品的快速开发。 由MathWorks 公司和TI 公司联合开发的DSPMATLAB Link for CCS Development Tools（简称CCSLink）是MATLAB6.5 版本（Release13）中增加的一个全新的工具箱，它提供了MATLAB、CCS 和DSP 目标板的接口，利用此工具可以像操作MATLAB变量一样来操作DSP 器件的存储器和寄存器，使开发人员在MATLAB 环境下完成对DSP 的操作，从而极大地提高DSP 应用系统的开发进程。 MATLAB 具有强大的分析、计算和可视化功能，利用MAT

27、LAB 提供的数十个专业工具箱，可以方便、灵活地实现对自动控制、信号处理、通信系统等的算法分析和仿真，是算法设计人员和工程技术人员必不可少的软件工具。6.1.3 DSP算法及芯片分类DSP运算的基本类型是乘法和累加(MAC)运算，对于卷积、相关、滤波和FFT基本上都是这一类运算。这样的运算可以用通用机来完成，但受到其成本和结构的限制不可能有很高的实时处理能力。 DSP运算的特点是寻址操作。数据寻址范围大，结构复杂但很有规律。例如FFT运算，它的蝶形运算相关节点从相邻两点直至跨越N/2间隔的地址范围，每次变更都很有规律，级间按一定规律排列，虽然要运算log2N遍，但每级的地址都可以预测，也就是寻

28、址操作很有规律而且可以预测。这就不同于一般的通用机，在通用机中对数据库的操作，具有很大的随机性，这种随机寻址方式不是信号处理器的强项。 无论是专用的DSP芯片或通用DSP芯片在结构考虑上都能适应DSP运算的这些特点。而专用芯片在结构上考虑的更加专业化，更为合理，因而有更高的运算速度。 为不同算法而专门设计的专用芯片：例如用于做卷积/相关并具有横向滤波器结构，INMOS公司的A100、A110；HARRIS公司的HPS43168；PLESSYGEC公司的PDSP16256等。用于做FFT，Austek公司的A41102，PLESSYGEC公司的PDSP16150等。这些都是为做FIR、IIR、F

29、FT运算而设计的，因而运算速度高，但是具有有限的可编程能力，灵活性差。6.1.4 DSP技术的应用（1）信号处理：数字滤波、自适应滤波、FFT、Hilbert变换、相关运算、频谱分析、卷积、模式匹配、窗函数、波形产生等。 （2）语音处理：语音编码、语音合成、语音识别、语音增强、语音邮件、语音储存等。 （3）图像/图形：二维和三维图形处理、图像压缩与传输、图像识别、动画、机器人视觉、多媒体、电子地图、图像增强等。 （4）军事：保密通信、雷达处理、声呐处理、导航、全球定位、跳频电台、搜索和反搜索等。 （5）仪器仪表：频谱分析、函数发生、数据采集、地震处理等。 （6）自动控制：控制、深空作业、自动驾

30、驶、机器人控制、磁盘控制等。 （7）医疗：助听、超声设备、诊断工具、病人监护、心电图等。 （8）家用电器：数字音响、数字电视、可视电话、音乐合成、音调控制、玩具与游戏等。 6.2 CCS开发环境简介6.2.1 驱动程序的配置（1）双击桌面上的Setup CCStudio v3.3。“Clear”原有的设备驱动程序配置。 （2）根据DSP的型号选择相应的TI原装驱动程序，根据DSP的型号选择相应的TI驱动程序，本实验箱采用SEED_DEC2812，故选择F2812 XDS510 Emulator。如图6-1所示。图6-1目标板选择（3）点中F2812 XDS510 Emulator驱动后，鼠标右

31、键，在弹出的菜单中点击Properties。设置完成后如下图6-2所示。 图6-2目标板选择（4）点击Next，作如下图6-3所示的设置。图6-3目标板选择（5）保存并启动CCS调试界面。6.2.2 创建工程文件按照以下步骤创建一个新工程并运行程序：（1）建一个文本文档，在里面写下程序，修改文本文档的扩展名为.c（2）打开CCStudio_v3.3, 选择Project->New（3）在Project Name框里输入工程名：(例如:1)（4）在Location框里输入或者浏览创建的文件夹。（5）在第三步的创建的文件夹里添加命令脚本2812.cmd和编辑好的.c文件（6）在ccs里打开编

32、好的.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.li

33、b：库文件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实验系统 为了更好地配合学校的理论教学，达到理论与实践完美的结合，合众达公司总结了 10 多年在 DSP 领域中的开发与应用经验，推出了双 DSP 教学系统 SEED-DTK 教学实验箱系列产品。它设计新颖、独特，为师生提供了一个完整的教学实验平台，为学生加速学习与系统掌握DSP 的开发与应用提供了强有力的手段。SEED-DTK 教学实验箱采用模块化设计理念，涵盖了 TI 所有的主流 DSP 系列：C2000、C3X、C5000 和 C6000 系列。其中 SEED-DTK实验箱中的主控板 SEED-DECxxxx 采用统一的系统结构、模块结构、机械结构和标准的总线接口以及相同的物理尺