您的当前位置：首页快速傅里叶变换程序设计

快速傅里叶变换程序设计

来源：星星旅游

沈阳工程学院

课程设计

设计题目：快速傅里叶变换程序设计

系别自动控制工程系班级测控本091班学生姓名庄国庆学号 2009308126 指导教师吕勇军职称教授起止日期：2011年 7 月 1 日起—至 2010 年 7 月5 日止

沈阳工程学院

课程设计任务书

课程设计题目：快速傅里叶变换程序设计

系别自动控制工程系班级测控本091班学生姓名庄国庆学号 2009308126 指导教师吕勇军职称教授课程设计进行地点：实训F430 任务下达时间： 10年 7月1日

起止日期： 10年7月1日起——至10年7月5日止

教研室主任年月日批准

1.设计主要内容及要求；

编写正弦信号发生器程序。

要求：1）研究FFT原理以及利用DSP实现的方法。 2）编写FFT程序。 3）调试程序，观察结果。

2.对设计论文撰写内容、格式、字数的要求；

（1）.课程设计论文是体现和总结课程设计成果的载体，一般不应少于3000字。

（2）.学生应撰写的内容为：中文摘要和关键词、目录、正文、参考文献等。课程设计论文的结构及各部分内容要求可参照《沈阳工程学院毕业设计（论文）撰写规范》执行。应做到文理通顺，内容正确完整，书写工整，装订整齐。

（3）.论文要求打印，打印时按《沈阳工程学院毕业设计（论文）撰写规范》的要求进行打印。

（4）. 课程设计论文装订顺序为：封面、任务书、成绩评审意见表、中文摘要和关键词、目录、正文、参考文献。

3.时间进度安排；顺序阶段日期 1 2 计划完成内容备注 7月4日教师讲解题目，学生查阅相关资料 7月5日进行方案论证，确定程序流程，计算参数 3 4 5

7月6日编写程序 7月7日调试程序 7月8日撰写论文，程序验收 II

DSP技术课程设计成绩评定表

系（部）：自控系班级：测控本091班学生姓名：庄国庆

指导教师评审意见评价内容具体要求权重 0.1 5 评分 4 3 2 加权分调研能查阅文献,收集资料；能制定课程设计方案论证和日程安排。工作工作态度认真，遵守纪律，出勤情况是否良好，能能力够完成设计工作，态度工作量按期完成规定的设计任务，工作量饱满，难度适宜。 0.2 5 4 3 2 0.2 5 4 3 2 说明说明书立论正确，论述充分，结论严谨合理，文字书的通顺，技术用语准确，符号统一，编号齐全，图表质量完备，书写工整规范。 0.5 5 4 3 2 指导教师评审成绩（加权分合计乘以12）指导教师签名：分加权分合计年月日评阅教师评审意见评价内容查阅文献工作量具体要求查阅文献有一定广泛性；有综合归纳资料的能力工作量饱满，难度适中。权重 0.2 0.5 评分加权分 5 5 5 4 4 4 3 3 3 2 2 2 说明说明书立论正确，论述充分，结论严谨合理，文字书的通顺，技术用语准确，符号统一，编号齐全，图表质量完备，书写工整规范。 0.3 评阅教师评审成绩（加权分合计乘以8）评阅教师签名：课程设计总评成绩

III

分加权分合计年月日分

中文摘要

DSP（digital singnal processor）是一种独特的微处理器，是以数字信号来

处理大量信息的器件。其工作原理是接收模拟信号，转换为0或1的数字信号，再对数字信号进行修改、删除、强化，并在其他系统芯片中把数字数据解译回模拟数据或实际环境格式。它不仅具有可编程性，而且其实时运行速度可达每秒数以千万条复杂指令程序，源源超过通用微处理器，是数字化电子世界中日益重要的电脑芯片。它的强大数据处理能力和高运行速度，是最值得称道的两大特色 DSP既是Digital Signal Processing的缩写(数字信号处理的理论和方法)或者是Digital Signal Processor(用于数字信号处理的可编程微处理器)的缩写。我们所说的DSP技术,则一般指将通用的或专用的DSP处理器用于完成数字信号处理的方法和技术。

