快速傅里叶变换(FFT)的DSP实现

1、目录1、 前言2、 设计题目3、 设计要求3.1 设计目的3.2 设计要求4、 设计内容5、 设计原理5.2 离散傅里叶变换dft5.3 快速傅里叶变换fft6、 总体方案设计6.1 设计有关程序流程图6.2 在ccsm境下加载、调试源程序7、 主要参数8、 实验结果分析9、 设计总结一、前言随着数字电子技术的发展，数字信号处理的理论和技术广泛的应用于通讯、 语音处理、 计算机和多媒体等领域。 快速傅里叶变换（ fft）使离散傅里叶变换的时间缩短了几个数量级。 在数字信号处理领域被广泛的应用。fft已经成为现代化信号处理的重要手段之一。本次课程设计主要运用 ccs这一工具。ccs（code c

2、omposer studio） 是一种针对tm320系列dsp的集成开发环境，在 windows操作系统 下，采用图形接口界面，提供环境配置、源文件编辑、程序调试、跟踪和分析等工具，可以帮助用户在一个软件环境下完成编辑、编译、链接、调试和数据分析等工作。ccs有两种工作模式，即软件仿真器和硬件在线编程。软件仿真 器工作模式可以脱离dsp芯片，在pc上模拟dsp的指令集和工作机 制，主要用于前期算法实现和调试。硬件在线编程可以实时运行在dsp芯片上，与硬件开发板相结合进行在线编程和调试应用程序。二、 设计题目快速傅里叶变换（fft的dsp实现三 、 设计要求3.1 设计目的加深对dft算法原理和

