FFT的C语言算法实现

1、FFT的C语言算法实现程序如下：/I1111/*FFT*#include#include#include#defineN1000typedefstructdoublereal;doubleimg;complex;voidfft();/*快速傅里叶变换*/voidifft();/*快速傅里叶逆变换*/voidinitW();voidchange();voidadd(complex,complex,complex*);/*复数加法*/voidmul(complex,complex,complex*);/*复数乘法*/voidsub(complex,complex,complex*);/*复数减法*

2、/voiddivi(complex,complex,complex*);/*复数除法*/voidoutput();/*输出结果*/complexxN,*W;/*输出序列的值*/intsize_x=0;/*输入序列的长度，只限2的N次方*/doublePI;intmain()inti,method;system(cls);PI=atan(1)*4;printf(Pleaseinputthesizeofx:n);/*输入序列的长度*/scanf(%d,&size_x);printf(PleaseinputthedatainxN:(suchas:56)n);/*输入序列对应的值*/for(i=0;i

3、size_x;i+)scanf(%lf%lf,&xi.real,&xi.img);initW();/*选择FFT或逆FFT运算*/printf(UseFFT(0)orIFFT(1)?n);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;ilog(size_x)/log(2);i+)l=1i;for(j=0;jsize_x;j+=2*l)for(k=0;k

4、l;k+)mul(xj+k+l,Wsize_x*k/2/l,&product);add(xj+k,product,&up);sub(xj+k,product,&down);xj+k=up;xj+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;jsize_x;j+=2*l)for(k=0;kl;k+)add(xj+k,xj+k+l,&up);up.real/=2;up.img/=2;sub(xj+k,xj+k+l,

5、&down);down.real/=2;down.img/=2;divi(down,Wsize_x*k/2/l,&down);xj+k=up;xj+k+l=down;change();voidinitW()inti;W=(complex*)malloc(sizeof(complex)*size_x);for(i=0;isize_x;i+)Wi.real=cos(2*PI/size_x*i);Wi.img=-1*sin(2*PI/size_x*i);voidchange()complextemp;unsignedshorti=0,j=0,k=0;doublet;for(i=0;i0)j=j1;i

6、f(ji)temp=xi;xi=xj;xj=temp;voidoutput()/*输出结果*/inti;followsn);printf(Theresultareasfor(i=0;i=0.0001)printf(+%.4fjn,xi.img);elseif(fabs(xi.img)real=a.real+b.real;c-img=a.img+b.img;voidmul(complexc-real=a.real*b.realc-img=a.real*b.imgvoidsub(complexc-real=a.real-b.real;c-img=a.img-b.img;voiddivi(complexa,complexb,complex-a.img*b.img;+a.img*b.real;a,complexb,complexa,complexb,complex*c)*c)*c)c-real=(a.real*b.real+a.i