基于dsp的快速傅里叶变换算法

基于dsp的快速傅里叶变换算法内容摘要：

置顺序的存储，这样就可以进行FFT的原位运算。 变址的功能如图24所示。 用软件实现是通用采用雷德（Rader）算法，算出的倒序以后立即将输入数据和对换。 尽管变址运算所占运算量的比例很小，但对某些高要求的应用（尤其在实时信号处理中），也可设法用适当的电路结构直接实现变址。 例如单片数字信号处理器TMS320C25就有专用于FFT的二进制码变址模式。 图24 码位倒置的变址处理01234567X（0）X（4）X（2）X（6）X（1）X（5）X（3）X（7）在这里，我想简单的介绍一下其他的算法，为了开发创新思维，开创改进新算法等。 在FFT算法中，除基2FFT算法外，混合计算法也尤为实用。 当的情况一般可有以下两种处理方法：（1）将用补零的方法延长，使N增长到最邻近的一个数值。 例如，N=30，可以在序列x(n)中补进x(30)=x(31)=0两个零值点，使N=32。 如果计算FFT的目的是为了解整个频谱，而不是特定频率点，则此法可行。 因为有限长序列补零以后并不影响其频谱，只是频谱的采样点数增加而已。 （2）如果要求特定频率点的频谱，则N不能改变。 如果N为复合数，则可以用以任意数为基数的FFT算法来计算。 快速傅里叶变换的基本思想就是要将DFT的运算尽量分小。 例如，N=6时，可以按照分解，将6点DFT分解为3组2点DFT。 本章小结在学习离散傅里叶变换的基础上，研究快速傅里叶变换的原理，掌握了快速傅里叶变换的几种算法，并深入学习了以基2FFT算法为主结合混合基的算法，为下面的程序编写和研究奠定了基础。 第3章 软件设计 算法设计和程序编写 算法设计流程根据快速傅里叶变换的算法和DSP上的实现规律的研究和学习。 可以绘出编程用的程序框图[4]如图31所示：程序说明：：①序列倒序程序；②第一级蝶形运算；③第二级蝶形运算；④第三级至第级的蝶形运算；⑤求功率谱及输出程序。 开始送入x(n)倒序L=1，MJ=0,B1输出结果结束图31 程序流程框图 程序编写DSP软件设计多用于算法比较复杂、乘加运算量比较大的场合,如通信、雷达、音视频处理等。 为了追求代码的高效性,以前大都用汇编语言来编DSP的应用软件。 随着DSP的应用范围不断延伸，单纯的汇编语言程序的难读性、难移植性、难修改性等缺点日益突出。 C语言以其独特的可读性、可修改性和可重用性，使DSP的运算速度大幅提高。 用C语言进行DSP软件设计，其效率一般低于汇编语言编制，这是因为汇编语言是低级语言，形成目标代码的速度比C语言快，因此，用C语言进行软件设计时，优化设计显得尤为重要。 鉴于DSP应用复杂性，用C语言进行软件开发时，一般先在PC上对算法进行仿真，然后将程序移植到DSP平台中。 由于DSP程序需要首先使用高级语言来模拟算法性能，对于本次设计题目基于DSP的快速傅里叶变换算法，采用C语言编程。 整个程序的编写过程[5]如下：（1）首先定义一个复数结构。 struct px{double }。 （2）定义一个输入数据序列。 struct px xin{N1}。 （3）定义两个复数相乘。 struct px EE（struct px b1,struct px b2）{struct px b3。 =**。 =*+*。 Return(b3)。 }（4）定义位反函数Void displace(void)。 {....nv2=N/2。 For(i=1。 i=nm1。 i++){if(ij){t=xin[j]。 xin[j]=xin[i]。 xin[i]=t。 }k=nv2。 While(kj){j=jk。 K=k/2。 }j=j+k。 }（5）定义FFT变换的函数。 Void FFT(void){.....For(l=1。 l=m。 l++){lt=pow(2,1)。 Lei=le/2。 Pi=。 =。 =。 =cos(pi/lei)。 =sin(pi/lei)。 For(j=1。 jlei。 j++){for(i=j。 i=N。 i=i+le){ip=i+lei。 T=EE(xin[ip],v)。 Xin[ip].real=xin[i].real=。 Xin[ip].imag=xin[i].。 Xin[i].real=xin[i].real+。 Xin[i].imag=xin[i].imag+。 }V=EE()。 }}}（6）：wstack 400hheap 100l MEMORY{ PAGE 0: VECT : o=80h,l=80h PRAM : o=100h,l=1f00h PAGE 1: DRAM : o=2000h,l=1000h }SECTIONS{ .text : {} PRAM PAGE 0 .data : {} PRAM PAGE 0 .cinit : {} PRAM PAGE 0 .switch : {} PRAM PAGE 0 .const : {} DRAM PAGE 1 .bss : {} DRAM PAGE 1 .stack : {} DRAM PAGE 1 .vectors: {} VECT PAGE 0 }注：整体程序见附录 CCS开发环境的使用及软件仿真 CCS开发环境的使用TI公司提供多种开发工具，可以快速实现基于DSP的应用设计，从概念到编码/编译，调试，通过分析，校正，并以测试。 许多工具都是TI的实时ExpressDSP™软件和开发工具策略的一部分，这对设计过程中快速起步及节省宝贵时间非常有帮助。 TI的实时Express DSP软件及开发工具策略包括三个组件，使开发者能够充分利用的TMS320™系列DSP潜能。 Code Composer Studio IDE是强大的DSP集成开发工具，利用CCS开发环境可以实现对设计的软件仿真。 针对所选择DSP芯片TMS320C5416芯片选择CCS的型号，本次设计采用CCStudio。 在进入CCS开发环境前，必须选择一个合适的配置环境。 进入配置设定软件Setup CCStudio。 使用标准配置文件产生一个系统配置： （1）双击桌面上的Setup Code Composer Sutdio图标，出现系统配置配置对话框。 （2）从available factory board中选择与系统匹配的标准设置。 确定可用配置中是否存在与系统匹配的配置，如图32所示图32 CCS配置环境图（3）单击选择的配置，然后单击ADD按钮将选择的配置添加到system configuration中。 这样选择的配置就出现在系统配置方框中My System图标下面。 如果你的配置包含多于一个的目标板，重复以上步骤直到你为每一个目标板选择了一个配置。 （4）单击Save amp。 Quit按钮保存配置。 （5）单击Yes按钮，启动配置好的CCS集成开发环境。 现在可以打开一个工程。 进入CCS开发环境后，可以建立一个新的工程也可以直接打开一个已有的工程。 按照以下步骤创建一个新工程：（1）如果CCS安装在C:\，在C:\\myprogects文件下新建一个practice文件夹。 （2）把C:\\tutorial\target\consultant文件夹下的内容复制到新建的文件夹里。 目标与当前CCS的配置有关。 在使用CCS前必须进行配置，CCS里没有默认的配置。 （3）选择ProjectNew。 （4）在Project Name框里输入工程名：(例如:practice)。 （5）在Location框里输入或者浏览第一步创建的文件夹。 （6）工程类型默认为可执行的(.out)文件，目标设置为CCS当前的配置。 （7）点击Finish。 文件里存储了工程配置和工程所需要的各种相关文件。 （8）选择ProjectAdd files to Project，把文件加到工程里。 你也可以在左边的工程视图窗口里右击工程，选择Add files to Project。 （9），(映射内存的连接命令文件)。 浏览C:\\c6000\cgtools\lib\目录。 （10）不必手工添加包含文件到工程里，因为编译程序的时候，程序会自动找到它们。 在编译一个工程后，包含文件会出现在工程视图里。 创建工程后，打开C语言程序，，显示没有错误后构建程序。 第一次使用全构建（Build All）功能便可以构建工程，以后可以使用增量构建（Build the project incremental）。 当构建完成后，输出窗口将会显示Build plete 0 errors，0 warnings。 当工程选项或所有文件发生改变后，执行Rebuild All命令重建工程。 程序成功构建后，执行FileLoad Program加载程序。 加载过程是将上述构建成功，生成的可执行文件加载到目标板，目标板可以是软件仿真环境，也可以是硬件目标板。 默认情况下，CCS集成开发环境将会在你的工程路径下创建一个Debug子目录。 点击Open加载程序。 加载完成后，完成一些基本调试以便在实践中体会CCS的功能强大的调试器（debugger）。 选择DebugGo main开始Main函数的执行。 执行到Main函数出暂停，此时程序指针（黄色箭头）停在Main函数的左边空白处。 这个区域被称为选择区域(select margin)。 可以在这个区域设置断点（break point），探针(probe)等。 把光标置于所需行上，按F9设置一个断点。 此外，你还可以通过选择Toggle Breakpoint工具条按钮创建断点。 设置断点后，一个红色图标将出现在选择空白区。 再按F9或Toggle Breakpoint按钮将除去断点。 ，在DoLoop行设置断点（Input1，Input2，Weights，Output，LOOPCOUNT）当程序暂停在Main函数处时，通过按F5，选择DebugRun，或者选择Run工具条来运行程序。 一旦程序运行到断点出，程序将挂起。 只有当程序执行挂起后才可单步执行。 当程序在断点处挂起后，便可以单步执行程序。 通过选择SourceSingle Step按钮，单步执行到DoLoop函数中。 多次单步执行观察执行结果。 在Single Step按钮下，还有Step Over和Step Out可用。 同样也可以使用汇编单步。 因此，源程序单步逐行各代码，汇编单步执行各条汇编指令。 在调试过程中，你应该查看变量的值以确保程序正常的执行。 当CPU被挂起时，可以在watch窗口里观察变量的值。 通过选择ViewWatch Window可以打开watch窗口。 Watch Locals条目下显示当前执行的相关变量值。 当你连续单步执行整个循环时，变量的值会随之改变。 此外，还可以通过把鼠标指针浮于变量上或把变量添加到Watch1 Tab里，来观察某个具体变量的值。 CCS软件仿真CCS IDE可以通过各种方法把程序处理到的数据画出来，包括时间/频率，星座图，眼图和图像。 选择View Graph，可以得到这些图，然后选择需要的图。 这时候可以在图属性（graph property）的对话框中指定图的属性选项。 下面的例子展示了一个单时刻(时间/频率)图表属性对话框。