用Matlab编写fft

FFT算法编写

1、程序

function [A] = myfft(A,M)

N=2^M;

LH=N/2;

J=LH;

N1=N-2;

for I=1:1:N1

if I

T=A(I+1);

A(I+1)=A(J+1);

A(J+1)=T;

end

K=LH;

while J>=K

J=J-K;

K=K/2;

end

J=J+K;

end

for L=1:1:M

B=2^(L-1);

for J=0:B-1

p=J*2^(M-L);

for k=J:2^L:N-1

T=A(k+1)+A(k+B+1)*exp(-i*2*pi*p/N);

A(k+B+1)=A(k+1)-A(k+B+1)*exp(-i*2*pi*p/N);

A(k+1)=T;

end

end

end

end

2、程序检验：

在Matlab中输入如下代码，将自己编写的FFT算法与Matlab自带算法的计算结果进行比较。

A=[0 1 2 3 4 5 6 7];

myfft(A,3)

fft(A,8)

计算结果如下图：

由结果可以看出，编写的myFFT算法得到的结果与Matlab自带算法得到的结果相同，说明编写正确。