傅里叶变换是将信号从时域变换到频域的一种变换形式，是信号处理领域中一种重要的分析工具。离散傅里叶变换（DFT）是连续傅里叶变换在离散系统中的表现形式。采用高级C语言实现FFT算法。利用DSP芯片特有的哈佛结构和专门的FFT指令。在DSP上能够更快的实现FFT。从而促进DSP芯片的发展，同时加快基于DSP数字信号处理的速度

通过对FFT的算法进行研究，从基础深入研究和学习，掌握FFT算法的关键。研究DSP芯片如何加快蝶形计算以及如何有效地码位倒置的输出颠倒过来。熟悉旋转因子的生成。通过学习DSP芯片的工作原理，分析DSP控制的算法，在DSP芯片上实现快速傅立叶变换算法的设计。通过对DSP开发环境的学习，掌握CCS的简单调试和软件仿真。在CCS开发环境中观察正弦波输入波形、输出波形、PC机FFT计算处理后的仿真波形图。比较仿真图，验证设计和程序的正确性。表明利用DSP控制器特有的反序间接寻址使FFT的实现更加方便

关键词数字信号处理（DSP），快速傅里叶变换（FFT），旋转因子

快速傅里叶变换程序设计

课程设计任务书 ............................................................................................................................. ..I 课程设计成绩评定表.................................................................................................................. .. Ⅲ 中文摘要 ............................................................................................................................................................ IV 1 设计任务描述 ...................................................................................................................................................1

1.1 设计题目 ...............................................................................................................................................1 1.2 设计目的 ................................................................................................................................................1 1.3 基本要求 ................................................................................................................................................1 2 设计思路 ...........................................................................................................................................................2

2.1 FFT算法简介 .........................................................................................................................................2 2.2 FFT原理 .................................................................................................................................................2 2.3 快速傅里叶变换算法 ............................................................................................................................3 3 软件流程图 .......................................................................................................................................................7 4 各部分程序设计及参数计算 ...........................................................................................................................8

4.1 程序编写 ................................................................................................................................................8 4.2 CCS开发环境的使用及软件仿真 ........................................................................................................8

4.2.1 CCS开发环境的使用 .................................................................................................................8 4.2.2CCS软件仿真 ..............................................................................................................................9

5 程序的调试 .....................................................................................................................................................11 6 工作过程分析 .................................................................................................................................................12

6.1 程序的初始化 ......................................................................................................................................12 6.2 位倒序子程序 ......................................................................................................................................12 6.3 FFT计算 ...............................................................................................................................................12 6.4 功率谱的计算 ......................................................................................................................................12 小结 .....................................................................................................................................................................13 致谢 .....................................................................................................................................................................14 参考文献 .............................................................................................................................................................15 附录A1 程序清单 .............................................................................................................................................16

快速傅里叶变换程序设计

1 设计任务描述

1.1 设计题目

快速傅里叶变换程序设计

1.2. 设计目的

1）理解FFT的算法以及利用DSP实现的方法。 2）能熟练的调试程序并能观察其结果。

3）熟悉TMS320Cx系列DSP芯片的软件设计方法。

1.3 基本要求

1）研究FFT原理以及利用DSP实现的方法。 2）编写FFT程序。

3）调试程序，观察结果。

快速傅里叶变换程序设计

2 设计思路

2.1 FFT算法简介

快速傅里叶变换（FFT）是一种高效实现离散傅里叶变换（DFT）的快速算法，是数字信号处理中最重要的工具之一，它在声学，语音，信号处理等领域有着广泛的应用。是将信号从时域变换到频域的一种变换形式，是信号处理领域中一种重要的分析工具。离散傅里叶变换（DFT）是连续傅里叶变换在离散系统中的表现形式。

傅里叶变换分为连续傅里叶变换和离散傅里叶变换。离散傅里叶变换简称DFT（Discrete Fourier Transform），是对离散信号进行傅里叶变换的方法，其运算量大、复杂度与变换点数的二次方成正比，因而不适用于进行实时信号处理。20世纪60年代由Cooley和Tukey提出了快速傅里叶变换（FFT）算法，它是快速计算DFT的一种高效方法，可以明显地降低运算量，大大地提高DFT的运算速度，从而使DFT在实际中得到了广泛的应用，已成为数字信号处理最为重要的工具之一。

DSP芯片的出现使FFT的实现变得更加方便。由于多数的DSP芯片都能在单指令周期内完成乘法—累加运算，而且还提供了专门的FFT指令（如实现FFT算法所必需的比特反转等），使得FFT算法在DSP芯片上实现的速度更快。本节首先简要介绍FFT算法的基本原理，然后介绍FFT算法的DSP实现。

