数字信号处理课程设计-FFT快速傅里叶变换程序设计.doc

快速傅里叶变换程序设计1中文摘要数字信号处理(DigitalSignalProcessing，DSP)是一门应用十分广泛的学科。数字信号处理是指利用计算机技术，以数字形式对信号进行采样、变换、滤波、估值、增强、压缩、识别等处理，以得到人们需要的信号形式。数字信号处理器也称DSP芯片，是一种用于进行数字信号处理运算的微处理器，其突出特点是采用多组总线技术实现并行机制，有独立的家发起和乘法器，灵活的寻址方式，实时快速地实现各种数字信号处理算法及各种复杂运算。傅里叶变换是一种将时域信号变换为频域信号的变换形式。在频域分析中，信号的频率及对应的幅值、相位（统称为频谱）反映了系统的性能。快速傅里叶变换(FastFourierTransform)是实现离散傅里叶变换(DFT)的一种快速高效的运算方法，是数字信号处理中最为重要的算法之一。FFT算法的关键在于利用了蝶形因子的内在对称性和周期性，从而加快了运算的速度，使运算时间缩短1至2个数量级。此次快速傅里叶变换的DSP程序设计，根据书上提供的C编程序在相对应的DSP工作环境下进行调试、图形分析、输入比较，来加深对程序的理解以及对所学内容的融合和巩固。程序设计所选择的头文件为，完成的是采样次数N为128的FFT运算。为了更好的观察到快速傅里叶运算的结果，还另外设计了一组为方波的输入，从而得到设计要求的FFT运算结果图形。关键词：数字信号处理，DSP芯片，快速傅里叶变换FFT，C语言程序快速傅里叶变换程序设计21设计任务描述1.1设计题目：快速傅里叶变换程序设计1.2设计要求1.2.1设计目的1）理解FFT的算法以及利用DSP实现的方法。2）能熟练的调试程序并能观察其结果。3）熟悉TMS320C54x系列DSP芯片的软件设计方法。1.3基本要求1）研究FFT原理以及利用DSP实现的方法。2）编写FFT程序。3）调试程序，观察结果。快速傅里叶变换程序设计32设计思路根据此次课程设计的要求，采用的是C语言程序。本次快速傅里叶变换程序设计主要包括三大部分：初始化定义部分，主函数部分，子程序部分。其中调用的子程序由四个功能函数组成：FFT初始化函数、计算功率谱函数、波形发生函数、倒序运算函数。这四个调用函数在主函数运行到相应位置时进入操作中，实现一个完整的快速傅里叶变换。由于在程序代码中调用了pow、log、cos、sin函数，该函数所在的C文件应包含头文件math.h。初始化定义部分主要是对程序需要用到的函数或者数据进行定义，这就需要我们熟悉前面知识所学到的各种基本数据类型的格式，如数组、结构、联合等构造类型数据。主函数部分就需要对FFT变换的整体过程有熟悉的了解，这样才能够知道应该调用的子程序的顺序。因为一旦程序开始运行，除了一开始的初始化阶段，直接进入的就是主函数部分。函数调用部分是整个程序的重点部分，在这里实现了波形的输入、FFT变换，可以通过CCS软件调试该程序，并用其中ViewGraphTime/Frequency菜单功能，显示变量INPUT与DATA图形，观察FFT的效果。在此次的程序设计中，我设计了正弦波和方波两种输入情况。对于不同的输入，经过FFT变换之后就会得到不同的频谱图，在整个程序中，FFT的变换过程是最大的难点，完成这部分需要对数字信号处理课程中的快速傅里叶变换的知识有很大程度的掌握，这样才能知道函数中倒序产生的原理与方法，并且对蝶形图中的运算也能相当了解，这样才能理清思路，利用C语言的字符语句达到倒序处理的目的。快速傅里叶变换程序设计43设计方框图设计方框图显现的是在设计时主要实现的功能和流程，简单易懂，能清晰的体现整个设计的思路。图3-1主程序流程结束程序初始化开始运行main()主函数调用InitForFFT初始化函数调用波形发生函数跳转到FFT程序在128个采样值内否输入波形是否在取点值范围内频谱值输出快速傅里叶变换程序设计54快速傅里叶变换的的算法实现4.1变换原理若给定由N个信号样本x（0），x（1），x（N-1）组成的信号序列x（n），DFT可用式2-1给出：10()()NnkNnXkxnWk=0,1，N-1（2-1）式2-1中，nkNW称为旋转因子或蝶形因子，nkNW=2/jnkNe。从中可以看出：当信号样本为复数时，计算单个()Xk需经过N次复数乘法和N-1次复数加法运算，相当于4N次实数乘法和2（2N-1）次实数加法。完成全部N点DFT共需2N次复数乘法和N（N-1）复数加法运算。可见，随着N不断增加，整个DFT运算量是相当庞大的，而FFT算法通过对计算过程的深入分析，利用旋转因子nkNW具有的周期性与对称性，实现了降低运算复杂度的目的。当序列长度N为偶数时，信号序列x（n）可被分解为奇、偶两个子序列，相应的N点DFT被分解为两个N/2点的DFT：()()()kNXkGkWHkk=0,1,，N/2-1（2-2）(/2)()()kNXNkGkWHkk=0,1,，N/2-1（2-3）式（2-2）和（2-3）中，G(k)和()Hk分别表示x（n）分解后得到的N/2点偶序列点奇序列的DFT。式（2-2）和式（2-3）表明，只要求出G(k)和()Hk，x（n）前N/2点和后N/2点的DFT就得到了，整个序列的DFT也就得到了。这样做的好处是计算N点DFT只需要约2N/2次复数乘法，总运算量约为直接DFT运算量的一半。同理，当N/2为偶数时，每个N/2点的DFT又可被分解成两个N/4点的DFT，进一步减少了DFT运算的复杂度。依次类推，直到不能继续分解为止。分解结束时，最小DFT的点数称为称为基数，当N=2L（L为正整数）时，经过L-1次分解，N点DFT最终可被分解为N/2个两点的DFT，即得到基数为2的FFT运算，使得DFT所需复数乘法次数降至2(/2)logNN。快速傅里叶变换程序设计64.2蝶形运算基于2FFT的蝶形运算流图如下图4-1所示，图中以N=8为例。图4-1蝶形运算采用的是原位运算原理和倒位序规律，其中原位运算指的是某一列的N个数据送到存储器后，经蝶形运算，其结果为下一列数据，它们以蝶形为单位仍存储在这同一组存储器中，直到最后输出，中间无需其他存储器。也就是蝶形的两个输出值仍放回蝶形的两个输入所在的存储器中。每列的N/2个蝶形运算全部完成后，再开始下一列的蝶形运算。而倒位序规律则是根据二进制的自然顺序和倒序得来的，其变换规律如图4-2。自然顺序（I）二进制数倒位序二进制数倒位序（J）0123456700000101001110010111011100010001011000110101111104261537图4-2x(0)X(0)x(4)X(1)10NWx(2)X(2)x(6)X(3)10NW0NW2NW11x(1)X(4)x(5)X(5)10NWx(3)X(6)x(7)X(7)10NW0NW2NW110NW1NW2NW3NW1111快速傅里叶变换程序设计75各部分程序设计5.1初始化程序#includemath.h/数学函数头文件#definePI3.1415926#defineN128/采样次数NvoidInitForFFT()；/FFT初始化函数voidMakeWave()；/波形发生函数voidfinv(intN1,float*xr,float*xi)；/倒序运算函数，对输入序倒序intINPUTN,DATAN；floatfWaveRN,fWaveIN,wN；floatsin_tabN,cos_tabN；/正余弦函数表intMum；/蝶形运算的级数这一段初始化程序是对需要用到数据和子程序段进行定义，其中包含了采样的次数、蝶形运算的级数，倒序运算正余弦函数表。5.2FFT的蝶形运算在进行蝶形变换的时候，其中还引入了倒序运算函数，即运算完之后的FFT的输出X(k)按正常顺序排列在存储单元中，即按X(0)，X(1)，X(7)的顺序排列，但是这时输入x(n)却不是按自然顺序存储的，而是按x(0)，x(4)，x(7)的顺序存入存储单元，看起来好像是“混乱无序”的，实际上是根据倒序原理：倒序数的加1是在最高位加1，满2向次高位进1，最高位变0，依次往下，从当前的倒序值求出下一