ditfft.m

在matlab中实现时间抽取基2 FFT算法

%按照时间抽取的基-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