myfft.m

myfft.m 实现对任意长度一维数组的基2FFT计算

% -------------------  myfft 函数 ---------------------- %
% --------- 实现对任意长度一维数组的基2FFT计算 ------------ %
% ------------------  fy  10717007  --------------------- %
% ------------------ 2008年05月05日 --------------------- %

function result=myfft(inputarray)


% ------------------- 将输入数组补零 --------------------- %

N=2^(log2(2^nextpow2(length(inputarray))));                     % 求出大于数组长度的、等于2的整数次幂的、用于后续计算的长度N
if length(inputarray)<N
    inputarray=[inputarray,zeros(1,N-length(inputarray))];      % 如果输入数组的长度不是2的整数次幂，则用零补至2的整数次幂
end


% ----------------- 将输入数组进行倒排序 ----------------- %

n2=N/2;
n1=N-1;
I=0;
J=0;
while I<n1
    if I<J
        t=inputarray(J+1);
        inputarray(J+1)=inputarray(I+1);
        inputarray(I+1)=t;
    end
    K=n2;
    while K<=J
        J=J-K;
        K=K/2;
    end
    J=J+K;
    I=I+1;
end


% ---------------------- 基2 FFT ------------------------ %

M=1;
while M<=nextpow2(length(inputarray))
    L=2^M;
    L1=L/2;
    U=1;
    W=exp(-j*pi/L1);                                            % 旋转因子
    J=0;
    while J<=L1-1
        I=J;
        while I<=N-1
            IP=I+L1;
            T=inputarray(IP+1)*U;
            inputarray(IP+1)=inputarray(I+1)-T;
            inputarray(I+1)=inputarray(I+1)+T;
            I=I+L;
        end
        U=U*W;
        J=J+1;
    end
    M=M+1;
end


% ------------------------ 输出 ------------------------- %

result=inputarray;