FFT的C语言算法实现.doc

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

1、FFT的C语言算法实现程序如下：/************FFT***********/#include#include#include#defineN1000typedefstruct{doublereal;doubleimg;}complex;voidfft();/*快速傅里叶变换*/voidifft();/*快速傅里叶逆变换*/voidinitW();voidchange();voidadd(complex,complex,complex

2、*);/*复数加法*/voidmul(complex,complex,complex*);/*复数乘法*/voidsub(complex,complex,complex*);/*复数减法*/voiddivi(complex,complex,complex*);/*复数除法*/voidoutput();/*输出结果*/complexx[N],*W;/*输出序列的值*/intsize_x=0;/*输入序列的长度，只限2的N次方*/doublePI;intmain(){inti,method;syste

3、m("cls");PI=atan(1)*4;printf("Pleaseinputthesizeofx:");/*输入序列的长度*/scanf("%d",&size_x);printf("Pleaseinputthedatainx[N]:(suchas:56)");/*输入序列对应的值*/for(i=0;i

4、FFT(1)?");scanf("%d",&method);if(method==0)fft();elseifft();output();return0;}/*进行基-2FFT运算*/voidfft(){inti=0,j=0,k=0,l=0;complexup,down,product;change();for(i=0;i

5、W[size_x*k/2/l],&product);add(x[j+k],product,&up);sub(x[j+k],product,&down);x[j+k]=up;x[j+k+l]=down;}}}}voidifft(){inti=0,j=0,k=0,l=size_x;complexup,down;for(i=0;i<(int)(log(size_x)/log(2));i++)/*蝶形运算*/{l/=2;for(j=0;j

6、dd(x[j+k],x[j+k+l],&up);up.real/=2;up.img/=2;sub(x[j+k],x[j+k+l],&down);down.real/=2;down.img/=2;divi(down,W[size_x*k/2/l],&down);x[j+k]=up;x[j+k+l]=down;}}}change();}voidinitW(){inti;W=(complex*)malloc(sizeof(complex)*size_x);for(i=0;i

7、i].real=cos(2*PI/size_x*i);W[i].img=-1*sin(2*PI/size_x*i);}}voidchange(){complextemp;unsignedshorti=0,j=0,k=0;doublet;for(i=0;i0){j=j<<1;j

8、=(k&1);k=k>>1;}if(j>i){temp=x[i];x[i]=x[j];x[j]=temp;}}}

9、voidoutput()/*输出结果*/{inti;printf("Theresultareasfollows");for(i=0;i=0.0001)printf("+%.4fj",x[i].img);elseif(fabs(x[i].img)<0.0001)printf("");elseprintf("%.4fj",x[i].img);}}voidadd(compl