2.2 FFT原理

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

22N/2）NN2/2。变成N（继续上面的例子，N=1024时，总的运算次数就变成了525312

次，节省了大约50%的运算量。如果将这种“一分为二”思想不断进行下去，直到分成两

N两一组DFT运算单元，则N点DFT变换只需要Nlog2次运算，N在1024时，运算量仅有10240次，是先前直接算法的1%，点数越多，运算量节约就越大，这就是FFT的优越性。

快速傅里叶变换程序设计

2.3 快速傅里叶变换算法

FFT的基本思想：将大点数的DFT分解为若干个小点数DFT的组合，从而减少运算量。根据对序列分解与选取方法的不同而产生了FFT的多种算法[3]。算法分类如图2-1所示：

基-2FFT算法基-4FFT算法

FFT算法

按时间抽取

按频率抽取

混合基算法基算法线性调频Z变换算法

图2-1 FFT的几种算法

在这次设计中，采用最基础的按时间抽取的基-2FFT算法来实现快速傅里叶变换。为了将大点数的DFT分解为小点数的DFT运算，要求序列的长度N为复合数，最常用的是

。该情况下的变换称为基-2FFT算法。下面讨论基-2FFT情N2M的情况（M为正整数）

况的算法。

先将序列x(n)按奇偶项分解为两组：

x(2r)x1(r)N r0,1,2,,1 （2-1） 2x(2r1)x2(r)将DFT运算也相应分为两组:

快速傅里叶变换程序设计

rkrkX1(k)x1(r)WNx(2r)W/2N/2,0kr0r0N12r0N12r0N12N12N12N12 （2-3）

rkrkX2(k)x2(r)WN/2x(2r1)WN/2,0k至此，一个N点DFT被分解为两个N/2点的DFT。由式（2-3）能否将全部的N点的

解求出来？

分析：

kX(k)X1(k)WNX2(k) （2-4）

X1(k)和X2(k)只有N/2个点，则由式（2-4）只能求出X(k)的前N/2个点的DFT。要

求出全部N点的X(k)，需要找出X1(k)、其中k=0,1,2......(N/2)-1。X2(k)和X(kN/2)的关系，

kN/2由式子（2-4）可得X(kN/2)X1(kN/2)WNX2(kN/2)化简得

NkX(kN/2)X1(k)WNX2(k) k=0,1,,1 （2-5）

2这样N点DFT可全部由下式确定出来：

X(k)X1(k)WNkX2(k)N k=0,1,,1 （2-6） k2X(kN/2)X(k)WX(k)1N2上式可用一个专用的蝶形符号表示，如图2-2所示，对应一次复乘和两次复加运算。

kaWNbk

WNkaWNbb

-1

图2-2 蝶形运算符号

通过这样的分解以后，每一个N/2点的DFT只需要(N)2N2次复数乘法，两个N/224点的DFT需要2(N)22N22次复乘，再加上将两个N/2点DFT合并成N点的DFT时，有N/222NNN次与WN因子相乘，一共需要次复乘。可见，通过这样的分解，运算量节省了222近一半。

快速傅里叶变换程序设计

因为N2M，N/2仍然是偶数，因此可以对两个N/2点的DFT分别作进一步的分解，将两个的DFT分解成两个N/4点的DFT。

例如对x1(r)，可以再按其偶数部分及奇数部分进行分解：

x1(2l)x3(l) N l0,1,,1 （2-7） 4x1(2l1)x4(l)则运算可相应分为两组：

N/41X1(k) l0x1(2l)W2lkN/2N/41l0(2l1)kx1(2l1)WN/2N/41N/41l0x3(l)WlkN/4WkN/2l0lkx4(l)WN/4 X3(k)WNk0,1,,14kN/2X4(k)

将系数统一为以N为周期，即WN/2Wk2kN，可得

X1(k)X3(k)WN2kX4(k) N k=0,1,,1 （2-8） 2k4X1(kN/4)X3(k)WNX4(k)同样，对X2(k)也可以进行类似的分解。一直分解下去，最后是2点的DFT，2点的DTF的运算也可以用蝶形符号来表示。这样，对于一个N238的DFT运算，最终结如

图2-3