3、基本性质的理解； 熟悉fft的算法原理和fft子程序的算法流程和应用；学习用fft对连续信号和时域信号进行频谱分析的方法； 学习dsp中fft的设计和编程思想；学习使用ccs勺波形观察器观察波形和频谱情况;3.2 基本要求研究fft原理以及利用dsp实现的方法；编写fftw序；调试程序，观察结果。设计内容用dsp汇编语言及c语言进行编程；实现fft运算、对输入信号进行频谱分析。五、 设计原理快速傅里叶变换fft快速傅里叶变换(fftd是一种高效实现离散傅里叶变换(dft 的快速算法，是数字信号处理中最为重要的工具之一，它在声学，语音，电信和信号处理等领域有着广泛的应用。5.1 离散傅里叶变换d

4、ft对于长度为n的有限长序列x(n),它的离散傅里叶变换(dft)为 n1x(k)x(n)wnnk ,k 0,1, n 1n 0(1)式中，wne j 2 / n ，称为旋转因子或蝶形因子。从dft的定义可以看出，在x(n)为复数序列的情况下，对某 个k值，直接按(1)式计算x(k)只需要n次复数乘法和(n-1)次 复数加法。因此，对所有n个k值，共需要n2次复数乘法和n(n-1) 次复数加法。对于一些相当大有n 值(如 1024 点)来说，直接计算它的dft所需要的计算量是很大的，因此dft运算的应用受到了很大的限制旋转因子 wn 有如下的特性。wnk n/2对称性：wnkwk周期性： wn

5、利用这些特性，既可以使又可以将长序列的5.2 快速傅里叶变换fft既可以使 dft中有些项合并，减少了乘法积项，dft分解成几个短序列的dft fft就是利用了旋 转因子的对称性和周期性来减少运算量的。fft的算法是将长序列的dft分解成短序列的dft)例如：n为偶 数时，先将n点的dft分解为两个n/2点的dft,使复数乘法减少一 半：再将每个n/2点的dft分解成n/4点的dft,使复数乘又减少一 半，继续进行分解可以大大减少计算量。最小变换的点数称为基数，对于基数为2的fft算法，它的最小变换是 2点dft一般而言，fft算法分为按时间抽取的 fft(dit fft)和按 频率抽取的ff

6、t ( dif fft两大类。d if fft法是在时域内将每 一级输入序列依次按奇/偶分成2个短序列进行计算。而dif fft算法是在频域内将每一级输入序列依次奇/偶分成2个短序列进行计 算。两者的区别是旋转因子出现的位置不同，得算法是一样的。在 kdif fft算法中，旋转因子wn出现在输入端，而在dif fft算法中它出现在输入端。假定序列x(n)的点数n是2的哥，按照dif fftt法可将其分为偶 序列和奇序列。偶序列：x(0), x(2), x(4), x(n -2),mpx1x(2r),r0,1, n/2 1奇序列：x(1), x(3), x(5), x(n -1)jpx2x(2r

7、 1),r0,1, n /2 1则x(n)的dft表示为n1n1x (k)x(n)wnnkx(n)wnnkn0n0n为偶数 n为奇数n /2 1x(2r)wn2rkr0n /2 1x1(r)wn2rkr0n/2 1x(2r 1)wn(2r 1)kr0n/2 1(2)wnkx2 (r)wn2rkr0由于wn2可表不为j(2 /n)ee j 2 /( n / 2)wn / 23)式x(k)n/2 1x1(r)wnrk/2r0n/2 1wnkx2 (r)wnrk/2r0x1(k) wnkx2(k)k 0,1,n/2 1(3)式中，x1(k)和x2(k)分别为x1和x2(n)的n/2的dft由于对称性

8、，wnk n/2wnk , 则 x (k n /2) x 1(k)wnkx2(k) 。因此， n点 x(k) 可分为两部分：前半部分： x(k) x1(k) wnkx2(k)k 0,1, n/2 1(4)后半部分： x (k n /2) x1(k) wnkx2 (k)k 0,1, n / 2 1(5)从式(4)和式(5)可以看出，只要求出0n/2-1区间x1(k)和x2(k)的值，就可求出 0n-1 区间 x(k) 的 n 点值。以同样的方式进行抽取，可以求得n/4点的dft,重复抽取过程， 就可以使n点的dft用上组2点的dft来计算，这样就可以大减少 运算量。基2 dif fft的蝶形运算

9、如图(a)所示。设蝶形输入为xm1(p)和 xm1，输出为xm(pjdxm(q),则有kxm( p) xm 1 (p) xmi(q)wn(6).kxm (q) xm 1 ( p) xm i(q )vn( 7)在基数为2的fft中，设n=2m,共有m级运算，每级有n/2个 2点fft蝶形运算，因此，n点fft总共有(n/2)l0g2 n个蝶形运算。xm(p)xm(q)图(a)基2 dif fft的蝶形运算例如：基数为2的fft当n=8时，共需要3级，12个基2 dit fft的蝶形运算。其信号流程如图(b)所示图（b） 8 点基2 dif fft蝶形运算从图（b）可以看出，输入是经过比特反转的倒

10、位序列，称为位码倒置，其排列顺序为x（0）,x（4）,x（2）,x（6）,x（1）,x（5）,x（3）,x（7）o输出是按自然顺序排列，其顺序为 x（0）,x（1）, ,x（6）,x（7）o六、总体方案设计6.1 设计程序流程图6.2 在cc/境下加载、调试源程序(1)起动ccs在ccs中建立一个工程文件 projectnewfft,往工程文件里添加程序sourcefile.建立c源文件和一个命令文件，并将这 两个文件添加到工程，再编译并装载程序:阅读dsp原理及应用中fft用dsp实现的有关程序。双击s乱叫ccs 2 c cooa) l快捷方式,启动ccs的仿真平台的配着选项。选择c5510

11、 simulator。add 力口至u my system 按下 savesy&ten corriguralionmm.c.tl. cstndii a 5”fl 1ft id: t 17 helpffe-ivftiiihl* aelory b小ard曲|c5母引sinu ihali 11qce502 dttlcb siwqlotwcs&thsim.fcbcssio ottl c sinulatcr cs&cxsin.*时/* vpn?4?n fi rssifw*jc55xx r*v2. i cfij cy .c5fkxim.串“：c55xk rtv2, i cfij fu .csemmmi力.

12、*mcs5kx rs 0 cru cy .cjckx式玉；*:邙也* rev3, 0 cfij fu .c5=kssim.*.factory bcudi 冉 cumton 5公/ or唾t*、卜 xdj ： add 2tm(2)启动c5510后打开文件fft.pjt将编写好的源程序，和命令文件加载到文件fft.pjtsource.(3)按下projectbuild调试程序，看其中是否有错误 fft.pjt - debugbuild complete,0 errors, 0 warnings, 0 remarks.(4)无错后，debugrun运行fft.out程序。fft.p广 - dehuf

13、j(5)通过graph property dialog窗口，改变n点的值，得到不同的结 果。七.主要参数进行n点fft运算，分别实现n=256,n=512得到不同的功率谱图六.源程序：cmd源文件代码:-f 0-w-stack 500-sysstack 500-l rts55.libmemorydaram: o=0x100, l=0x7f00vect:o=0x8000, l=0x100daram2:o=0x8100,l=0x7f00saram: o=0x10000,l=0x30000sdram:o=0x40000,l=0x3e0000sections.text: daram.vectors:

14、vect.trcinit:daram.gblinit:daram.frt:daram.cinit:daram.pinit:daram.sysinit:daram2.far:daram2.const:daram2.switch:daram2.sysmem:daram2 .cio:daram2.mem$obj:daram2.sysheap:daram2.sysstack:daram2.stack:daram2.input:daram2.fftcode:daram2c文件源码：#include math.h#define sample_1 256#define signal_1_f 60#defin

15、e signal_2_f 200#define signal_sample_f 512#define pi 3.1415926int inputsample_1;float fwaversample_1,fwaveisample_1,wsample_1;float sin_tabsample_1;float cos_tabsample_1;void init_fft_tab();void input_data();void fft(float datarsample_1,float dataisample_1);void main()int i;init_fft_tab();input_dat

16、a();f or (i=0;isample_1;i+)fwaveri=inputi;fwaveii=0.0f;wi=0.0f;fft(fwaver,fwavei);while(1);void init_fft_tab()float wt1;float wt2;int i;for (i=0;isample_1;i+)wt1=2*pi*i*signal_1_f;wt1=wt1/signal_sample_f;wt2=2*pi*i*signal_2_f;wt2=wt2/signal_sample_f;inputi=(cos(wt1)+cos(wt2)/2*32768;void input_data(

17、)int i;for(i=0;isample_1;i+)sin_tabi=sin(2*pi*i/sample_1);cos_tabi=cos(2*pi*i/sample_1);void fft(float datarsample_1,float dataisample_1)int x0,x1,x2,x3,x4,x5,x6,x7,xx;int i,j,k,b,p,l;float tr,ti,temp;for(i=0;isample_1;i+)x0=x1=x2=x3=x4=x5=x6=0;x0=i&0x01;x1=(i/2)&0x01;x2=(i/4)&0x01;x3=(i/8)&0x01;x4=

18、(i/16)&0x01;x5=(i/32)&0x01;x6=(i/64)&0x01;x7=(i/128)&0x01;xx=x0*128+x1*64+x2*32+x3*16+x4*8+x5*4+x6*2+x7;dataixx=datari;)for(i=0;isample_1;i+)(datari=dataii;dataii=0;)for(l=1;l0)(b=b*2;i-;)for(j=0;j0)p=p*2;i-;p=p*j;for(k=j;k256;k=k+2*b)tr=datark;ti=dataik;temp=datark+b;datark=datark+datark+b*cos_tabp

19、+dataik+b*sin_tabp;dataik=dataik-datark+b*sin_tabp+dataik+b*cos_tabp;datark+b=tr-datark+b*cos_tabp-dataik+b*sin_tabp;dataik+b=ti+temp*sin_tabp-dataik+b*cos_tabp;for(i=0;isample_1/2;i+) wi=sqrt(datari*datari+dataii*dataii);八、实验结果及分析作图，得到输入信号的功率图谱2) fft变换结果图3)改变信号的频率可以再做次实验s3 graiph fr per t jr bi al ogxdi splay typeisi n口亡 timet a.graph titlegraphical bi5playstart addr”5廿pageditaac q-u.i s i ti on