课程设计（论文）-快速傅里叶变换程序设计

1、1设计任务描述1.1设计题目快速傅里叶变换程序设计1.2设计要求121设计目的1）理解fft的算法以及利用dsp实现的方法。2）能熟练的调试程序并能观察具结果。3）熟悉tms320c54x系列dsp芯片的软件设计方法。1.3基本要求1）研究fft原理以及利用dsp实现的方法。2）编写fft程序。3）调试程序，观察结果。2设计思路2.1 fft算法原理若给定出n个信号样本x (0),兀(1),，兀(nl) 组成的信号序列兀(n ), dft可用式21给岀：n-1x (k) = x(n)wk k 二0, 1 ,n -1n=o(2-1)式21中，w腭称为旋转因子或蝶形因子，wk = ejm/n。从中

2、可以看叽 当信号样本为复数时，计算单个x伙)需经过n次复数乘法和n1次复数加法运 算，相当于4n次实数乘法和2 (2n1)次实数加法。完成全部n点dft共需 tv?次复数乘法和n (7v-1)复数加法运算。可见，随着n不断增加，整个dft 运算量是相当庞大的，而fft算法通过对计算过程的深入分析，利用旋转因子 w护具有的周期性与对称性，实现了降低运算复朵度的目的。当序列长度n为偶数时，信号序列兀(几)可被分解为奇、偶两个子序列，相应的n点dft被分解为两个n /2点的dft：x伙)=g+敝/7伙)k =0, 1,，n /2-1(2-2)x(n/2 + k) = g伙)伙)k 二0,1,，n /

3、2-1(2-3)式(2-2)和(2-3)中，g(k)和h伙)分别表示x (“)分解后得到的n/2点偶序 列点奇序列的dfto式(2-2)和式(2-3)表明，只要求出g(k)和h伙)，兀(«) 前w/2点和后n/2点的dft就得到了，整个序列的dft也就得到了。这样做 的好处是计算n点dft只需要约"2/2次复数乘法，总运算虽约为直接dft运 算量的一半同理，当n/2为偶数时，每个n/2点的dft 乂可被分解成两个n/4点的dft,进一步减少了 dft运算的复杂度。依次类推，直到不能继续分解为止。 分解结束时，最小dft的点数称为称为基数，当n = 2(乙为正整数)时，经 i

4、ll-1次分解，n点dft最终可被分解为n/2个两点的dft,即得到基数为2 的fft运算，使得dft所需复数乘法次数降至（nlogj。2.2基2fft的蝶形运算流图观察图21,根据dft的基2fft算法，可以总结出以下儿条规律：（1）n点fft运算从输入端开始，逐级进行，共需经过厶级运算；在第加（m=l, 2,，m ）级屮存在个相似的蝶形运算组（除输入数据不同外）; 每个组内蝶形运算的个数为2w-',参与每个蝶形运算的两个输入数据相距2心个 点。（2）屮间数据的存储，可采用原位存储法。即每次蝶形运算的结果存储在 与原数据相同的内存单元内。（3）为了保证输出数据按自然数序排列，在进行f

5、ftz前输入数据需要按 照特定的顺序存放，通过位倒序寻址可以满足这种要求。2.2.1输入、输出序列的倒位序规律由流程图21可以看出，当进行原位运算时，发现当运算完成后，fft的输tbx按自然顺序排列在存储单元中，即按x（0）, x（l）,，x（7）的顺序排 列；但是这是输入兀(防却不是按自然顺序存储的,而是按兀(0),兀(4), ，x(7) 的顺序存入存储单元，这种方式就称之为倒位序。当用二进制表示这个顺序时，它正好是“码位倒置”的顺序。例如，原来的 自然顺序应是兀的地方，现在存放x(4),用二进制码表示这一规律时，则是在 x(001)处存放兀(100),班011)出存放兀(110),即将自然

6、顺序的二进制码位倒置过 来，第一位码变成最末位码，这样倒置以后的顺序正是输入所需要的顺序。表 2-1中列出的是n詣 时按码位倒置规律所得的顺序，其结果与按时间抽取算法 fft流程图中的输入顺序是一致的。同理，当w二256时，亦可以采用同样的方 法进行位倒序操作。表2-1码位倒置顺序自然顺序二进码表示码位倒置倒位序00000000100110042010010230111106410000115101101561100113711111172.2.2蝶距的计算设n = » ,则整个运算流图中包含厶级蝶形运算，每一级则有n/2个蝶形单元。蝶距即每个蝶形单元两个输入(出)节点的序号差。以n