快速傅里叶变换程序设计

这种方法，由于每一步分解都是按输入序列在时域上的次序是属于偶数还是奇数来抽取的，故称为“时间抽取法”。

分析上面的流图，N2M一共要进行M次分解，构成了从x(n)到X(k)的M级运算过程。每一级运算都是由N/2个蝶形运算构成，因此每一级运算都需要N/2次复乘和M次复加，则按时间抽取的M级运算后总用需要：

NN复数乘法次数：mF*Mlog2N

22复数加法次数：aFN*MNlog2N

根据上面的过程，分析FFT算法的两个特点，它们对FFT的软硬件构成产生很大的影响。

（1）原位运算：也成为同址运算，当数据输入到存储器中以后，每一级运算的结果仍然存储在原来的存储器中，直到最后输出，中间无需其它的存储器。根据运算流图分析原位运算是如何进行的。原位运算的结构可以节省存储单元，降低设备成本。

（2）变址：分析运算流图中的输入输出序列的顺序，输出按顺序，输入是“码位倒置”的顺序，见表2-1所示。

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

快速傅里叶变换程序设计

2 DSP简介

DSP微处理器

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

（1）在一个指令周期内可完成一次乘法和一次加法；（2）程序和数据空间分开，可以同时访问指令和数据；

（3）片内具有快速RAM，通常可通过的数据总线在两块中同时访问；（4）具有低开销或无开销循环及跳转的硬件支持；（5）快速的中断处理和硬件I/O支持；

（6）具有在单周期内操作的多个硬件地址产生器；（7）可以并行执行多个操作；

（8）支持流水线操作，使取指、译码和执行等操作可以重叠执行。

当然，与通用微处理器相比，DSP微处理器（芯片）的其他通用功能相对较弱些。

DSP优点

对元件值的容限不敏感，受温度、环境等外部因素影响小；容易实现集成；VLSI

可以分时复用，共享处理器；

方便调整处理器的系数实现自适应滤波；

可实现模拟处理不能实现的功能：线性相位、多抽样率处理、级联、易于存储等；可用于频率非常低的信号。

DSP缺点

需要模数转换；

受采样频率的，处理频率范围有限；

数字系统由耗电的有源器件构成，没有无源设备可靠。

但是其优点远远超过缺点。

快速傅里叶变换程序设计

DSP的开发工具数字信号处理器（DSP）作为一种可编程专用芯片，是数字信号处理理论实用化过程的重要技术工具，在语音处理、图像处理等技术领域得到了广泛的应用。但对于算法设计人员来讲，利用汇编语言或C 语言进行DSP 功能开发，具有周期长、效率低的缺点，不利于算法验证和产品的快速开发。

由MathWorks 公司和TI 公司联合开发的DSPMATLAB Link for CCS Development Tools（简称CCSLink）是MATLAB6.5 版本（Release13）中增加的一个全新的工具箱，它提供了MATLAB、CCS 和DSP 目标板的接口，利用此工具可以像操作MATLAB变量一样来操作DSP 器件的存储器和寄存器，使开发人员在MATLAB 环境下完成对DSP 的操作，从而极大地提高DSP 应用系统的开发进程。

MATLAB 具有强大的分析、计算和可视化功能，利用MATLAB 提供的数十个专业工具箱，可以方便、灵活地实现对自动控制、信号处理、通信系统等的算法分析和仿真，是算法设计人员和工程技术人员必不可少的软件工具。

DSP算法及芯片分类 DSP运算的基本类型是乘法和累加(MAC)运算，对于卷积、相关、滤波和FFT基本上都是这一类运算。这样的运算可以用通用机来完成，但受到其成本和结构的不可能有很高的实时处理能力。

DSP运算的特点是寻址操作。数据寻址范围大，结构复杂但很有规律。例如FFT运算，它的蝶形运算相关节点从相邻两点直至跨越N/2间隔的地址范围，每次变更都很有规律，级间按一定规律排列，虽然要运算log2N遍，但每级的地址都可以预测，也就是寻址操作很有规律而且可以预测。这就不同于一般的通用机，在通用机中对数据库的操作，具有很大的随机性，这种随机寻址方式不是信号处理器的强项。

无论是专用的DSP芯片或通用DSP芯片在结构考虑上都能适应DSP运算的这些特点。而专用芯片在结构上考虑的更加专业化，更为合理，因而有更高的运算速度。

