用matlab編寫實現fft的程序。

%本程序對輸入序列實現DIT-FFT基2算法，點數取大於等於長度的2的冪次

%------------------------------------

%

myditfft.c

%------------------------------------

m=nextpow2(x);

%求的x長度對應的2的最低冪次m

N=2^m;

if length(x)<N

x=[x,zeros(1,N-length(x))];

%若的長度不是2的冪，補0到2的整數冪

end

nxd=bin2dec(fliplr(dec2bin([1:N]-1,m)))+1;

%求1：2^m數列的倒序

y=x(nxd);

%將倒序排列作為的初始值

for mm=1:m

%將DFT做m次基2分解，從左到右，對每次分解作DFT運算

Nmr=2^mm;

u=1;

%旋轉因子u初始化

WN=exp(-i*2*pi/Nmr);

%本次分解的基本DFT因子WN＝exp(-i*2*pi/Nmr)

for j=1:Nmr/2

%本次跨越間隔內的各次碟形運算

for k=j:Nmr:N

%本次碟形運算的跨越間隔為Nmr=2^mm

kp=k+Nmr/2;

%確定碟形運算的對應單元下標

t=y(kp)*u;

%碟形運算的乘積項

y(kp)=y(k)-t;

%碟形運算的加法項

y(k)=y(k)+t;

end

u=u*WN;

%修改旋轉因子，多乘壹個基本DFT因子WN

end

end