FFT的C語言算法實現(xiàn).doc

《FFT的C語言算法實現(xiàn).doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、FFT的C語言算法實現(xiàn)程序如下：/************FFT***********/#include#include#include#defineN1000typedefstruct{doublereal;doubleimg;}complex;voidfft();/*快速傅里葉變換*/voidifft();/*快速傅里葉逆變換*/voidinitW();voidchange();voidadd(complex,complex,complex

2、*);/*復(fù)數(shù)加法*/voidmul(complex,complex,complex*);/*復(fù)數(shù)乘法*/voidsub(complex,complex,complex*);/*復(fù)數(shù)減法*/voiddivi(complex,complex,complex*);/*復(fù)數(shù)除法*/voidoutput();/*輸出結(jié)果*/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)");/*輸入序列對應(yīng)的值*/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()/*輸出結(jié)果*/{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