function y=myditfft(x)
%本程序對輸入序列實現DIT-FFT基2算法，點數取大于等于長度的2的冪次
%------------------------------------
%             myditfft.c
%------------------------------------
m=nextpow2(x);                                %求的x長度對應的2的最低冪次m
N=2^m;
if length(x)<N
    x=[x,zeros(1,N-length(x))];               %若的長度不是2的冪，補0到2的整數冪
end
nxd=bin2dec(fliplr(dec2bin([1:N]-1,m)))+1;    %求1：2^m數列的倒序
y=x(nxd);                                     %將倒序排列作為的初始值
for mm=1:m                                    %將DFT做m次基2分解，從左到右，對每次分解作DFT運算
    Nmr=2^mm;
    u=1;                                      %旋轉因子u初始化
    WN=exp(-i*2*pi/Nmr);                      %本次分解的基本DFT因子WN＝exp(-i*2*pi/Nmr)
      for j=1:Nmr/2                           %本次跨越間隔內的各次碟形運算
          for k=j:Nmr:N                       %本次碟形運算的跨越間隔為Nmr=2^mm
              kp=k+Nmr/2;                     %確定碟形運算的對應單元下標
              t=y(kp)*u;                      %碟形運算的乘積項
              y(kp)=y(k)-t;                   %碟形運算的加法項
              y(k)=y(k)+t;
          end
          u=u*WN;                             %修改旋轉因子，多乘一個基本DFT因子WN
      end
  end