Matlab快速傅里叶变换程序(FFT)编写
(不利用Matlab内置fft)
最近在学习数字信号处理,正好到快速傅里叶变换,写一个基于基2FFT算法的傅里叶变换。利用原理:DIT-FFT(时域抽取法基2FFT)。 DIT-FFT: 设序列x(n)的长度为N,且满足N=2^M,M为自然数。 ①按n的奇偶把x(n)分解为两个N/2的子序列。 ②对x(n)做DFT,经过化简可以得到 X(k)=X1(k)+W^k; X(k+N/2)=X1(k)+W^kX2(k); k=0,1,…,N/2-1; 由此得到一个蝶形运算符号: ③这是DIT-FFT基本原理,按照N值的大小,还可进一步进行分解运算,可分解M次,将N点DFT分解为N个1点DFT和M级蝶形运算,而1点DFT就是时域序列本身。 DFT与FFT运算量比较: N点DFT:复数乘法CM=NN 复数加法CA=N(N-1) N点FFT: 复数乘法CM=MN/2 复数加法CA=MN N=2^M 代码:
function H=ditfft2(xn,M)
%DIT-FFT快速傅里叶变换程序
%程序名称:ditfft
%程序作者:grace_fight 2018/10/29
b=length(xn); %调整补零
if(b |