limsnudt 发表于 2006-3-29 12:45

[原创]自己编写的FFT程序运行速度问题

这里是小弟自己编写的二维快速Fourier变换的程序(Matlab),一维速度很快,但二维就很慢,请教各位大侠如何改进!!!(这是我的作业),谢谢!<br>可以给我发邮件 limsnudt@sohu.com <br>
[此贴子已经被aspen于2006-3-30 9:32:21编辑过]

limsnudt 发表于 2006-3-29 17:54

不好意思,程序没有上来

<P>function y=daoxu(a,n)<BR>%对输入的2的n次幂个点进行倒序运算<BR>t=;<BR>b=dec2bin(t-1,n);<BR>if rem(n,2)==0<BR>    m=n*0.5;<BR>else <BR>    m=(n+1)*0.5;<BR>end<BR>b1=b.';%转置之后来交换行,看看速度会不会快起来<BR>for k=1:m<BR>    d=b1(k,:);<BR>    b1(k,:)=b1(n+1-k,:);%换行<BR>    b1(n+1-k,:)=d;<BR>end<BR>b=b1.';<BR>for l=1:2^n<BR>    a1(l)=a(bin2dec(b(l,:))+1);<BR>end<BR>y=a1;</P>
<P><BR>%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%<BR>%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%<BR>function y=ft1(a)<BR>%已经进行倒序之后的一维快速Fourier变换,b为经过倒序之后的输入序列,N为凑为2的次幂的幂指数<BR>%此处的Fourier正变换前面不带任何系数<BR>M=length(a);<BR>N=log2(M);<BR>b=daoxu(a,N);<BR>for k=1:2:(2^N-1)<BR>    c(k)=b(k)+b(k+1);<BR>    c(k+1)=b(k)-b(k+1);<BR>end<BR>%以上计算的是最底层的单个点的Fourier变换<BR>%具体的计算过程采用从下到上分成各个小部分进行计算的方法<BR>for n=2:N<BR>    for t=1:2^(N-n)<BR>            m=2^(n-1);<BR>            p=t*2^n-(2^n-1);<BR>            u=0;<BR>            while (p&lt;=t*2^n-2^(n-1))&amp;(u&lt;=(m-1))<BR>                d(p)=c(p)+c(p+2^(n-1))*((exp(-j*2*pi/(2*m)))^u);<BR>                d(p+m)=c(p)-c(p+2^(n-1))*((exp(-j*2*pi/(2*m)))^u);<BR>                p=p+1;<BR>                u=u+1;   <BR>            end<BR>    end<BR>    c=d;<BR>end<BR>d=[];<BR>y=c;</P>
<P>%%%%%%%%%%%%%%%%%%%%%%%%%%%%%<BR>%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%</P>
<P>function y=haofft(a)<BR>tic;<BR>%二维快速Fourier变换,即对一维的情况进行循环<BR>n=length(a);<BR>b=zeros(n);<BR>c=zeros(n);<BR>for k=1:n<BR>    b(k,:)=ft1(a(k,:));<BR>end<BR>a=[];<BR>for l=1:n<BR>    c(:,l)=ft1(b(:,l));<BR>end<BR>y=c;<BR>toc;</P>

happy 发表于 2006-3-29 19:26

回复:(limsnudt)[原创]请大侠赐教,小弟谢谢你!

matlab不是自带了吗?
页: [1]
查看完整版本: [原创]自己编写的FFT程序运行速度问题