《fft快速傅里叶变换-c语言实现.doc》由会员分享，可在线阅读，更多相关《fft快速傅里叶变换-c语言实现.doc（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-datefft快速傅里叶变换-c语言实现fft快速傅里叶变换-c语言实现#include #include #include #define N 1000/*定义复数类型*/typedef structdouble real;double img;complex;complex xN, *W; /*输入序列,变换核*/int size_x=0; /*输入序列的大小，在本程序中
2、仅限2的次幂*/double PI; /*圆周率*/void fft(); /*快速傅里叶变换*/void initW(); /*初始化变换核*/void change(); /*变址*/void add(complex ,complex ,complex *); /*复数加法*/void mul(complex ,complex ,complex *); /*复数乘法*/void sub(complex ,complex ,complex *); /*复数减法*/void output();int main()int i; /*输出结果*/system(cls);PI=atan(1)*4;p
3、rintf(Please input the size of x:n);scanf(%d,&size_x);printf(Please input the data in xN:n);for(i=0;isize_x;i+) scanf(%lf%lf,&xi.real,&xi.img);initW();fft();output();return 0;/*快速傅里叶变换*/void fft()int i=0,j=0,k=0,l=0;complex up,down,product;change();for(i=0;i log(size_x)/log(2) ;i+) /*一级蝶形运算*/ l=1i;
4、for(j=0;jsize_x;j+= 2*l ) /*一组蝶形运算*/ for(k=0;kl;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; /*初始化变换核*/void initW()int i;W=(complex *)malloc(sizeof(complex) * size_x);for(i=0;isize_x;i+) Wi.real=cos(2*PI/size_x*i); Wi.img=-1
5、*sin(2*PI/size_x*i);/*变址计算，将x(n)码位倒置*/void change()complex temp;unsigned short i=0,j=0,k=0;double t;for(i=0;i0 ) j=j1; if(ji) temp=xi; xi=xj; xj=temp; /*输出傅里叶变换的结果*/void output()int i;printf(The result are as followsn);for(i=0;i=0.0001)printf(+%.4fjn,xi.img); else if(fabs(xi.img)real=a.real+b.real;c-img=a.img+b.img;void mul(complex a,complex b,complex *c)c-real=a.real*b.real - a.img*b.img;c-img=a.real*b.img + a.img*b.real;void sub(complex a,complex b,complex *c)c-real=a.real-b.real;c-img=a.img-b.img;-