my_fft.m

自制的快速傅立叶变换函数

function sw=my_fft(st)
%Recursive Implementation of FFT

N=length(st);
%check length of N is 2^k
if (rem(log(N),log(2)))
    disp('slow_fft:N must be an exact power of 2')
    return
end

WN=exp(2*pi*j/N);

%split st into even and odd samples
st_even=st(1:2:end-1);
st_odd=st(2:2:end);
%implement recursion
if (N==2)
    g=st_even;
    h=st_odd;
    gg=[g g];
    hh=[h -h];
else
    g=my_fft(st_even);
    h=my_fft(st_odd);
    gg=[g g];
    hh=WN.^(-[0:N-1]).*[h h];
end
sw=gg+hh;