7、 = 8为例，结合 图21可知共包含3级蝶形运算，每一级蝶形单元的蝶距如下：第一级，蝶距为1, 可以看作由21-1 = 2°得到：第二级，蝶距为2,可以看作由22-1=2,得到；第三级,蝶距为4,可以看作由23'1 = 22得到。因此得：第加级蝶形单元的蝶距为:2心。2.2.3旋转因子的计算由fft算法原理过程可知，若n = 2l,则共有厶级蝶形运算，各级蝶形运算中旋转因子分别如下：第厶级的旋转因子为（厂二0,1,，n/2-1）；第乙1级的旋转因子为w（/2 （厂二0,1,，n/22-l） ； ；第一级的旋转因子为叭才（广二0, 1,，/v/2l-1） o由此可见，第加级蝶形

8、运算屮旋转因子为w；/2“， r=o, 1,，n/2"】1。2.3 fft算法的dsp的实现方法设fft运算的输入数据为实数，则2n点实数fft算法的实现步骤为：第 一步，把2 n实数输入序列纟fl合成n点的复数序列。然后把该复数序列进行位 倒序操作后存储在输入区。第二步，进行n的fft运算。第三步，把n点fft 输出拆成2n的复数序列，这2n的复数序列对应于2n点时实数输入序列的 dft输出。第四步，结果输出及功率谱计算。3软件流程图4各部分程序设计及参数计算4.1初始化程序#i ncludemath. httdefine pi 3.1415926define n 128void

9、initforfft ();void makewaveo ;void finv (int nl, floa.t *xr, float *xi);int inputn, datan;float fwavcrn,fwaveln, wn;float sin_tabn, cos_tabn;int mum;初始化程序是对采样点数n、各个子程序、数据实部和虚部、输入输出以及正余 弦表进行定义，在后面的程序屮运用时就不用再进行定义了。4. 2子程序4.2.1旋转因子、蝶距运算voi d fft(float xrn, float xin)int s, b;int m, j, k； float x, y; f

