%時域抽取法基2FFT通用源程序
%若xn長度不足N則補零至NN為2的整數(shù)次冪
function?Xk=n_fft（xnN）
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%第一步:補零并調(diào)用倒序子程序
if?length（xn）xn=[xnzeros（1N-length（xn））];
end
xn=bit_reversal（xn）;?????????????%倒序程序
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%第二步:構(gòu)造運算流圖
L=log2（N）;???????????????????????????????????????????%?級數(shù)

%構(gòu)造第一級
G=zeros（NL）;
for?ii=1:（N/2）
G（2*ii-11）=ii;
G（2*ii1）=ii;
end

%構(gòu)造第2級到第L級
for?ii=2:L
di=2^（ii-2）;
g=G（:ii-1）;
for?jj=1:（N/2）
pos=find（g==jj）;
num=floor（pos（1）/（2^（ii-1）））+1;
if?mod（num2）==1
P=pos（2）;
else
P=pos（1）;
end
G（P+diii）=jj;
G（P-diii）=jj;
end
end
%第三步:構(gòu)造翅權(quán)數(shù)據(jù)
CQ=zeros（N/2L）;
for?ii=1:L
Jmax=2^（ii-1）-1;
JJ=（2^（L-ii））.*[0:Jmax];
for?k=1:length（JJ）
JJ（k）=cos（2*pi*JJ（k）/N）+i*sin（2*pi*JJ（k）/N