快速傅里叶变换程序设计

《快速傅里叶变换程序设计》由会员分享，可在线阅读，更多相关《快速傅里叶变换程序设计（33页珍藏版）》请在金锄头文库上搜索。

1、沈 阳 工 程 学 院课 程 设 计设计题目： 快速傅里叶变换程序设计 沈阳工程学院课程设计任务书课程设计题目： 快速傅里叶变换程序设计 教研室主任 年 月 日批准1.设计主要内容及要求；编写正弦信号发生器程序。要求：1）研究FFT原理以及利用DSP实现的方法。 2）编写FFT程序。 3）调试程序，观察结果。2.对设计论文撰写内容、格式、字数的要求；（1）.课程设计论文是体现和总结课程设计成果的载体，一般不应少于3000字。（2）.学生应撰写的内容为：中文摘要和关键词、目录、正文、参考文献等。课程设计论文的结构及各部分内容要求可参照沈阳工程学院毕业设计（论文）撰写规范执行。应做到文理通顺，内容

2、正确完整，书写工整，装订整齐。（3）.论文要求打印，打印时按沈阳工程学院毕业设计（论文）撰写规范的要求进行打印。（4）. 课程设计论文装订顺序为：封面、任务书、成绩评审意见表、中文摘要和关键词、目录、正文、参考文献。3.时间进度安排；顺序阶段日期计 划 完 成 内 容备注17月12日教师讲解题目，学生查阅相关资料27月13日确定FFT算法以及程序流程37月14日编写程序47月15日调试程序57月16日撰写论文，程序验收DSP技术课程设计成绩评定表 指 导 教 师 评 审 意 见评价内容具 体 要 求权重评 分加权分调研论证能独立查阅文献,收集资料；能制定课程设计方案和日程安排。0.15432工

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

4、谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.35432评阅教师评审成绩（加权分合计乘以8）分加权分合计评 阅 教 师 签 名： 年 月 日课 程 设 计 总 评 成 绩分中文摘要数字信号处理 (Digital Signal Processing，DSP)是一门涉及许多科学而又广泛应用于众多领域的新兴学科。步入21世纪以后，社会进入数字化时代，而DSP正是这场数字化的核心。简单的说，数字信号处理器就是把信号用数字符号表示成序列，通过计算机或专用信号处理设备，用数字的数值计算方法进行处理（如滤波、变换、压缩、增强、估计、识别等），以达到提取有用信息便于应用的目的

5、。本次课程设计用的是TMS320C54x系列芯片，TMS320C54x系列芯片是TMS320C5000平台下的定点DSP芯片。54x系列芯提供了低成本、低功耗、高性能的处理能力，在各个领域应用日益广泛。本文就是利用它来实现快速傅里叶变换这种运算的。本次我课程设计的题目是快速傅里叶变换的DSP实现方法，作为数字信号处理的一种算法，快速傅里叶变换日益广泛的应用于实时控制和信号处理等各个领域。快速傅里叶变换(Fast Fourier Transform)是实现离散傅里叶变换(DFT)的一种快速高效的运算方法，是数字信号处理中最为重要的工具之一。它使DFT的运算效率提高12个数量级，为数字信号处理技术

6、应用于各种高速信号的实时处理创造了良好的条件，从而大大推动了数字信号处理技术的发展。本次课程设计完成的是长度为256点的FFT运算，它的运算可以用一个流程图来描述，因为流程图的外形像一只蝴蝶，所以称之为蝶形图，一个蝶形图包含一次复乘，两次复加。通过计算蝶距和旋转因子就可画出每级的蝶形图。本次程序通过编写蝶距和旋转因子的子程序，每次都调用这两个子程序，就能计算出输入的数据所对应的输出。关键词 数字信号处理（DSP），快速傅里叶变换（FFT）目 录中文摘要I1 设计任务描述11.1 设计题目11.2 设计要求11.2.1 设计目的11.3 基本要求12 设计思路22.1 FFT算法的由来22.2

7、FFT算法原理22.3 基2FFT的蝶形运算流图32.4 时间抽取算法FFT的运算特点42.4.1 原位运算42.4.2 输入、输出序列的倒位序规律52.4.3 蝶距的计算52.4.4 旋转因子的计算62.5 FFT算法的DSP的实现方法62.6 FFT运算中应注意的问题63 软件流程图74 各部分程序设计及参数计算84.1 程序的初始化84.2 位反转子程序84.3 旋转因子的软件实现94.4 实现点复数FFT运算94.4.1 第一级蝶形运算104.4.2 第二级蝶形运算104.4.3 第三级第级蝶形运算114.4.4功率谱计算的实现134.5 参数计算145 程序的调试156 工作过程分析

