function f=fft1(x)
N=length(x); %序列长度
y=zeros(1,N);
r=N;
m=0;
while r~=1
m=m+1;
r=r/2;
end % 二进制的长度
for g=0:N-1
t=0;
n=1;
s=g;
while s~=0
t=mod(s,2)*2^(m-n)+t;
n=n+1;
s=(s-mod(s,2))/2;
end %二进制倒转
l=x(1,g+1);
y(1,t+1)=l;
end
%倒序实现完毕
for g=1:m
for j=1:2^(m-g)
for k=1:2^(g-1)
a=y(1,2^(g-1)*(j-1)*2+k);
b=y(1,2^(g-1)*(j-1)*2+k+2^(g-1));
y(1,2^(g-1)*(j-1)*2+k)=a+exp(-2*1i*pi*(k-1)*2^(m-g)/N)*b;
y(1,2^(g-1)*(j-1)*2+k+2^(g-1))=a-exp(-2*1i*pi*(k-1)*2^(m-g)/N)*b;
end
end
end
f=y;
stem(y);
end
评论0