fastft.m

包括iir,fir,功率谱

function output=fastft(X,N)   %input the matrix X and the point N
if length(X)<N  
    X=[X,zeros(1,(N-length(X)))];  %if X has lessthan N points 
end
if length(X)>N
    X=X(1:N);   %truncated if it has more
end
A=X;
b=dec2bin(N-1);
for i=1:N
    a=dec2bin(i-1);
    while length(a)<length(b)
        a=[dec2bin(0),a];
    end
    for j=1:length(a)
        b(j)=a(length(a)-j+1);
    end
    X(i)=A(bin2dec(b)+1);
end
for m=1:log2(N)
   k=1; 
    for p=1:N/(2^m)
        for q=0:(2^(m-1)-1)
            r=q*2^(log2(N)-m);
            A(k)=X(k)+X(k+2^(m-1))*exp((-sqrt(-1)*2*pi*r)/N);
            A(k+2^(m-1))=X(k)-X(k+2^(m-1))*exp((-sqrt(-1)*2*pi*r)/N);
            k=k+1;
        end
        k=2^(m-1)+k;
    end
    X=A;
end
output=X;