fft快速傅里叶变换-c语言实现.doc
Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-datefft快速傅里叶变换-c语言实现fft快速傅里叶变换-c语言实现#include <stdio.h>#include <math.h>#include <stdlib.h>#define N 1000/*定义复数类型*/typedef structdouble real;double img;complex;complex xN, *W; /*输入序列,变换核*/int size_x=0; /*输入序列的大小，在本程序中仅限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;printf("Please input the size of x:n");scanf("%d",&size_x);printf("Please input the data in xN:n");for(i=0;i<size_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=1<<i; for(j=0;j<size_x;j+= 2*l ) /*一组蝶形运算*/ for(k=0;k<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; /*初始化变换核*/void initW()int i;W=(complex *)malloc(sizeof(complex) * size_x);for(i=0;i<size_x;i+) Wi.real=cos(2*PI/size_x*i); Wi.img=-1*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;i<size_x;i+) k=i;j=0; t=(log(size_x)/log(2); while( (t-)>0 ) j=j<<1; j|=(k & 1); k=k>>1; if(j>i) temp=xi; xi=xj; xj=temp; /*输出傅里叶变换的结果*/void output()int i;printf("The result are as followsn");for(i=0;i<size_x;i+) printf("%.4f",xi.real); if(xi.img>=0.0001)printf("+%.4fjn",xi.img); else if(fabs(xi.img)<0.0001)printf("n"); else printf("%.4fjn",xi.img);void add(complex a,complex b,complex *c)c->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;-
