如何实现128点的基2-FFT算法,并与MATLAB的fft算法作对比分析.

Question

不用库函数实现，用源代码实现，很急，找好心人帮助。并给与流程图和原理。要是哪位能帮我解决，请把编好的程序发我邮箱qq244139940，我会追加分，谢谢

Answer 1

我只能给你一个fft算法，流程图说起来有点复杂，可以matlab里面的函数tic（开启时钟）t=toc（关闭时钟）t就是运算过程的时间
当然tic放程序开始，toc放结尾，来分析之即可
function d=lxfft(x)
n=length(x);
if n>2
for i=0:n/2-1
x1(i+1)=x(2*i+1);
x2(i+1)=x(2*i+2);
end
X1=lxfft(x1);
X2=lxfft(x2);
for i=0:n/2-1
X2(i+1)= X2(i+1)*exp(-j*2*pi/n*i);//旋转因子
d(i+1)=X1(i+1)+X2(i+1);
d(i+n/2+1)=X1(i+1)-X2(i+1);
end
else
d(1)=x(1)+x(2);
d(2)=x(1)-x(2);
end
end

Answer 2

disp('请输入一个128点序列');
for ii=1:128 %用户可以自由输入序列
x(ii) = input(['x(',num2str(ii),')=']);
end
%整体运用原位计算
m=nextpow2(x);N=2^m; % 求x的长度对应的2的最低幂次m
if length(x)<N
x=[x,zeros(1,N-length(x))]; % 若x的长度不是2的幂，补零到2的整数幂
end
nxd=bin2dec(fliplr(dec2bin([1:N]-1,m)))+1; % 求1:2^m数列序号的倒序
y=x(nxd); % 将x倒序排列作为y的初始值
for mm=1:m % 将DFT作m次基2分解,从左到右，对每次分解作DFT运算,共做m级蝶形运算，每一级都有2^(mm-1)个蝶形结
Nz=2^mm;u=1; % 旋转因子u初始化为WN^0=1
WN=exp(-i*2*pi/Nz); % 本次分解的基本DFT因子WN=exp(-i*2*pi/Nz)
for j=1:Nz/2 % 本次跨越间隔内的各次蝶形运算,在进行第mm级运算时需要2^(mm-1)个 蝶形
for k=j:Nz:N % 本次蝶形运算的跨越间隔为Nz=2^mm
kp=k+Nz/2; % 蝶形运算的两个因子对应单元下标的关系
t=y(kp)*u; % 蝶形运算的乘积项
y(kp)=y(k)-t; % 蝶形运算
y(k)=y(k)+t; % 蝶形运算
end
u=u*WN; % 修改旋转因子,多乘一个基本DFT因子WN
end
end
y
y1=fft(x) %自己编的FFT跟直接调用的函数运算以后的结果进行对比本回答被提问者采纳