原创 一个不错的fft的实现

#include <iom128.h>

#include <intrinsics.h>

/*********************************************************************

                         快速福利叶变换C程序包

函数简介：此程序包是通用的快速傅里叶变换C语言函数，移植性强，以下部分不依

         
赖硬件。此程序包采用联合体的形式表示一个复数，输入为自然顺序的复

         
数（输入实数是可令复数虚部为0），输出为经过FFT变换的自然顺序的

         
复数.此程序包可在初始化时调用create_sin_tab()函数创建正弦函数表，

         
以后的可采用查表法计算耗时较多的sin和cos运算，加快可计算速度.与

         
Ver1.1版相比较，Ver1.2版在创建正弦表时只建立了1/4个正弦波的采样值，

         
相比之下节省了FFT_N/4个存储空间

使用说明：使用此函数只需更改宏定义FFT_N的值即可实现点数的改变，FFT_N的

         
应该为2的N次方，不满足此条件时应在后面补0。若使用查表法计算sin值和

         
cos值，应在调用FFT函数前调用create_sin_tab()函数创建正弦表

函数调用：FFT(s);

作    者：吉帅虎

时    间：2010-2-20

版    本：Ver1.2

参考文献： 

**********************************************************************/

#include<math.h>

#define FFT_N 128                                                  
//定义福利叶变换的点数

#define PI
3.1415926535897932384626433832795028841971               //定义圆周率值

struct compx {float real,imag;};                                    //定义一个复数结构

struct compx s[FFT_N];                                             
//FFT输入和输出：从S[0]开始存放，根据大小自己定义

float SIN_TAB[FFT_N/4+1];                                             //定义正弦表的存放空间

/*******************************************************************

函数原型：struct
compx EE(struct compx b1,struct compx b2) 

函数功能：对两个复数进行乘法运算

输入参数：两个以联合体定义的复数a,b

输出参数：a和b的乘积，以联合体的形式输出

*******************************************************************/

struct compx EE(struct compx a,struct compx
b)     

{

 struct compx c;

 c.real=a.real*b.real-a.imag*b.imag;

 c.imag=a.real*b.imag+a.imag*b.real;

 return(c);

}

/******************************************************************

函数原型：void
create_sin_tab(float *sin_t)

函数功能：创建一个正弦采样表，采样点数与福利叶变换点数相同

输入参数：*sin_t存放正弦表的数组指针

输出参数：无

******************************************************************/

void create_sin_tab(float *sin_t)                    

{

  int
i;

 
for(i=0;i<=FFT_N/4;i++)

 
sin_t=sin(2*PI*i/FFT_N);