fft.m

计算快速傅立叶变换fft的程序

%计算Wj的值
w=zeros(1,10);
for n=1:10
    w(n)=exp(-2*pi*i/2^n);        
end;

T=[1 1;1 -1];
for n=1:9
    kn=zeros(1,2^n);
    kn(1)=1;
    for m=1:2^n-1
        kn(m+1)=w(n+1)^m;
    end
    K=diag(kn);                 

    I=eye(2^n);
    A=[I I;I -I];
    B=[I zeros(2^n,2^n);zeros(2^n,2^n) K];
    C=[T zeros(2^n,2^n);zeros(2^n,2^n) T];
    T=A*B*C;
end
T10=T;                          

x=linspace(0,2*pi,1024);
y=exp(-abs(x));                       

for m=0:1023
    a(m+1)=m;                       
end
ch=[512 256 128 64 32 16 8 4 2 1];    
for m=1:1024
    v(1)=a(m);
    u(1)=mod(v(1),2);
    for n=2:10
        v(n)=(v(n-1)-u(n-1))/2;
        u(n)=mod(v(n),2);
    end
    b(m)=u*ch';
end
Y=zeros(1,1024);
for m=1:1024
    Y(m)=y(b(m)+1);                        
end
%求出结果
equ=T10*Y'