No BSD License  

fft

by

 

fft code written my me

myfft.m
function xn=myfft(x)
N=length(x);%ȡ鳤
M=log2(N);%鳤2Ϊ׵
%˴xxtmp
%˼룺ÿλx(i)еiֵ2ƣÿνλȡ浽ΪM
%ĴӵMλ1λſλõĶƱʾ
%黻ʮƵźposٽx(i)xtmp(pos)
%matlab1ʼӦΪx(pos+1)=x(i+1)
xtmp=zeros(1,N);
value=zeros(1,M);
for i=0:N-1
    repr=i;
    for t=1:1:M
        repr=bitshift(i,1-t);
        value(t)=bitand(repr,1);
    end
    pos=0;
    for k=1:1:M
        pos=pos+value(k)*2^(M-k);
    end
    xtmp(pos+1)=x(i+1);
end
%xtmp=x;

%fft
%Ҫ˼룺M
%ÿwidth㣬ÿ2^iľ루iΪi㣩
%ÿdeepth
for i=1:M
    deepth=2^(i-1);
    width=2^(M-i);
    for t=1:2^i:N
        for k=1:deepth
            tmp=xtmp(t+k-1);
            wn=width*(k-1);
            xtmp(t+k-1)=tmp+exp(-j*2*pi*wn/N)*xtmp(t+k+deepth-1);
            xtmp(t+k+deepth-1)=tmp-exp(-j*2*pi*wn/N)*xtmp(t+k+deepth-1);
        end
    end
end
xn=xtmp;
            





Contact us