dit_fft.c

快速傅立叶变换

#include "math.h"
#include "stdio.h"
#define pi 3.14
int M,N;
float Re,Im;
float X[20],A[20],B[20]; /*定义全局变量，其中A，B存放序列X（N）的实部和虚部*/

int pow1(int a,int b) /*计算某个数的N次靡*/
{
int i,c=1;
if(b>=1)
{
for(i=0;i<=b-1;i++)
c=c*a;
}
return(c);
}




void change(void)/*实现倒续*/
{
int LH=N/2;
int J,N1,I,K;
float T;
J=LH;N1=N-2;
for(I=1;I<=N1;I++)
{
if(I<J){T=X[I];A[I]=X[J];A[J]=T;}
K=LH;
for(;J>=K;){J=J-K;K=K/2;}
J=J+K;}
}

void Wn(int p)/*旋转因子的计算，其中分为实部和虚部*/
{
double n,m;
m=(double)N;
n=2.0*pi/m*p*-1.0;
Re=(float)cos(n);Im=(float)sin(n);
}

void DIT_FFT(void)/*快速DFT运算*/
{
int L,b,t,p,w,J,K,c,h=2;
for(L=1;L<=M;L++)
{
t=L-1;
b=pow1(h,t);
for(J=0;J<=b-1;J++)
{t=M-L;c=pow1(h,t);p=J*c;
for(K=J;K<=N-1;K=K+c)
{
Wn(p);

A[K]=A[K]+A[K+b]*Re-B[K+b]*Im;
B[K]=B[K]+B[K+b]*Re+A[K+b]*Im;
A[K+B]=A[K]-A[K+b]*Re+B[K+b]*Im;
B[K+B]=B[K]-B[K+b]*Re-A[K+b]*Im;
c=pow1(h,L);
}
}
}
  }

void display(void)
{
int i;
for(i=0;i<=N-1;i++) /*输入部分，直接输如任意点的N=2的M次幂，输入M*/
printf(" %f+j*%f ",A[i],B[i]);
}
main()
{
int i,q=2;
scanf("%d",&M);N=pow1(q,M);
for(i=0;i<N;i++)
{
scanf("%f",&X[i]);
A[i]=X[i];
B[i]=0;
}
change();
DIT_FFT();/*函数调用*/
display();
getch();
}