dit-fft算法子程序.txt

DIT-FFT算法子程序 FFT长度为2m

DIT-FFT算法子程序 
FFT长度为2m，m为正整数。FFT输出结果放在输入复数数组中。其中xr存放信号序列实部，xi存放信号序列虚部。如果信号长度小于N，需要给xr和xi后面补足0，计算结果x(k)的实部和虚部仍然分别存放在数组xr和xi中。
Void fft(double Rer[]，double Imr[]，int N，int M) )
{
Int L,B,J,P,k,I； 
Double rParkKB，iParkKB;
Double rcf[128]，icf[128];
Double PI2=8.O*atan(1.O);
For(i=O；i<N；i++)
{
Rcf[i]=cos(i*PI2/N);
Icf[i]=sin(i*PI2/N);
}
ChangeOrder(xr,xi,N);/*调用倒序子程序*/
／*计算各级蝶形*／ 
For(L=1;L<=M;L++)
{
B=(int)(pow(2,(L-1))+O.5);
For(J=O；J<=B-1；J++) 
{
P=-J*((int)(pow(2,(M-L))+O.5)); 
For(k=J;k<=N_1;k+=(int)(pow(2,L)十O.5))
{ 
rPartKB=xr[k+B]*rcf[P]-xi[k+B]*icf(P); 
iPartKB=xi[k+B]*rcf[P]-xi[k+B]*icf(P); 
xr[k+B]=xr[k]-rPartKB; 
xi[k+B]=xi[k]-iPartKB;
xr[k+B]=xr[k]-iPartKB;
xi[k+B]=xi[k]-iPartKB;
xi[k]=xr[k]-rPartKB;
xr[b]=xr[k]+iPartKB;
             }
}
}
}
/*倒序子程序*/
Void ChangeOrder(Double xr[]，Double xi[] 
{
Int LH，NI，I，J，K;
Double T;
 LH;N／2；J=LH；NI=N-2;
For(I=1；I<=N1；I++) 
     {  
If(I<J) 
{ 
T=xr[I];xr[I]-xr[J];xr[J]=T;
T=xi[I]；xi[I]=xi[J]；xi[J]=T；
}
K=LH;
While(j>=k)
{
   J=J-K;
K=(int)(k/2+0.5);
}
 J=J+K;
}
}