数字信号处理应用1.doc

快速傅里叶变换原理及算法 课 程 数字信号处理实验 系 （院） 物理与电子科学系 专 业 班 级 学生姓名 学 号  离散傅里叶变换的性质 有限长序列的离散傅里叶变换，简称为离散傅里叶变换，即DFT(Discrete Fourier Transform)。DFT的定义如下。 设有限长序列，它的离散傅里叶变换DFT定义为 ?????????????????????? (1) 根据式(5-112)可以推出公式 ????????????????????? (2) 式(2)称为离散傅里叶反变换(IDFT)。式(1)和式(2)构成一DFT变换对。注意不要把离散傅里叶变换DFT和离散时间傅里叶变换DTFT混淆了。DTFT是对任意序列的傅里叶变换，它的频谱是一个连续函数，而DFT是对有限长序列的离散傅里叶变换，DFT的特点是无论在时域还是在频谱都是离散的，而且都是有限长的。 离散傅里叶变换具有下列性质： 线性 需将较短序列补零后，再按长序列的点数做DFT 循环位移(Circular shift of a sequence) 对称性 (symmetry) 周期共轭对称(Periodic conjugate symmetry)定义为 周期共轭反对称(Periodic conjugate antisymmetry)定义为 循环卷积定理 二、快速傅里叶变换的算法原理 1. 将长序列DFT分解为短序列的DFT 2. 利用旋转因子的周期性、对称性、可约性。将时域序列逐次分解为一组子序列，利用旋转因子的特性，由子序列的DFT来实现整个序列的DFT。 其中：快速傅里叶变换分为两种，分为基2时间抽取算法和基2频率抽取算法 基2时间抽取(Decimation in time)FFT算法 其中:r=0,1,2… 基2频率抽取(Decimation in frequency)FFT算法 三、FFT的特点和规律 FFT算法特点：() （1）共需次迭代； （2）第次迭代对偶结点的偶距为，因此一组结点覆盖的序号个数是。 （3）第次迭代结点的组数为。 (4) 可以预先计算好，而且的变化范围是。 FFT算法流程：() （1）初始化：； （2）第次迭代： （a）下标控制变量初始化； （b）“结点对”的个数初始化; （c） 四、蝶形运算的MATALAB的程序设计 disp(请输入一个8点序列);for ii=1:8 ?????????????????????%自由输入序列x(ii) = input([x(,num2str(ii),)=]); end %整体运用原位计算m=nextpow2(x);N=2^m; % 求x的长度对应的2的最低幂次mif length(x)N x=[x,zeros(1,N-length(x))]; % 若x的长度不是2的幂，补零到2的整数幂end nxd=bin2dec(fliplr(dec2bin([1:N]-1,m)))+1; % 求1:2^m数列序号的倒序y=x(nxd); % 将x倒序排列作为y的初始值for mm=1:m % 将DFT作m次基2分解,从左到右，对每次分解作DFT运算,共做m级蝶形运算，每一级都有2^(mm-1)个蝶形结Nz=2^mm;u=1; % 旋转因子u初始化为WN^0=1WN=exp(-i*2*pi/Nz); % 本次分解的基本DFT因子WN=exp(-i*2*pi/Nz)for j=1:Nz/2 % 本次跨越间隔内的各次蝶形运算,在进行第mm级运算时需要2^(mm-1)个 蝶形for k=j:Nz:N % 本次蝶形运算的跨越间隔为Nz=2^mmkp=k+Nz/2; % 蝶形运算的两个因子对应单元下标的关系t=y(kp)*u; % 蝶形运算的乘积项y(kp)=y(k)-t; % 蝶形运算y(k)=y(k)+t; % 蝶形运算end u=u*WN; % 修改旋转因子,多乘一个基本DFT因子WNend end y y1=fft(x) 五、快速傅里叶变换MATALAB程序设计 function samples(f,Fs,M) N=2^M; % fft点数=取样总点数 Ts=1/Fs; % 取样时间间隔 T=N*Ts; % 取样总时间=取样总点数*取样时间间隔 n=0:N-1; t=n*Ts; Xn=cos(2*f*pi*t); subplot(2,1,1); stem(t,Xn); axis([0 T 1.1*min(Xn) 1.1*max(Xn)]); xlabel(t --); ylabel(Xn); Xk=abs(fft(Xn,N)); subplot(2,1,2); stem(