FFT的C语言算法实现

程序如下：

/************FFT***********/ #include #include #include

#define N 1000 typedef struct {

double real; double img; }complex;

void fft(); /*快速傅里叶变换*/ void ifft(); /*快速傅里叶逆变换*/ void initW(); void change();

void add(complex ,complex ,complex 数加法*/

void mul(complex ,complex ,complex 数乘法*/

void sub(complex ,complex ,complex 数减法*/

*); /*复*); /*复*); /*复 void divi(complex ,complex ,complex *);/*复数除法*/

void output(); /*输出结果*/

complex x[N], *W;/*输出序列的值*/

int size_x=0;/*输入序列的长度，只限2的N次方*/ double PI;

int main() {

int i,method;

system(\"cls\"); PI=atan(1)*4;

printf(\"Please input the size of x:\\n\"); /*输入序列的长度*/ scanf(\"%d\

printf(\"Please input the data in x[N]:(such as:5 6)\\n\");

/*输入序列对应的值*/ for(i=0;iscanf(\"%lf %lf\ initW();

/*选择FFT或逆FFT运算*/

printf(\"Use FFT(0) or IFFT(1)?\\n\"); scanf(\"%d\

if(method==0) fft(); else ifft(); output(); return 0; }

/*进行基-2 FFT运算*/ 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<for(j=0;j{

mul(x[j+k+l],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;

} } } }

void ifft() {

int i=0,j=0,k=0,l=size_x; complex up,down;

for(i=0;i< (int)( log(size_x)/log(2) */

{ l/=2;

for(j=0;jadd(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; }

);i++) /*蝶形运算