8、166.1 程序的初始化166.2 位倒序子程序166.3 FFT计算166.4 功率谱的计算17小结18致谢19参考文献20附录A1 程序清单21附录A2 程序图形301 设计任务描述1.1 设计题目 快速傅里叶变换程序设计1.2 设计要求1.2.1 设计目的1）理解FFT的算法以及利用DSP实现的方法。2）能熟练的调试程序并能观察其结果。3）熟悉TMS320C54x系列DSP芯片的软件设计方法。1.3 基本要求1）研究FFT原理以及利用DSP实现的方法。2）编写FFT程序。3）调试程序，观察结果。2 设计思路2.1 FFT算法的由来傅里叶变换是数字信号处理领域中的一种分析工具，它可以将信号

9、从时域变换到频域，称之为傅里叶正变换，也可以把信号从频域变换到时域，称之为傅里叶逆变换。傅里叶变换分为连续傅里叶变换和离散傅里叶变换。离散傅里叶变换简称DFT（Discrete Fourier Transform），是对离散信号进行傅里叶变换的方法，其运算量大、复杂度与变换点数的二次方成正比，因而不适用于进行实时信号处理。为了提高DFT的运算速度，在20世纪60年代由Cooley和Turkey提出了快速傅里叶变换的思想，简称FFT（Fast Fourier Transform），它是一种高效实现DFT的算法，能够明显降低DFT运算的复杂度，使DFT得到了广泛的应用。2.2 FFT算法原理若给定

10、由个信号样本（0），（1），（-1）组成的信号序列（），DFT可用式2-1给出： =0,1，-1 （2-1）式2-1中，称为旋转因子或蝶形因子，=。从中可以看出：当信号样本为复数时，计算单个需经过次复数乘法和-1次复数加法运算，相当于4次实数乘法和2（2-1）次实数加法。完成全部点DFT共需次复数乘法和（-1）复数加法运算。可见，随着不断增加，整个DFT运算量是相当庞大的，而FFT算法通过对计算过程的深入分析，利用旋转因子具有的周期性与对称性，实现了降低运算复杂度的目的。当序列长度为偶数时，信号序列（）可被分解为奇、偶两个子序列，相应的点DFT被分解为两个/2点的DFT： =0,1, ，/2-

11、1 （2-2） =0,1, ，/2-1 （2-3）式（2-2）和（2-3）中，和分别表示（）分解后得到的/2点偶序列点奇序列的DFT。式（2-2）和式（2-3）表明，只要求出和，（）前/2点和后/2点的DFT就得到了，整个序列的DFT也就得到了。这样做的好处是计算点DFT只需要约/2次复数乘法，总运算量约为直接DFT运算量的一半同理，当/2为偶数时，每个/2点的DFT又可被分解成两个/4点的DFT，进一步减少了DFT运算的复杂度。依次类推，直到不能继续分解为止。分解结束时，最小DFT的点数称为称为基数，当=（为正整数）时，经过-1次分解，点DFT最终可被分解为/2个两点的DFT，即得到基数为2

12、的FFT运算，使得DFT所需复数乘法次数降至。2.3 基2FFT的蝶形运算流图基2FFT的蝶形运算过程可用图2-1所示，此时=8，=3。图2-1 8点基2FFT运算过程观察图2-1，根据DFT的基2FFT算法，可以总结出以下几条规律：（1）点FFT运算从输入端开始，逐级进行，共需经过级运算；在第（=1，2，）级中存在个相似的蝶形运算组（除输入数据不同外）；每个组内蝶形运算的个数为，参与每个蝶形运算的两个输入数据相距个点。（2）中间数据的存储，可采用原位存储法。即每次蝶形运算的结果存储在与原数据相同的内存单元内。（3）为了保证输出数据按自然数序排列，在进行FFT之前输入数据需要按照特定的顺序存放

13、，通过位倒序寻址可以满足这种要求。2.4 时间抽取算法FFT的运算特点快速傅立叶变换(FFT)算法基本上分为两大类：按时间抽取的FFT运算和按频率抽取的FFT运算。两者在算法的时间和空间复杂度上是一致的，只是序列在计算前后的排列有所不同。在本论文里，采用的是按时间抽取的FFT(DITFFT)算法。2.4.1 原位运算当数据输入到存储器中以后，每一级运算的结果仍然存储在同一组存储器中，直到最后输出，中间无需其它存储器，这叫原位运算。DITFFT的运算就是原位计算，从图2-2可以看出这种运算是很有规律的，每级（每列）计算都是由N/2个蝶形运算构成的，每一个蝶形结构完成下述基本迭代运算 （2-4）式中：m表示第m列迭代； 则分别为该蝶形单元两个输入数据所在行数。式（2-4）的蝶形运算如图2-2 所示。-1图2-2 按时间抽取算法基本蝶形运算单元由前面介绍过的完整的DIT-FFT运算流程图2-2可以看出，第级蝶形运算的输出数据仅与该级蝶形运算的输入数据有关，与前级蝶形的输入数据无关，且第级蝶形运算的输出数据为第级蝶形运算的输入数据。某任何一个蝶形运算的两个输入节点和的节点变量进行蝶形运算后，得到的结果为该蝶形运算两个输出节点，两节点的节