fft快速算法.doc

基2DIT-FFT的快速算法#include#includemath.h#define pi 3.14159void DWX(double a,int n) /实现倒位序运算函数int j=n/2,i=0,k;double t=0;for(i=1;in-2;i+)if(i=k)j=j-k;k=k/2;elsej=j+k;break;else / /实现高位向低位进位k=n/2;while(1)if(j=k)j=j-k;k=k/2;elsej=j+k;break;class complex /实现复数运算public:/无参构造函数complex()re=0;im=0;/有参构造函数complex(double real,double imag)re=real;im=imag;/加法complex operator + (complex& c)return complex( re + c.re , im + c.im );/减法complex operator - (complex& c)return complex( re - c.re , im - c.im );/乘法complex operator * (complex& c)return complex( (re * c.re)-(im * c.im) , (re * c.im)+(im * c.re) );/除法complex operator / (complex& c)return complex( ( re*c.re + im*c.im )/( c.re*c.re + c.im*c.im ),(im * c.re)-(re * c.im)/(c.re*c.re)+(c.im*c.im) );/显示void show()coutre=0)?+:-) j=0)?im:(0-im) ;/设值void setValue(double real,double imag)if(real0.000001|real0.000001|imag -0.000001) im=imag;else im=0; double ren()return re;double imm()return im;private:double re,im;void wn(complex w,int len) /获得旋转因子int i=0;for(;ilen;i+) wi.setValue(cos(-2*pi*i)/(2*len),sin(-2*pi*i)/(2*len);void getX(complex x,double y,int n)int i=0;for(;in;i+)xi.setValue(yi,0);void fft(complex a,complex w,int m) /fft迭代算法complex q,t;int i,j,k,p,b,c;for(i=1;i=m;i+)b=(int) pow(2,i-1);for(j=0;j=(int) pow(2,i-1)-1;j+)p=(int) pow(2,m-i)*j;for(k=j,c=1;c=(int) pow(2,m-i);c+)t=ak+ak+b*wp;ak+b=ak-ak+b*wp;ak=t;k=k+(int)pow(2,i);void main()int n,i,m=0,t;coutn;double *X=new doublen; cout请输入离散数列元素:endl; /初始化数列for(i=0;iXi;t=n;while(t/2) /计算出数列的阶数m+;t=t/2;complex *x=new complexn; /申请频域的数组空间complex *w=new complexn/2; /申请旋转因子的数组空间 DWX(X,n); /实现倒位序getX(x,X,n); /获得复数数列wn(w,n/2); /获得旋转因子fft(x,w,m); /实现fft快速算法 for(i=0;in;i+)xi.setValue(xi.