DSP芯片按用途或构成分类可以分为下列几种类型：

为不同算法而专门设计的专用芯片：例如用于做卷积/相关并具有横向滤波器结构，INMOS公司的A100、A110；HARRIS公司的HPS43168；PLESSYGEC公司的PDSP16256等。用于做FFT，Austek公司的A41102，PLESSYGEC公司的PDSP16150等。这些都是为做FIR、IIR、FFT运算而设计的，因而运算速度高，但是具有有限的可编程能力，灵活性差。

快速傅里叶变换程序设计

DSP技术的应用信号处理：数字滤波、自适应滤波、FFT、Hilbert变换、相关运算、频谱分析、卷积、模式匹配、窗函数、波形产生等。

语音处理：语音编码、语音合成、语音识别、语音增强、语音邮件、语音储存等。图像/图形：二维和三维图形处理、图像压缩与传输、图像识别、动画、机器人视觉、多媒体、电子地图、图像增强等。

军事：保密通信、雷达处理、声呐处理、导航、全球定位、跳频电台、搜索和反搜索等。仪器仪表：频谱分析、函数发生、数据采集、地震处理等。

自动控制：控制、深空作业、自动驾驶、机器人控制、磁盘控制等。医疗：助听、超声设备、诊断工具、病人监护、心电图等。

家用电器：数字音响、数字电视、可视电话、音乐合成、音制、玩具与游戏等。

生物医学信号处理举例：

快速傅里叶变换程序设计

3 程序语言及CCS开发环境

3.1 程序编写

DSP软件设计多用于算法比较复杂、乘加运算量比较大的场合,如通信、雷达、音视频处理等。为了追求代码的高效性,以前大都用汇编语言来编DSP的应用软件。随着DSP的应用范围不断延伸，单纯的汇编语言程序的难读性、难移植性、难修改性等缺点日益突出。C语言以其独特的可读性、可修改性和可重用性，使DSP的运算速度大幅提高。用C语言进行DSP软件设计，其效率一般低于汇编语言编制，这是因为汇编语言是低级语言，形成目标代码的速度比C语言快，因此，用C语言进行软件设计时，优化设计显得尤为重要。鉴于DSP应用复杂性，用C语言进行软件开发时，一般先在PC上对算法进行仿真，然后将程序移植到DSP平台中。

由于DSP程序需要首先使用高级语言来模拟算法性能，对于本次设计题目基于DSP的快速傅里叶变换算法，采用C语言编程。程序参考教材

注：整体程序见附录

3.2 CCS开发环境的配置、使用及软件仿真

CCS提供了配置、建立、调试、跟踪和分析程序的工具，它便于实时、嵌入式信号处理程序的编制和测试，它能够加速开发进程，提高工作效率。CCS提供了基本的代码生成工具，它具有一系列的调试、分析能力。CCS支持如下所使的开发周期的所有阶段：

3.2.1 CCS开发环境的配置

Code Composer Studio IDE是强大的DSP集成开发工具，利用CCS开发环境可以实现

快速傅里叶变换程序设计

对设计的软件仿真。

针对所选择DSP芯片TMS320C16芯片选择CCS的型号，本次设计采用CCStudio v3.3开发环境。在进入CCS开发环境前，必须选择一个合适的配置环境。进入配置设定软件Setup CCStudio v3.3。

使用标准配置文件产生一个系统配置：

（1）双击桌面上的Setup Code Composer Sutdio图标，出现系统配置配置对话框。（2）从available factory board中选择与系统匹配的标准设置。确定可用配置中是否存在与系统匹配的配置，本次设计采用F2812 Device Simulator如图4-1所示

图4-1

（3）单击选择的配置，然后单击ADD按钮将选择的配置添加到system configuration中。这样选择的配置就出现在系统配置方框中My System图标下面。如果你的配置包含多于一个的目标板，重复以上步骤直到你为每一个目标板选择了一个配置。

（4）单击Save & Quit按钮保存配置。（5）单击Yes按钮，启动配置好的CCS集成开发环境。现在可以打开一个工程。进入CCS开发环境后，可以建立一个新的工程也可以直接打开一个已有的工程。

按照以下步骤创建一个新工程并运行程序：

