快速傅里叶变换FFT的matlab实现及FFT的简单应用.pdf

信号与系统课程设计 快速傅里叶变换FFT 的matlab 实现和FFT 的简单应用 1 2008102018 电子二班） （卿立艳 08级 【摘要】 在信号处理中，DFT （离散傅里叶变换）的计算具有举足轻重的地位。但是基于 其复杂的计算，直接应用起来十分麻烦，基于此，本文利用 Matlab 软件对有限长度信号的 DFT 进行改进，提出FFT （快速傅里叶变换），并利用FFT 对所给连续时间和离散时间信号 做了频谱分析。 关 键 词：DFT ，FFT ，有限长度信号，频谱分析。 一、前言： 傅里叶变换在信号处理中具有十分重要的作用，但是基于离散时间的傅里叶变换具有很 大的时间复杂度，根据傅里叶变换理论，对一个有限长度且长度为N 的离散信号，做傅里 叶变换的时间复杂度为 2 ，当 很大时，其实现的时间是相当惊人的（比如当 为 4 O(N ) N N 10 时，其完成时间为 8 （ 为计算机的时钟周期）），故其实现难度是相当大的，同时也严 10   重制约了DFT 在信号分析中的应用，故需要提出一种快速的且有效的算法来实现。 正是鉴于DFT 极其复杂的时间复杂度，1965 年J .W .Cooley 和J .W .Tukey 巧妙地利用 W 因子的周期性和对称性，提出了一个DFT 的快速算法，即快速傅里叶变换（FFT ），从 N 而使得DFT 在信号处理中才得到真正的广泛应用。 本文基于时间抽选奇偶分解，利用Matlab 软件实现快速傅里叶变换。基于所编的FFT 源程序应用的一个实例，本文对有限长度离散时间和连续时间信号进行频谱分析。 二、 FFT 的具体实现、 2.1 DFT 的算法和时间复杂度 对于一个长度为N 的离散信号序列x[n ] ，其DFT 变换为 N 1 X k x n W nk ( )  [ ] N （1） n 0 2 nk j N nk 其中W e 。 N 对任意0 m N 1， N 1 0 1 ( 1) X (m ) x[n ]W nm x[0]W m x[1]W m ...x[N 1]W N  m （2 ） N N N N n 0 1 信号与系统课程设计 nu=log2(n); p1=p; b=zeros(1,n); for t=1:nu; p2=floor(p1/2); b=b*2+(p1-2*p2); p1=p2; end; yr(p+1)=xr(b+1); xr=yr; % 倒位序结束 t=0:n/2-1; %计算因子w 开始 (只计算w0 到w n/2-1) for v=0:n/2-1; w=exp(-2*i*pi*t/n); end; %计算因子w 结束 for m=1:nu;% 计算x(k)开始 h=2^(m-1); k=1; while(kn+1) for t=1:h; y=bitshift(k-1,nu-m,