基于DSP的FFT算法实现.doc

《基于DSP的FFT算法实现.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基于DSP的FFT算法实现1、FFT的原理快速傅氏变换（FFT）是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。设x(n)为N项的复数序列，由DFT变换，任一X（m）的计算都需要N次复数乘法和N-1次复数加法，而一次复数乘法等于四次实数乘法和两次实数加法，一次复数加法等于两次实数加法，即使把一次复数乘法和一次复数加法定义成一次“运算”（四次实数乘法

2、和四次实数加法），那么求出N项复数序列的X（m）,即N点DFT变换大约就需要N2次运算。当N=1024点甚至更多的时候，需要N2=次运算，在FFT中，利用WN的周期性和对称性，把一个N项序列（设N=2k,k为正整数），分为两个N/2项的子序列，每个N/2点DFT变换需要（N/2）2次运算，再用N次运算把两个N/2点的DFT变换组合成一个N点的DFT变换。这样变换以后，总的运算次数就变成N+2（N/2）2=N+N2/2。继续上面的例子，N=1024时，总的运算次数就变成了次，节省了大约50%的运算量。而如果我们将这种

3、“一分为二”的思想不断进行下去，直到分成两两一组的DFT运算单元，那么N点的DFT变换就只需要Nlog2N次的运算，N在1024点时，运算量仅有10240次，是先前的直接算法的1%，点数越多，运算量的节约就越大，这就是FFT的优越性。数字信号处理器(DSP)是一种可编程的高性能处理器，近年来发展很快．它不仅适用于数字信号处理，而且在图像处理、语音处理、通信等领域得到了广泛的应用．通用的微处理器在运算速度上很难适应信号实时处理的要求．联沪处理器中集成有高速的乘法器硬件，能快速地进行大量数据的乘法和加法运算。快速傅里叶

4、变换(FFT)的出现使得DFr在实际应用中得到了广泛的应用．2、基于DSP的FFT算法实现用C语言实现FFT算法/*****************fftprograme*********************/#include"typedef.h"#include"math.h"structcompxEE(structcompxb1,structcompxb2){   structcompxb3;   b3.real=b1.real*b2.real-b1.imag*b2.imag;   b3.imag=b1.r

5、eal*b2.imag+b1.imag*b2.real;   return(b3);}voidFFT(structcompx*xin,intN){   intf,m,nv2,nm1,i,k,j=1,l;   /*intf,m,nv2,nm1,i,k,j=N/2,l;*/   structcompxv,w,t;   nv2=N/2;   f=N;   for(m=1;(f=f/2)!=1;m++)   {       ;   }   nm1=N-1;      /*变址运算*/   for(i=1;i<=nm1;i+

6、+)   {       if(i

7、l++)       {           le=pow(2,l);           //这里用的是L而不是1            lei=le/2;           pi=3.14159;           v.real=1.0;           v.imag=0.0;           w.real=cos(pi/lei);           w.imag=-sin(pi/lei);           for(j=1;j<=lei;j++)           {            

8、   /*doublep=pow(2,m-l)*j;                 doubleps=2*pi/N*p;                 w.real=cos(ps);                 w.imag=-sin(ps);*/               for(i=j;i<=N;i=i+le)               {