DFT算法原理、FFT的算法原理

《数字信号处理》课程论文离散傅里叶变换(DFT)算法简介及其应用举例姓名：安昱学号：12011243986专业：通信工程班级：2011级（1）班指导老师：武永峰学院：物理电气信息学院完成日期：2013年11月11日离散傅里叶变换(DFT)算法简介及其应用举例（安昱120112439862011级1班）[摘要]：离散傅立叶变换（DFT）实现了信号首次在频域表示的离散化，使得频域也能够用计算机进行处理。并且这种DFT变换可以有多种实用的快速算法。使信号处理在时、频域的处理和转换均可离散化和快速化。最后就该项目做了总结。[关键词]DFT算法Matlab语言频域采样DFT应用一、DFT算法原理快速傅氏变换（FFT）是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。设x(n)为N项的复数序列，由DFT变换，任一X（m）的计算都需要N次复数乘法和N-1次复数加法，而一次复数乘法等于四次实数乘法和两次实数加法，一次复数加法等于两次实数加法，即使把一次复数乘法和一次复数加法定义成一次“运算”（四次实数乘法和四次实数加法），那么求出N项复数序列的X（m）,即N点DFT变换大约就需要N2次运算。当N=1024点甚至更多的时候，需要N2=1048576次运算，在FFT中，利用WN的周期性和对称性，把一个N项序列（设N=2k,k为正整数），分为两个N/2项的子序列，每个N/2点DFT变换需要（N/2）2次运算，再用N次运算把两个N/2点的DFT变换组合成一个N点的DFT变换。这样变换以后，总的运算次数就变成N+2（N/2）2=N+N2/2。继续上面的例子，N=1024时，总的运算次数就变成了525312次，节省了大约50%的运算量。而如果我们将这种“一分为二”的思想不断进行下去，直到分成两两一组的DFT运算单元，那么N点的DFT变换就只需要Nlog2N次的运算，N在1024点时，运算量仅有10240次，是先前的直接算法的1%，点数越多，运算量的节约就越大，这就是FFT的优越性。二、FFT的算法原理FFT算法的输出X(K)为自然顺序，但为了适应原位计算，其输入序列不是按x(n)的自然顺序排序，这种经过M-1次奇偶抽选后的排序为序列的倒序。因此，在运算之前应先对序列x(n)进行倒序。倒序的规律就是把顺序数的二进制位倒置，即可得到倒序值。倒序数是在M位二进制数最高位加一，逢2向右进位。M位二进制数最高位的权值为N/2，且从左到右二进制位的权值依次为你N/4，N/8，…，2，1。因此，最高位加一相当于十进制运算J+N/2。（J表示当前倒序数的十进制数值）三、DFT的定义设序列x(n)长度为M，定义x(n)的N点DFT为1,...,1,0,)()]([)(210NkenxnxDFTkXknNjNnN式中，N称为离散傅里叶变换区间长度，要求N≥M。为书写简单，令NjNeW2，因此通常将N点DFT表示为101,...,1,0,)()]([)(NnknNNNkWnxnxDFTkX定义X(k)的N点离散傅里叶逆变换(IDFT)为101,...,1,0,)(1)]([)(NnknNNNnWkxNkXIDFTnx四、DFT算法举例1、用DFT(FFT)对时域离散信号进行频谱分析给定参考信号如下：)()(41nRnx其它0748301)(2nnnnnx其它－－0743304)(3nnnnnxnnx4cos)(4:)(5nx用)()(41nRnx以8为周期进行周期性延托形成的周期序列（1）分别以变换区间N=8,16,32对)()(41nRnx进行DFT(FFT),画出相应的幅频特性曲线（2）分别以变换区间N=8,16对)(),(32nxnx分别进行DFT(FFT),画出相应的幅频特性曲线（3）分别以变换区间N=4,8,16对)(4nx分别进行DFT(FFT),画出相应的幅频特性曲线（4）对)(5nx进行频谱分析,请自己选择变换区间,要求画出幅频特性曲线2、MATLAB函数简介MATLAB是一门计算机编程语言，取名来源于MatrixLaboratory，本意是专门以矩阵的方式来处理计算机数据，它把数值计算和可视化环境集成到一起，非常直观，而且提供了大量的函数，使其越来越受到人们的喜爱，工具箱越来越多，应用范围也越来越广泛。本题要用到一维快速傅里叶变换函数fft、取模（实数取绝对值）函数abs和求相位函角函数angle、绘图函数plot和stem。这些函数都属于MATLAB基本函数●fft和ifft：一维快速傅里叶变换和一维快速傅里叶逆变换函数。调用各式如下：Xk=fft(xn,N)采用FFT算法计算时域序列向量xn的N点DFT。缺省N时fft函数自动按x的长度计算x的DFT，返回xn的N点DFT向量Xk。当N为2的整数次幂时，fft按基2FFT算法计算，否则用混合基算法。ifft的调用格式与fft相同。●abs：求绝对值（复数求摸）。y=abs(x)计算实数x的绝对值。当x为复数时得到x的摸（幅度值）。当x为向量时，计算其每个元素的摸。●angle：求相角。ph=angle(x)计算复向量x的每个元素的相角（rad），返回相位向量ph。Ph值介于–π和+π之间。下面的简单程序就可以实现计算矩形序列x1(n)的32点FFT,并画出幅频特性和相频特性曲线。%ex1.m:几个函数调用举例x1n=[11111111];x1k=fft(x1n,32);%计算32点fftx1m=abs(x1k);%计算32点fft的模ph1=angle(x1k);%计算32点fft的相位k=0:31;%以下为绘图部分subplot(2,1,1);stem(k,x1m,'.');gridonxlabel('k');ylabel('幅度')subplot(2,1,2);stem(k,ph1,'.');gridonxlabel('k');ylabel('相位')运行结果如图所示。矩形序列的32点DFT五、实验总结快速傅里叶变换（FFT）是离散傅里叶变换（DFT）的快速算法。它是数字信号处理领域中的一项重大突破。它考虑了计算机和数字硬件实现的约束条件，研究了有利于机器操作的运算结构，使DFT的计算时间缩短了1-2个数量级有效地减少了计算所需的存储容量。我们只有熟练DFT的理论算法才能更好的运用MATLAB来计算。[参考文献][1]刘智敏.误差与数据处理[M].北京：原子能出版社，1981.[2]HansemanD,LittefieldB,李人厚.张平安等校译.精通MATLAB5综合辅导与指南[M].西安：交通大学出版社，2001.[3]高西全.数字信号处理[M]西安电子科技大学出版社，2000