C语言实现FFT(快速傅里叶变换)

}

{

int le,lei,ip; //FFT运算核，使用蝶形运算完成FFT运算 f=FFT_N;

for(l=1;(f=f/2)!=1;l++) //计算l的值，即计算蝶形级数 ;

for(m=1;m<=l;m++) // 控制蝶形结级数

{ //m表示第m级蝶形，l为蝶形级总数l=log（2）N

le=2<<(m-1); //le蝶形结距离，即第m级蝶形的蝶形结相距le点

lei=le/2; //同一蝶形结中参加运算的两点的距离 u.real=1.0; //u为蝶形结运算系数，初始值为1 u.imag=0.0;

//w.real=cos(PI/lei); //不适用查表法计算sin值和cos值 // w.imag=-sin(PI/lei);

w.real=cos_tab(PI/lei); //w为系数商，即当前系数与前一个系数的商 w.imag=-sin_tab(PI/lei);

for(j=0;j<=lei-1;j++) //控制计算不同种蝶形结，即计算系数不同的蝶形结 {

for(i=j;i<=FFT_N-1;i=i+le) //控制同一蝶形结运算，即计算系数相同蝶形结

{

ip=i+lei; //i，ip分别表示参加蝶形运算的两个节点 t=EE(xin[ip],u); //蝶形运算，详见公式 xin[ip].real=xin[i].real-t.real; xin[ip].imag=xin[i].imag-t.imag; xin[i].real=xin[i].real+t.real; xin[i].imag=xin[i].imag+t.imag; }

u=EE(u,w); //改变系数，进行下一个蝶形运算 } } } }

/************************************************************ 函数原型：void main()

函数功能：测试FFT变换，演示函数使用方法 输入参数：无 输出参数：无

************************************************************/ void main() { int i;

create_sin_tab(SIN_TAB);

for(i=0;i

s[i].real=sin(2*3.141592653589793*i/FFT_N); //实部为正弦波FFT_N点采样，赋值为1 s[i].imag=0; //虚部为0 }

FFT(s);

for(i=0;i

s[i].real=sqrt(s[i].real*s[i].real+s[i].imag*s[i].imag);

while(1); }

//进行快速福利叶变换 //求变换后结果的模值，存入复数的实