（1）建一个文本文档，在里面写下程序，修改文本文档的扩展名为.c （2）打开CCStudio_v3.3, 选择Project->New （3）在Project Name框里输入工程名：(例如:1) （4）在Location框里输入或者浏览创建的文件夹。

（5）在第三步的创建的文件夹里添加命令脚本2812.cmd和编辑好的.c文件

快速傅里叶变换程序设计

（6）在ccs里打开编好的.c文件，依次点击编译、连接、运行，执行File->Load Program加载程序。加载过程是将上述构建成功，生成的可执行文件加载到目标板，目标板可以是软件仿真环境，也可以是硬件目标板。默认情况下，CCS集成开发环境将会在你的工程路径下创建一个Debug子目录，把生成的.out文件放在里面。点击Open加载。

3.2.2 CCS窗口介绍及文件简介

CCS窗口介绍：

使用CCS常遇见的文件简介： 1. program,c：C程序源文件

2. program.asm：汇编程序源文件

3. filename.h：C程序的头文件，包含DSP/BIOS API模块的头文件 4. filename.lib：库文件

5. project.cmd：连接命令文件

6. program.obj：由源文件编译或汇编而得的目标文件

7. program.out：经完整的编译、汇编以及连接都生成可执行文件 8. program.map：经完整的编译、汇编以及连接后生成空间分配文件 9. project.pjt：存储环境设置信息的工作区文件保存配置文件时将产生下列文件： 1. programcfg.cmd：连接器命令文件 2. programcfg.h：汇编头文件 3. programcfg.s：汇编源文件

快速傅里叶变换程序设计

3.2.3 CCS软件仿真

CCS IDE可以通过各种方法把程序处理到的数据画出来，包括时间/频率，星座图，眼图和图像。选择View-> Graph，可以得到这些图，然后选择需要的图。这时候可以在图属性（graph property）的对话框中指定图的属性选项。(如上图)

面的例子展示了一个单时刻(时间/频率)图表属性对话框点击，一旦属性被设定了，选择OK按钮，开启图窗口，就会画出指定的数据点

根据芯片和所编写的程序，我做了两个个仿真图：方波输入波形、PC机FFT计算处理后的仿真波形图。Display type分别是single time和FFT magnitude。其中输入在single time下完成。两个个仿真的start address都是INPUT。都采用16-bit signed integer。最后得出的软件仿真图依次如图4-2、图4-3所示：

图4-2 输入的方波

快速傅里叶变换程序设计

图4-3 FFT处理后的波形

快速傅里叶变换程序设计

4 软件流程图

开始程序初始化送入数据调入系数表输入数据位码倒置 FFT的蝶形运算Ｎ是否发生溢出？Ｙ归一化Ｎ输入数据结束？Ｙ各图形输出结束

快速傅里叶变换程序设计

5 各部分程序设计及参数计算

快速傅里叶变换程序设计

6 程序的调试及结果

我们根据老师给定的FFT程序在CCS环境下进行调节，经过很多次调试，终于出现了理想的波形输出。并在原来程序的基础上加入了指示灯的信号程序：当程序进入到FFT变换时，黄色指示灯亮；执行完或执行之前，红色指示灯亮。经过几次调试以后，指示灯显示程序正常。

正弦波形：

FFT变换之后波形：

方波：

快速傅里叶变换程序设计

FFT变换之后的波形：

三角波：

FFT变换之后的波形：

快速傅里叶变换程序设计

7 工作过程分析

6.1 程序的初始化

128点实数FFT的程序主要由4部分组成，分别是位反转子程序，FFT核心计算子程序，奇偶分离及结果产生子程序，还有功率谱计算子程序。首先在程序的开始应对程序进行初始化，程序的初始化包括为输入数据和旋转因子表定义变量，还有是在此段程序中设置复数数据的个数以及FFT运算的级数，还设置了正弦表和余弦表。

6.2 位倒序子程序

在编写位倒序子程序时，使用提供的位倒序寻址方式，可以方便的实现位倒序操作。在该寻址方式下，用AR0存放数据N/2，用另外的辅助寄存器ARx存放原始数据的首地址，位倒序操作把AR0中的数加到ARx中，且以向右进位的方式进行，则所得地址将以位倒序的方式产生。

6.3 FFT计算

当2N=256时，128点复数FFT运算过程分成七级、3个阶段实现，这三个阶段是：

N第一级蝶形运算，第二级蝶形运算，第三级～第log2级蝶形运算，以下分别分析这三个阶段蝶形运算的工作过程。

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

