#include<iostream.h>
#include <math.h>
#define N 64
#define m 6 //2^m=N
double twiddle[N/2]={1,0.9951,0.9808,0.9570,0.9239,0.8820,0.8317,0.7733,
0.7075,0.6349,0.5561,0.4721,0.3835,0.2912,0.1961,0.0991,
0.0000,-0.0991,-0.1961,-0.2912,-0.3835,-0.4721,-0.5561,-0.6349,
-0.7075,-0.7733,0.8317,-0.8820,-0.9239,-0.9570,-0.9808,-0.9951,}; //N=64
double x_r[N]={1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,};
double x_i[N];

void fft_init() //为数组X_i赋值
{
int i;
for(i=0;i<N;i++)
x_i[i]=0.0;
}
void bitrev()
{
int p=1,q,i;
int bit_rev[N];
double xx_r[N];
bit_rev[0]=0;
while(p<N)
{
for(q=0;q<p;q++)
{
bit_rev[q]=bit_rev[q]*2;
bit_rev[q+p]=bit_rev[q]+1;
}
p=p*2;
}
for(i=0;i<N;i++)
{
xx_r[i]=x_r[i];
}
for(i=0;i<N;i++)
{
x_r[i]=xx_r[bit_rev[i]];
}
}

void display()
{
int i;
for(i=0;i<N;i++)
cout<<x_r[i]<<","<<x_i[i]<<endl;
}

void fft1()
{
int L,i,b,j,p,k,tx1,tx2;
double TI,TR,temp;
double tw1,tw2;

for(L=1;L<=m;L++)
{ /* for(1) */
b=1; i=L-1;
while(i>0)
{b=b*2;i--;} /* b= 2^(L-1) */
for(j=0;j<=b-1;j++) /* for (2) */
{ p=1; i=m-L;
while(i>0) /* p=pow(2,7-L)*j; */
{p=p*2; i--;}
p=p*j;
tx1=p%(N);
tx2=tx1+(3*N)/4;
tx2=tx2%(N);
if (tx1>=(N/2))
tw1=-twiddle[tx1-(N/2)];
else
tw1=twiddle[tx1];
if (tx2>=(N/2))
tw2=-twiddle[tx2-(N/2)];
else
tw2=twiddle[tx2];
for(k=j;k<N;k=k+2*b) /* for (3) */
{TR=x_r[k]; TI=x_i[k]; temp=x_r[k+b];
x_r[k]=x_r[k]+x_r[k+b]*tw1+x_i[k+b]*tw2;
x_i[k]=x_i[k]-x_r[k+b]*tw2+x_i[k+b]*tw1;
x_r[k+b]=TR-x_r[k+b]*tw1-x_i[k+b]*tw2;
x_i[k+b]=TI+temp*tw2-x_i[k+b]*tw1;
}
}
}

}

int main(int argc, char* argv[])
{

fft_init();
bitrev();
fft1();
display(); //FFT
return 0;
}

把他变为C# 的类