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

1、目录一、前言二、设计题目三、设计要求3.1 设计目的3.2 设计要求四、设计内容五、设计原理5.2 离散傅里叶变换 DFT5.3 快速傅里叶变换 FFT六、总体方案设计6.1 设计有关程序流程图6.2在CCS环境下加载、调试源程序七、主要参数八、实验结果分析九、设计总结一、前言随着数字电子技术的开展，数字信号处理的理论和技术广泛的应 用于通讯、语音处理、电脑和多媒体等领域。 快速傅里叶变换 FFT 使离散傅里叶变换的时间缩短了几个数量级。 在数字信号处理领域被 广泛的应用。FFT已经成为现代化信号处理的重要手段之一。本次课程设计主要运用 CCS这一工具。CCS(Code Composer St

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

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

4、N的有限长序列x(n),它的离散傅里叶变换DFT为n1nkX(k)x(n)WNnk ,n0k 0,1, N 11式中,WNe/N,称为旋转因子或蝶形因子。从DFT的定义可以看出，在x(n)为复数序列的情况下，对某个k值，直接按1式计算X(k)只需要N次复数乘法和N-1丨次 复数加法。因此，对所有N个k值，共需要N2次复数乘法和N(N-1) 次复数加法。对于一些相当大有 N 值如 1024 点来说,直接计算 它的DFT所需要的计算量是很大的，因此DFT运算的应用受到了很大的限制5.2快速傅里叶变换 FFT旋转因子 WN 有如下的特性。对称性： WNWk 周期性： WN利用这些特性，又可以将长序列

5、的WNk N /2既可以使 DFT中有些项合并，减少了乘法积项，DFT分解成几个短序列的DFT FFT就是利用了旋 转因子的对称性和周期性来减少运算量的。FFT的算法是将长序列的DFT分解成短序列的DFT例如：N为偶 数时，先将N点的DFT分解为两个N/2点的DFT使复数乘法减少一 半:再将每个N/2点的DFT分解成N/4点的DFT,使复数乘又减少一 半，继续进行分解可以大大减少计算量。最小变换的点数称为基数， 对于基数为2的FFT算法，它的最小变换是 2点DFT一般而言，FFT算法分为按时间抽取的 FFTDIT FFT丨和按 频率抽取的F FT DIF FFT两大类。D IF FFT算法是在

6、时域内将每 一级输入序列依次按奇/偶分成2个短序列进行计算。而DIF FFT算法是在频域内将每一级输入序列依次奇/偶分成2个短序列进行计 算。两者的区别是旋转因子出现的位置不同，得算法是一样的。在kDIF FFT算法中，旋转因子Wn 出现在输入端，而在DIF FFT算法中 它出现在输入端。假定序列x(n)的点数N是2的幕，按照DIF FFT算法可将其分为偶 序列和奇序列。偶序列：x(0), x(2), x(4),x(N-2),即右 x(2r),r0,1, N /2 1奇序列：x(1), x(3), x(5),x(N -1),即x2x(2r 1),r0,1, N /2 1那么x(n)的DFT表示

7、为X(k)N1x( n )WNnkn0n为偶数N1x(n)WNnkn0n 为奇数N / 2 1x(2r)WN2rkr0N /2 1x(2r 1)WN(2r r01)kN / 2 1x1(r)WN2rkr0N /2 1WNkx2(r)WN2rkr0(2)由于W可表示为e j(2 / N)e j2 /(N / 2)WN / 2，那么 3式X(k)N /2 1x1(r )WNrk/ 2r0X1(k) WNk X2(k)N/ 2 1WNkx2 (r)WNrk/2r0k 0,1,N /2 1(3)式中，Xl(k)和 X2(k)分别为 xi(n)和 X2(n)的 n/2 的 DFT。由于对称性，w, n/

8、2WnK ,那么 X (k N/2) XMk) W,X2(k)。因此，N点 X(k) 可分为两局部：前半局部： X(k) X1(k) wNkX2(k)k 0,1, N /2 14后半局部： X(k N/2) X1(k) wNkX2(k)k 0,1, N /2 1 5从式4和式5可以看出，只要求出0N/2-1区间Xl(k)和X2(k) 的值，就可求出0N-1区间X(k)的n点值。以同样的方式进行抽取，可以求得N/4点的DFT重复抽取过程，就可以使N点的DFT用上组2点的DFT来计算，这样就可以大减少 运算量。基2 DIF FFT的蝶形运算如图(a)所示。设蝶形输入为Xm1(p)和Xm1(q)，输