6.4 功率谱的计算

对信号进行傅里叶变换取sin部分为实部，cos部分为虚部，直接算实部和虚部的平方和，得到的就是功率谱分布。功率信号的功率谱反应了信号功率随频率分布的特点，功率谱是信号先自相关再作FFT变换

快速傅里叶变换程序设计

小结

单片机、DSP、智能仪器、ARM是我们专业的几门主要课程，都涉及到编程的知识，虽然我们以前也做过单片机的不少实验和课设，但是以前都是用汇编编的，但这次的DSP课设却用C语言编程，而且DSP中有很多指令单片机中都没有，这些都给我带来了不少的麻烦。还有，FFT在我们上学期的数字信号处理中学过，可当时本就没怎么听懂，再加上这么上时间没接触，都已经忘的差不多了，我不得又查了好多的资料对快速傅里叶变换重新学习了一遍，在学习离散傅里叶变换的基础上，研究快速傅里叶变换的原理，掌握了快速傅里叶变换的几种算法，并深入学习了以基-2FFT算法为主结合混合基的算法，为下面的程序编写和研究奠定了基础。通过这次的课设，我更加熟悉了CCS开发的环境，它提供了环境配置、源文件编辑、程序调试、跟踪和分析等工具，帮助用户在一个软件环境下完成编辑、编译链接、调试和数据分析等工作。这样大大加快软件开发进程，提高工作效率。在设计部分，成功的在CCS环境下检测程序，做出软件仿真波形图：正弦波输入波形、PC机FFT计算处理后的仿真波形图。基本完成课题设计，做出成果。比较仿真图，可以对设计进行更深入的学习，验证了程序设计的正确性。

这次课设除了学到了更多，也和老师有了更多的沟通，在课设期间，老师组织了一次简单的探讨，一个班叫了6个学生，让我们对自的专业提出自己的一些看法和意见，老师能在这么繁忙的工作中还不能然我们给提意见，这让我很是感动，老师为自己的事业倾尽心血，对待我们不想是师生，倒像是朋友，经常能看到吕老师在同学面前大笑，笑的是那么的真诚、那么的亲切。原本我对老师有种惧怕或者说抵触，可是吕老师让我的这种感觉不见了，甚至很想和吕老师多多交流、沟通。每次吕老师看到自己在调试程序，都会拍着我的肩膀笑笑，似乎对我很有信心似得，这让我产生很大的动力，让我相信自己一定可以成功的调试出程序。

一周的课设结束了，这次的课设意义又非比寻常，课设一结束，我们大三的生活也即将结束，我们也将进入找工作的阶段，我们原本迷茫、原本惆怅，可一想到吕老师那充满鼓舞的微笑，我们也充满了动力，一切困难我们都会努力的解决

快速傅里叶变换程序设计

致谢

\"春蚕到死丝方尽，蜡炬成灰泪始干\"，我用这两句来说我们的吕老师实在是在恰当不过了，在这一周的课设中，吕老师每天都要到实验室来看看同学们的设计过程，如果哪位同学有什么不能解决的问题，吕老师都会不厌其烦的引导，给出思路。他每天都很忙，很多时候他都在办公室忙着搞科研，同学们有问题了就会到他的办公室去找他，每次去办公室找老师时心里都会有些害怕，担心会因为打扰他他会批评我们，但是每次找吕老师时，他的脸上总是面带着微笑，然后给同学们认真的讲解。而这次，吕老师不但要带着我们搞课设，还要指导那些参加飞思卡尔比赛的同学，吕老师这一周过的真的很累，老师，您辛苦了

在这里我也同样要感谢雷老师在最后一天对我们的答辩，因为吕老师临时有事，故雷老师给我答辩，这本不是雷老师的事，雷老师本可对我们宽松些，这样自己也会轻松许多，然而雷老师却非常的认真，总是问的详详细细的，好多同学都被问的无言以对，而且因为大家都急着答辩，害的雷老师很晚才去吃午饭，炎热的夏天，闷热的教室，豆大的汗珠顺着雷老师的脸颊流下来，在次，我怎么忘记对雷老师的感谢

同时，也感谢和自己做相同课设题目的黄玉亮、石菊等人，我每当越到不懂的地方都是先和大家一切探讨，所以，这次课设的成功同样离不开我的同学们，谢谢你们

