本文共 738 字，大约阅读时间需要 2 分钟。

（1）序列的倒序

function [X] = invertedorder(A)%invertedorder 序列时域抽取（倒序）%   A-时域序列，X-时域抽取后的序列N=length(A);LH=N/2;j=LH;N1=N-2;X=A;for i=1:N1    if i>=j        T=X(i+1);        X(i+1)=X(j+1);        X(j+1)=T;    end    K=LH;    while j>=K        j=j-K;        K=K/2;    end    j=j+K;endend

（2）DIT-FFT算法

function [Xk] = DIT_FFT(xn,M)%DIT_FFT 序列长度为2^M的傅里叶变换%   xn-时域序列,M=log2(N)N=2^M;Xk=invertedorder(xn);for l=1:M    B=2^(l-1);    for j=0:B-1        P=2^(M-l)*j;        for k=j:2^l:N-1            WNP=exp(-1j*2*pi*P/N);            T=Xk(k+1)+Xk(k+1+B)*WNP;            Xk(k+1+B)=Xk(k+1)-Xk(k+1+B)*WNP;            Xk(k+1)=T;        end    endendend

（3）验证

xn=0:7;M=3;Xk=DIT_FFT(xn,M)Xk1=fft(xn)

验证结果如下：

由图可看到，该上述两段代码计算的结果与MATLAB自带的函数计算结果相同，证明了这两段代码的正确性。