9、出为Xm(p)和Xm(q)，那么有kxm( p) xm 1(P)Xm 1(q)Vn §kXm(q) Xm l(p) Xm1(q)WN 7在基数为2的FFT中，设N=2M，共有M级运算，每级有N/2个 2点FFT蝶形运算，因此，N点FFT总共有(N/2)log2N个蝶形运算。Xm(P)Xm(q)图(a)基2 DIF FFT的蝶形运算例如：基数为2的FFT当N=8时，共需要3级，12个基2 DIT FFT的蝶形运算。其信号流程如图(b)所示图(b) 8 点基2 DIF FFT蝶形运算从图(b)可以看出，输入是经过比特反转的倒位序列，称为位码倒置，其排列顺序为x(0),x(4),x(2),

10、x(6),x(1),x(5),x(3),x(7)。输出是按自然顺 序排列，其顺序为 x(0),x(1), ,x(6),x(7)。六、总体方案设计6.1设计程序流程图6.2在CCS境下加载、调试源程序1丨起动CCS在CCS中建立一个工程文件 project'new'FFT,往工程文件里添加程序filenewsourcefile.建立C源文件和一个命令文件，并将这两个文件添加到工程，再编译并装载程序：阅读Dsp原理及应用中fft用dsp实现的有关程序双击Setup CCS 2CCS 000) 快捷方式启动CCS的仿真平台的配着选项。选择C5510 Simulator。Add 加到

11、my system 按下 save2启动c5510后翻开文件FFT.pjt将编写好的源程序，和命令文件加载到文件FFT.pjtSource. FFT,pj尢-Debug Build Complete,0 Errors, 0 Warnings, 0 Remarks 4无错后，Debug'run运行FFT.out程序。(5)通过graph property dialog窗口，改变N点的值，得到不同的结 果。七. 主要参数进行N点FFT运算，分别实现N=256,N=512得到不同的功率谱图六.源程序：Cmd源文件代码:-f 0-w-stack 500-sysstack 500-l rts55

12、.libMEMORYDARAM: o=0x100, l=0x7f00 VECT:o=0x8000, l=0x100 DARAM2:o=0x8100,l=0x7f00 SARAM: o=0x10000,l=0x30000 SDRAM:o=0x40000,l=0x3e0000 SECTIONS.text: >DARAM.vectors: >VECT.trcinit:>DARAM.gblinit:>DARAM.frt:>DARAM.cinit:>DARAM.pinit:>DARAM.sysinit:>DARAM2.far:>DARAM2.cons

13、t:>DARAM2.switch:>DARAM2.sysmem:>DARAM2.cio:>DARAM2.MEM$obj:>DARAM2.sysheap:>DARAM2.sysstack:>DARAM2 .stack:>DARAM2 .input:>DARAM2 .fftcode:>DARAM2 C文件源码：#include "math.h"#define sample_1 256#define signal_1_f 60#define signal_2_f 200#define signal_sample_f 51

14、2#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_data();f or (i=0;i<sample_1;i+)fwaveri=in

15、puti;fwaveii=0.0f;wi=0.0f;fft(fwaver,fwavei);while(1);void init_fft_tab()float wt1;float wt2;int i;for (i=0;i<sample_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()int i;for(i=0;i<sample_1;i+)

16、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;i<sample_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=(i/16)

17、&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;i<sample_1;i+)datari=dataii;dataii=0;for(L=1;L<=8;L+)b=1;i=L-1;while(i>0)b=b*2;i-;for(j=0;j<=b-1;j+)p=1;i=8-L;while(i>0)p=p*2;i-;p=p*j;for(k=j;k<

18、256;k=k+2*b)TR=datark;TI=dataik;temp=datark+b;datark=datark+datark+b*cos_tabp+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;i<sample_1/2;i+)wi=sqrt(datari*datari+dataii*dataii);八、实验结果及分析作图，得到输入信号的功率图谱2FFT变换结果图3改变信号的频率可以再做次实验Q GraLfb Tr oper t jr Bi &L agXDi splay Type1Si ngle Timefall Graph litisGraphi cal EispllySi韭t AddresswFageDkTAAc'u.isi ti on E；口ffer Si1,024Index Inert1Di sl&y II苦Si z*