10、inv(n, xr, xi);for (m=1;m<=mum;m+)b= (int) (pow(2, ml)+0. 5);for(j=0;j<b;j+)s二 j*(int) (pow(2, mum-m)+0. 5);for (k=j; k<=n-l; k+= (int) (pow (2, m) +0. 5)该子程序是时间抽取法fft程序，要求采样点数为2的整数幕次方，xr 和xi 分别为输入序列的实部和虚部。s为旋转因子的幕数，b为蝶形图运算输 入数据的距离，也即各级旋转因子的个数。finv(n,xr,xi)语句是实现倒序运算 函数,对输入序列倒序。b=(int) (pow(

11、2, m-1)+0. 5)语句计算出蝶距b二2飞旷1), s=j*(int) pow (2, mum-m) +0. 5 语句计算出旋转因了的幕数 s二2八(num-1)。4.2.2蝶形图变换x=xrk+b*cos_tabs+xik+b*s in_tabs;y二xik+b*cos_tabs-xrk+b*sin_tabs;xrk+b=xrk-x;xi k+b二xik-y;xrk=xrk+x;xik二xik+y;该段子程序是实现蝶形图的变换，蝶形运算展开，结果的实部和虚部分别 存储在原实部和虚部位置。4.2.3波形发生函数void makewaveoint i; int j; int 1;for (

12、i=0;i<n;i+)j=(int)i/20;l=j%2;if(l=0)inputi=1024;else inputi=0;该程序是实现输入波形为方波，从0点开始20个点一个高电平，20个点一个低 电平。4. 2.4倒序void finv(int nl, float *xr, float *xi)int m, n, n2, k;float t;n2二nl/2;n 二 n2;for (m=1;m<=nl-2;m+)if (mn)t=xrm;xrm=xrn;xrn=t;t二xim;xim二xin;xin=t;k=n2;while (n>=k)n=nk;k=(int) (k/2+0

13、. 5);n二n+k;该程序段是倒序运算函数finv (nl, xr, xi),对输入序列倒序。n1为序列长 度；xr,xi分别为输入序列的实部和虚部。倒序原理：倒序列的加1实在最咼位加1,满2向次咼位进1,最咼位变0, 依次往下，从当前倒序值可求得下一倒序值。4. 3主程序main()initforfft ();makewave (); for (i=0;i<n;i+)fwaveri=inputi; f wave i i=0. 0;wi二0. 0;mum二(int) (0. 5+log (n)/log(2);fft (fwaver, fwavel); for(i=0;i<n;i

14、+)data订二wi; while；主程序的功能是调用各个子程序，mum二(int) (0. 5+log(n)/log(2)语句中mum 为蝶形运算的级数，n二2飞um。num二7。小结在这次设计中，我完成了这次任务，在一周的课设中，我弄懂了快速傅里叶 变换程序设计，并且调试出该程序的输入输岀波形以及功率谱。在这次课程设计屮，我学到了很多上课时没有学到的知识。这次设计的程序 是关于快速傅里叶变换的，在设计程序z前得先弄明口快速傅里叶变换的理论知 识，我翻阅了上学期学的数字信号处理，弄明口了该程序要实现的功能。然后把 整个程序分成好几个模块，先读懂每个模块，再把程序结合在一起，最后终于弄 懂了整

15、个程序。在程序的调试过程屮我遇到了许多困难。首先，在编译时有两个 错误是认为因素造成的，有一个是因为把指令的拼音打错了，还有一个是因为在 程序的最开始多留出一行，由于dsp的汇编指令要求非常严格，所以在编写程序 时应该注意书写的格式。通过课程设计我收获很多，不仅对这个课程有了更深的理解，而且也学会了 团队精神的重耍性，个人的能力是有限的，团结才能有力量，我们都尽自己所能 来完成这次课程设计。通过这次课程设计，我懂得了理论与实际结合是很必要的。 只有理论知识是远远不够的，只有把所学的理论知识与实际结合起来，从理论屮 得岀结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考能力。 重要的

16、是我们在设计过程屮发现了自己的不足，对前面学过的知识理解的不够深 刻，掌握的不够牢固。通过这次课程设计，我们相当丁把前而所学过的知识乂重 新温故了 一遍。致谢课程设计结束了，在课程设计的过程中我学到了很多课堂上所不能体会的知 识。我们做的是快速傅里叶变换程序设计，在这次设计当中，我学会了团体合作 还有很多关于dsp的相关知识。一周的课程设计结束了，以前在上课的时候老师 讲解的东四以为明白就可以，但是在这次实践屮，我明白了，那是远远不够的。在老师、同学的帮助下，终于完成了这次实验。查阅资料，请教同学，相互 讨论，还好有老师和同学，一步一步的修改和讲解让我觉得非常的暖心。可能在 以后步入社会以后这

17、种感觉可能不复存在。所以我珍惜现在的每一次的设计。在这里要非常感谢我的老师。每天都来实验室为同学们解答各种问题，当我 们出错误的时候，老师都会在身边所以我们感到非常的安心。这也是一次跟老师 更加近距离的学习机会。在这里还要感谢我同组的同学以及帮助我们的同学。在每天的课程设计中， 都有你们的陪伴，在我有困难的时候，你们永远在我的身边。非常谢谢你们对我 的帮助。这次课程设计对我以后的学习乃至工作都有很人的帮助，我对dsp有了更 深一层次的了解。虽然对程序设计还是有很多困难，很多要学的。但我想只要我 们珍惜每次设计的经过，从屮我们肯定会有一些所得。再次感谢我们的指导老师，还有曾经一直帮助我的同学。参

18、考文献1 俞一彪，孙兵.数字信号处理理论与应用南京：东南大学出版社,20052 李行一.数字信号处理重庆：重庆大学出版社，20023 郭森楙，颜允圣.数字信号处理器体系结构、实现与应用.北京：清华 大学出版社，2005姜沫岐，许涵，俞鹏，段国强.dsp原理与应用一从入门到提高.北 京：机械工业出版社，20075 俞卞章.数字信号处理西安：西北工业人学出版社，20026 王安国.数字信号处理基础北京：电子丁业出版社，2003附录a1程序清单#include，zmath. h ttdefine pi 3.1415926 itdefine n 128 void initforfft();voi d

19、makewave();void finv(int nl, float *xr, float *xi);int inputn, datan;float fwavern,fwavein, wn;float sin_tabn, cos_tabn; int mum;void eft(float xrn, float xin)int s, b;int m, j, k;float x, y;finv(n, xr,xi);for(m=1;m<=mum;m+)b=(int) (pow(2, m-l)+0. 5);for(j=0;j<b;j+)s=j*(int) (pow(2, mum-m)+0. 5);for (k=j; k<=nl; k+二(int) (pow (2, m) +0. 5)x=xrk+b*cos_tabs+xik+b*s in_tabs; y=xik+b*cos_tabs-xrk+b*sin_tabs; xrk+b=xrk-x;xik+b=xik-y;xrk=xrk+x;x 订 k二x 订 k+y;for (m=0;m<