tft.m

matlab环境下编写的fft算法实现的源代码

clc;
clear all;
t=[0:1:255];
x=sin(2*pi*t/20);
y=real(fft(x));
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
figure(1);
plot(t,x);
figure(2);
plot(t,y);
%%%%%%%%%%%%  fft  %%%%%%%%%%%%%%%%%%%
N=256;
NU=8;
NV2=N/2;
NM1=N-1;

J=1;
for I=1:NM1
    if I<J
        T=x(J);
        x(J)=x(I);
        x(I)=T;
    end
    K=NV2;
    while K<J
        J=J-K;
        K=K/2;
    end
    J=J+K;
end

for i=1:256
    xin(2*i-1)=x(i);
    xin(2*i)=0;
end

for l=1:NU
		le=2^l;
		lel=le/2;
		ur=(2^15-1)/2^15;
		ui=0.0;
        wr=cos(pi/lel);
        wi=-sin(pi/lel);
		for j=1:lel
            for i=j:le:N
				ip=i+lel;
				ip_cnt=ip*2-1;
                
                t1=xin(ip_cnt)*ur-xin(ip_cnt+1)*ui;
				t1=t1/2;
				t2=xin(ip_cnt)*ui+xin(ip_cnt+1)*ur;
				t2=t2/2;

                xin(2*i-1)=xin(2*i-1)/2;
				xin(2*i)=xin(2*i)/2;
                
				xin(ip_cnt)=xin(2*i-1)-t1;
				xin(ip_cnt+1)=xin(2*i)-t2;
                
				xin(2*i-1)=xin(2*i-1)+t1;
				xin(2*i)=xin(2*i)+t2;
            end
			ur1=ur*wr-ui*wi;
			ui1=ur*wi+ui*wr;
			ur=ur1;
			ui=ui1;
        end
         tst1=xin*260;
     end

	for i=1:256
        xf(i)=tst1(2*i-1);
    end

    figure(3)
    plot(t,xf,'r')
    
    err=0;
    for i=1:256
        if floor(xf(i))~=floor(y(i))
            err=err+1;
        end
    end
    err