for(i=0;i<num_stages;i++) // for N-point FFT
{
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;
}
}
}
|
