用matlab实现DFT-FFT

1用matlab实现DFTFFT目录实验目的...........................................................................................................................................2实验内容...........................................................................................................................................21.用MATLAB实现DFT.................................................................................................................22.用MATLAB实现FFT，分析有限离散序列的FFT..................................................................33.通过分别计算时间，得出DFT与FFT的算法差异..............................................................7实验原理...........................................................................................................................................71.离散傅里叶变换的快速算法FFT.........................................................................................72.FFT提高运算速度的原理.....................................................................................................83.理论分析DFT与FFT算法差异..........................................................................................10实验步骤.........................................................................................................................................11实验结果.........................................................................................................................................11实验分析.........................................................................................................................................21实验结论.........................................................................................................................................25实验体会.........................................................................................................................................262实验目的1.通过研究DFT,FFT性质，用语言实现DFT,FFT。不使用MATLAB现有的FFT函数，自己编写具体算法。2.掌握FFT基2时间抽选法，理解其提高减少乘法运算次数提高运算速度的原理。3.设计实验，得出DFT和FFT算法差异的证明，如复杂度等(精度、不同长度的序列等）。实验内容1.用MATLAB实现DFTN点序列x(n)的DFT为：X(k)=∑x(n)WNnk0≤k≤N−1𝑁−1𝑛=0DFT的矩阵为：根据DFT公式与矩阵展开，通过MATLAB实现DFT：32.用Matlab实现FFT编程思想及程序框图：原位计算因为DIT-FFT与DIF-FFT的算法类似，这里我们以DIT-FFT为例。N=2M点的FFT共进行M级运算，且每一级都由N/2个蝶形运算组成，后一级的节点数据由前一级同处一条水平线位置的节点数据产生，所以我们同样可以将后一级的节点数据储存到前一级的节点中，这样的方法叫做原位计算，它大大节省了内存资源，降低了成本，简化了运算。序列的倒序无论是进行DIT-FFT还是DIF-FFT都需要进行倒序，包括输入倒序与输出倒序，以一定的方式将数组进行重新排列。倒序的方法：首先由于N=2M,我们就可以用M位二进制数来表示节点的顺序，并且按照奇偶时域抽取。然后，如图1所示，第一次按最低位n0的0、1值分解为奇偶组，第二次按次低位n1的0、1值分解为奇偶组，以此类推。最后，所得二进制数所对应的十进制数即为序列倒序后产生的序列。图1序列倒序过程倒序的MATLAB方法：用雷德算法可以对输入信号序列进行倒序重排，流程图如下所示：4蝴蝶因子的变化规律在DIT-FFT中，每一级都由N/2个蝶形运算构成，每个蝶形运算包含一个蝴蝶因子，每一级的蝶形因子又有一定的变化规律：设L表示自左而右的运算级次（L=1,2,3,…,M），序数R，次数K。每个蝶形运算的两个输入量相距B=2^(L-1)个点。假设N=8，则M=3，这时有：L=1时，B=1，S=N/2，R=0，K=1:N/2则有P=(K-1)*1，所以WNP=WNJ，J=0,1,2,3L=2时，B=2，S=N/4，R=0:N/2:N-1，K=1:N/4则有P=(K-1)*2，所以WNP=WN/2J，J=0,2L=3时，B=4，S=N/8，R=0:N/4:N-1，K=1:N/8则有P=(K-1)*4，所以WNP=WN/4J，J=05所以对于一般情况N=2M，第L级的旋转因子为P=(K-1)*B。从而得到DIT-FFT的Matlab流程图：6DIT-FFT的MATLAB实现为（以对x(n)=cos(nπ6)进行16点的变化为例）：73.通过分别计算时间，得出DFT与FFT的算法差异：法一：对N=512，1024，2048和4096点的离散时间信号x(n)，用Matlab语言编程分别以DFT和FFT计算N个频率样值X(k)，比较两者所用时间的大小。设x(n)=cos(nπ6)。利用TIC,TOC函数，分别跟踪变换时间。法二：利用clock返回当前日期向量的时间，通过etime（）函数返回走过的日期向量的时间。用MATLAB实现如下：实验原理1.离散傅里叶变换的快速算法FFTN点序列x(n)的DFT为：X(k)=∑x(n)WNnk0≤k≤N−1𝑁−1𝑛=0（1）由于系数WNnk=e−j2πNnk是一个周期函数：WNn(N−k)=WNk(N−n)=WN−nk（2）且是对称的：8WNnk+N/2=−WNnk（3）快速傅里叶变换算法正是基于这样的基本思想而发展起来的，它的算法基本可以分称两大类：时间抽取法（DIT-FFT）和频率抽取（DIF-FFT）。由于DIF-FFT算法思想基本一致，只是划分方式略有差异，所以这里以DIT-FFT算法为例进行说明。当N是2的整数次方时，称为基2的FFT算法。首先将序列x(n)分解为两组，偶数项为一组，奇数项为一组：{x(2r)=x1(r)x(2r+1)=x2(r)r=0,1,…，N2−1(4)将x1(r)和x2(r)分别进行N/2点的DFT得X1(k)和X2(k)，且：{X(k)=X1(k)+WNkX2(k)X(N2+k)=X1(k)−WNkX2(k)r=0,1,…，N2−1(5)重复这一过程，可得到x（n）的FFT。2.FFT提高运算速度的原理FFT算法将长序列的DFT分解为短序列的DFT。N点的DFT先分解为2个N/2点的DFT，每个N/2点的DFT又分解为N/4点的DFT，以此类推。最小变换的点数即所谓的“基数”，这个基数是2点的DFT（又叫蝴蝶因子）。如公式（5）所示，对于X（k）的计算可以分为两部分，因为在上下两个式子中都出现了X1(k)与X2(k)，因此只需要一次复数乘法与两次复数加法即可分别得到N/2点的DFT，从而得到总的N点的DFT。如图2所示。X1(k)X1(k)+WNkX2(k)WNkX2(k)X1(k)−WNkX2(k)图2DIT-FFT蝴蝶因子下图为DIT-FFT与DIF-FFT蝴蝶因子的三种形式：9图3DIT-FFT和DIF-FFT的蝴蝶因子(1)原始形式；（2）简化形式；（3）优化形式下面以8点的DIT-FFT为例：图48点的DIT-FFT对于8点的FFT，我们需要M=log28=3阶运算，每一阶有四个蝴蝶因子，在每个蝴蝶因10子中需要1次复数乘法与两次复数加法，因为每个蝴蝶因子都一样，所以FFT通过重复运算大大简化了算法与复杂度。3.理论分析DFT与FFT算法差异DFTX(k)=∑x(n)WNnk0≤k≤N−1𝑁−1𝑛=0DFT算法复杂度的计算：复数乘法复数加法一次X(k)NN-1N次X(k)(N点DFT)N2N(N-1)对于N=512、1024和8192的DFT，分别需要复数乘法（次）N2=5122=218=262144N2=10242=220=1048576N2=81922=226=67108864这是一个巨大的数字，很难在实际中应用。FFT{X(k)=X1(k)+WNkX2(k)X(N2+k)=X1(k)−WNkX2(k)r=0,1,…，N2−1FFT算法复杂度的计算：对于N=2M点的FFT,需要M=log2N阶的重复运算；每一阶有N/2个蝴蝶因子；每一个蝴蝶因子需要1此复数乘与2次复数加。复数乘法复数加法N点FFTN2log2NNlog2N对于N=512、1024和8192的DFT，分别需要复数乘法（次）N2log2N=5122log2512=230411N2log2N=10242log21024=5120N2log2N=81922log28192=53248相比于DFT，FFT的运算复杂度大大降低了。实验步骤1.若x(n)=cos(nπ6)是一个N=16的有限序列，利用MATLAB计算它的DFT并画出图形。若N不等于2的整数次方，假设N=12，利用MATLAB计算它的DFT并画出图形。2.若x(n)=cos(nπ6)是一个N=16的有限序列，利用MATLAB计算它的FFT并画出图形。若N不等于2的整数次方，假设N=12，利用MATLAB计算它的FFT并画出图形。3.根据上述两个步骤的实验结果，比较DFT与FFT在算法与结果上的相同与差异。4.通过对N=8的有限序列x(n)=[2,4,-1,0,-2,-4,3,1]进行FFT变换，在MATLAB中加入disp（）函数以及序列存储单元，跟踪并分别展示：输入到各存储单元的数据倒序后各存储单元的数据各运算级次对应的该级运算后存储单元的数据输出各存储单元的数据通过数据分析FFT具体算法，更深入地理解FFT。5.通过tic（），toc（）函数，计算不同长度序列的DFT与FFT所用时间，得到二者算