在此，也感谢图书馆为我们提供便利的条件查询资料，谢谢

快速傅里叶变换程序设计

参考文献

[1] 俞一彪，孙兵. 数字信号处理理论与应用.南京：东南大学出版社，2005 [2] 李行一. 数字信号处理.重庆：重庆大学出版社，2002

[3] 刘和平.数字信号处理器、结构及应用基础——TMS320F28x[M].北京：机械工业出版

社，2007.

[4]姜沫岐，许涵，俞鹏，段国强 . DSP原理与应用—从入门到提高. 北京: 机械工业出版社， 2007

[5] 俞卞章. 数字信号处理. 西安: 西北工业大学出版社， 2002 [6] 百度.www.baidu.com

快速傅里叶变换程序设计

附录A1 程序清单

#include\"math.h\" //数字函数头文件 #define PI 3.1415926 #define N 128 //采样次数N void InitForFFT(); //FFT初始化函数 void MakeWave(); //波形发生函数 void finv(int N1,float *xr,float *xi); //倒序运算函数f（N1，Xr,Xi）,对输入序列倒序 int INPUT[N],DATA[N];

float fWaveR[N],fWaveI[N],w[N]; float sin_tab[N],cos_tab[N]; //正余弦函数 int Mum; //Mun为蝶形图运算的级数

void FFT(float Xr[N],float Xi[N]) //时间抽取法FFT程序，要求采样点数为2的整数幂次方， //X[]和X[]分别为输入序列的实部和虚部 {

int S,B; //S为旋转因子的幂数，B为蝶形图运算输入数据的距离， //也即各级旋转因子的个数 int m,j,k; float X,Y;

finv(N,Xr,Xi); //倒序运算函数，对输入序列倒序 for(m=1;m<=Mum;m++) {

B=(int)(pow(2,m-1)+0.5); //B=2^(m-1) for(j=0;jS=j*(int)pow(2,Mum-m)+0.5;

for(k=j;k<=N-1;k+=(int)(pow(2,m)+0.5)) {

X=Xr[k+B]*cos_tab[S]+Xi[k+B]*sin_tab[S]; Y=Xi[k+B]*cos_tab[S]-Xr[k+B]*sin_tab[S]; Xr[k+B]=Xr[k]-X; Xi[k+B]=Xi[k]-Y; Xr[k]=Xr[k]+X; Xi[k]=Xi[k]+Y; } } }

for(m=0;m23

快速傅里叶变换程序设计

{

w[m]=sqrt(Xr[m]*Xr[m]+Xi[m]*Xi[m]); } }

main() {int i;

InitForFFT(); MakeWave(); for(i=0;ifWaveR[i]=INPUT[i]; fWaveI[i]=0.0; w[i]=0.0; }

Mum=(int)(0.5+log(N)/log(2)); FFT(fWaveR,fWaveI);

for(i=0;ivoid InitForFFT() { int i;

for(i=0;isin_tab[i]=sin(PI*2*i/N); cos_tab[i]=cos(PI*2*i/N); } }

void MakeWave() { int i;

for(i=0;iINPUT[i]=sin(PI*2*i/N*3)*1024; } }

//计算功率普 //FFT初始化函数 //波形发生函数 //Mum为蝶形运算的级数，N=2^Mun //FFT初始化函数，建立正余弦函数表 //波形发生函数 //f=3Hz,正弦函数 24

快速傅里叶变换程序设计

//倒序运算函数finv(N1,Xr,Xi),对输入序列倒序

//N1为序列长度；Xr[],Xi[]分别为输入序列的实部和虚部

//倒序原理：倒序列的加1实在最高位加1，满2向次高位进1，最高位变0，依次往下 //从当前倒序值可求得下一倒序值

void finv(int N1,float*xr,float*xi) //倒序运算函数f(N1,Xr,Xi),对输入序列倒序 {

int m,n,N2,k; float T; N2=N1/2; n=N2; for(m=1;m<=N1-2;m++) { if(m=k) { n=n-k; k=(int)(k/2+0.5); } n=n+k; } }

//m为正序列；n为到序列；k为各个权值；

//N2为最高位的权值

//临时变量T //最高位加1相当于十进制加上最高位的权N1/2 //第一个倒序值 //第0个和最后一个不倒序 //为了避免再次调换，只需对m

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文