求快速傅里叶算法的C语言实现代码

求快速傅里叶算法的C语言实现代码

这是源于Numerical Recipes 的关键性的函数，我曾使用过（书本可能有印刷错误，这里给的没有错误）。我不可能给你在这里讲解语句功能，你可以查原书。
isign 1 或 0 是正变换和反变换。调用前，要自己去掉 mean，尾部要自己 padding ( 最简单添0），时间域 和 频率 域 要自己 滤波。 nn 必须是2的整数次方，例如1024，4096。

#define SWAP(a,b) tempr=(a);(a)=(b);(b)=tempr
void jfour1(float ya[], unsigned long nn, int isign)
{
unsigned long n,mmax,m,j,istep,i;
double wtemp,wr,wpr,wpi,wi,theta;
float tempr,tempi;
n=nn << 1;
j=1;
for (i=1;i if (j > i) {
SWAP(ya[j],ya[i]);
SWAP(ya[j+1],ya[i+1]);
}
m=n >> 1;
while (m >= 2 && j > m) {
j -= m;
m >>= 1;
};
j += m;
};
mmax=2;
while (n > mmax) {
istep=mmax << 1;
theta=isign*(6.28318530717959/mmax);
wtemp=sin(0.5*theta);
wpr = -2.0*wtemp*wtemp;
wpi=sin(theta);
wr=1.0;
wi=0.0;
for (m=1;m for (i=m;i<=n;i+=istep) {
j=i+mmax;
tempr = wr * ya[j]- wi * ya[j+1];
tempi = wr * ya[j+1] + wi * ya[j];
ya[j] = ya[i] - tempr;
ya[j+1] = ya[i+1] - tempi;
ya[i] += tempr;
ya[i+1] += tempi;
};
wr = (wtemp=wr) * wpr - wi * wpi + wr;
wi = wi * wpr + wtemp * wpi + wi;
};
mmax=istep;
};
}
#undef SWAP
void jrealft(float ya[], unsigned long n, int isign)
{
void jfour1(float ya[], unsigned long nn, int isign);
unsigned long i,i1,i2,i3,i4,np3,n05;
float c1=0.5,c2,h1r,h1i,h2r,h2i;
double wr,wi,wpr,wpi,wtemp,theta;
n05 = n >> 1;
theta=3.141592653589793/(double) (n05);
if (isign == 1) {
c2 = -0.5;
jfour1(ya,n05,1);
} else {
c2=0.5;
theta = -theta;
};
wtemp=sin(0.5*theta);
wpr = -2.0*wtemp*wtemp;
wpi=sin(theta);
wr=1.0+wpr;
wi=wpi;
np3=n+3;
for (i=2;i<=(n>>2);i++) {
i4=1+(i3=np3-(i2=1+(i1=i+i-1)));
h1r = c1 * (ya[i1] + ya[i3]);
h1i = c1 * (ya[i2] - ya[i4]);
h2r = -c2* (ya[i2] + ya[i4]);
h2i = c2 * (ya[i1] - ya[i3]);
ya[i1] =h1r + wr * h2r - wi * h2i;
ya[i2] =h1i + wr * h2i + wi * h2r;
ya[i3] =h1r - wr * h2r + wi * h2i;
ya[i4] = -h1i + wr * h2i + wi * h2r;
wr= (wtemp=wr) * wpr - wi * wpi + wr;
wi=wi * wpr + wtemp * wpi + wi;
};
if (isign == 1) {
ya[1] = (h1r=ya[1]) + ya[2];
ya[2] = h1r-ya[2];
} else {
ya[1] = c1 * ((h1r=ya[1]) + ya[2]);
ya[2]=c1 * (h1r - ya[2]);
jfour1(ya,n05,-1);
}
}