%按照時間抽取的基-2快速傅里葉變換（基-2 FFT-DIT）。輸入倒位序，輸出自然順序。
%先對輸入序列根據基-2進行補零，然后用二進制倒序，再進行FFT
function y=ditfft(x)
%補零
M=nextpow2(x);N=2^M;
if length(x)<N
    x=[x,zeros(1,N-length(x))];
end
%二進制倒序
order=bin2dec(fliplr(dec2bin([0:N-1],M)))+1;
y=x(order);
%FFT的蝶形運算
for L=1:M
    B=2^(L-1);
    Wpn=1;
    w=exp(-i*2*pi/(2*B));   %2^(M-L)/N=2^L
    for J=1:B
        for k=J:2*B:N-1
            t=y(k+B)*Wpn;
             y(k+B)=y(k)-t;
             y(k)=y(k)+t;
        end
        Wpn=Wpn*w;
    end
end