超急！ 誰能幫我解釋C程式，有重賞 ” 20 點 ”！

★解釋越詳細越好！！

FFT是快速傅立葉轉換
Complex是複數(實部┼虛部)

主程式：

main()
{
COMPLEX y[8]={1000,0,1000,0,1000,0,1000,0,
0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0}; /*rectangular input*/
int i, n = 8;
FFT(y,n); /*calls generic FFT function*/
for (i = 0; i<n; i++)
{
*out_addr++ = (y[i]).real; /*real output component */
*out_addr++ = (y[i]).imag; /*imaginary output component*/
}
}

副程式：

/*FFT.C - FFT RADIX-2 USING DIF. FOR UP TO 512 POINTS */
#include "complex.h"
#include "twiddle.h"
void FFT(COMPLEX *Y, int N)
{
COMPLEX temp1,temp2;
int i,j,k;
int upper_leg, lower_leg;
int leg_diff;
int num_stages=0;
int index, step;
i=1;
do
{
num_stages+=1;
i=i*2;
} while (i!=N);

leg_diff=N/2;
step=512/N;
for (i=0;i<num_stages;i++)
{
index=0;
for (j=0;j<leg_diff;j++)
{
for (upper_leg=j;upper_leg<N;upper_leg+=(2*leg_diff))
{
lower_leg=upper_leg+leg_diff;
temp1.real=(Y[upper_leg]).real + (Y[lower_leg]).real;
temp1.imag=(Y[upper_leg]).imag + (Y[lower_leg]).imag;
temp2.real=(Y[upper_leg]).real - (Y[lower_leg]).real;
temp2.imag=(Y[upper_leg]).imag - (Y[lower_leg]).imag;
(Y[lower_leg]).real=temp2.real*(w[index]).real-temp2.imag*(w[index]).imag;
(Y[lower_leg]).imag=temp2.real*(w[index]).imag+temp2.imag*(w[index]).real;
(Y[upper_leg]).real=temp1.real;
(Y[upper_leg]).imag=temp1.imag;
}
index+=step;
}
leg_diff=leg_diff/2;
step*=2;
}
j=0;
for (i=1;i<(N-1);i++) /*bit reversal for resequencing data*/
{
k=N/2;
while (k<=j)
{
j=j-k;
k=k/2;
}
j=j+k;
if (i<j)
{
temp1.real=(Y[j]).real;
temp1.imag=(Y[j]).imag;
(Y[j]).real=(Y[i]).real;
(Y[j]).imag=(Y[i]).imag;
(Y[i]).real=temp1.real;
(Y[i]).imag=temp1.imag;
}
}
return;
}