数字信号处理设计master-副本.docx

FFT算法的matlab实现及应用研究一、设计要求：1.编程实现FFT算法；2.运用编写的FFT程序对信号进行FFT计算和还原，待分析的信号自行选择和产生，可以是一段音乐，可以是自己录入的语音信号或者是一副图像等；3.与matlab的FFT函数进行比较；3.设计系统界面。本次设计选择对图片进行处理，对该图像进行FFT变换。在Matlab环境下编写基2 DIT-FFT算法；利用自己编写的算法对选取的图片进行计算和恢复，并与Matlab数字信号处理工具箱中的fft函数进行对比研究，验证自编算法的正确性。设计系统界面二、系统总体流程图：三、FFT算法的基本原理快速傅里叶变换FFT是为提高DFT运算速度而采用的一种算法，对一个有限长度序列x(n)的N点的DFT为：所以，要求N点的DFT,需要N2次的复数乘法运算,N*(N-1)次复数乘法运算算。随着N的增加，运算量将急剧增加，而在实际问题中，N往往是较大的，因此无论是用通用计算机还是用DSP芯片，都需要消耗大量的时间，不能满足实时的要求,不适合于对实时处理要求高的场合。为了能实时处理DFT,要想减少DFT的运算量可以有两个途径：第一是降N，N的值减小了，运算量就减少了；第二是利用旋转因子的周期性，对称性和可约性。利用这两个途径实现DFT的快速傅里叶变换FFT，FFT算法基本上可分为时域抽取基2FFT算法和频域抽取基2FFT算法。旋转因子具有周期性，共轭对称性以及可约性。1）、本次课设选择时域抽取基2FFT算法来实现FFT功能，序列x(n)的长度为N，且N满足N=2M,M为正整数。若N不能满足上述关系，可以将序列x(n)补零实现。按时域抽取基2-FFT算法的基本思路是将N点序列按时间下标的奇偶分为两个N/2点序列，计算这两个N/2点序列的N/2点DFT；每一个N/2点序列按照同样的划分原则，可以划分为两个N/4点序列，最后，将原序列划分为多个2点序列，将计算量大大降低。时间下标的奇偶将N点x(n)分别抽取组成两个N/2点序列，分别记为x1(n)和x2(n)，将x(n)的DFT转化为x1(n)和x2(n)的DFT的计算。利用旋转因子的可约性，即：用蝶形图表示如下： X1(k)X(K)=X1(k)+ WNK X2(k) WNK X2(k)X(K+N/2)=X1(k)-WNK X2(k)依此类推，还可以把x1(n)和x2(n)按n值得奇偶分为两个序列，这样就达到了降N得目的，从而减少了运算量。FFT对DFT的数学运算量改进：直接采用DFT进行计算，运算量为N2次复数乘法和N*(N-1)次复数乘法。当采用M次FFT时，由N=2M求得M=logN，运算流图有M级蝶形，每一级都由N/2个蝶形运算构成，这样每一级蝶形运算都需要N/2次复数乘法和N次复数加法。M级运算共需要复数乘法次数为C=N/2*M,复数加法次数为C=N*M。当N值较大时，FFT减少运算量的特点表现的越明显。四、FFT算法的运算规律及编程思想1)、对图片的选择保存一张图片，格式为bmp，jpg或者是gif中的任何一种。并将该图片文件保存在电脑的某个盘中。[filename,pathname]=uigetfile({*.jpg;*.tif;*.bmp;*.gif },File Selector);image=imread(strcat(pathname,filename)); 这些代码实现了对图片的路径进行的选择，只要找到保存图片的位置即可打开图片。if ndims(image)==3 image=rgb2gray(image); end 这些代码实现了对图片进行灰度变换，可以将原来是彩色的图片变换成黑白色，目的是为了取点时方便简单，而且速度更快，节省时间2）、T运算的核心是蝶形运算，找出蝶形运算的规律是编程的基础。对N=2M点的FFT共有M级运算，用L表示从左到右的运算级数(L=1，2，…，M )。 第L级共有B=2L-1个不同指数的旋转因子，用R表示这些不同指数旋转因子从上到下的顺序(R=0，1，…，B-1)。第R个旋转因子的指数P=2M-LR，旋转因子指数为P的第一个蝶的第一节点标号k从R开始，由于本级中旋转因子指数相同的蝶共有2M-L个，且这些蝶的相邻间距为2L，故旋转因子指数为P的最后一个蝶的第一节点标号k为：(2M-L-1)2L+R=N-2L+R个节点与第 一个节点都相距B点。总结上述运算规律，可采用如下运算方法进行DIT-FFT运算。首先读入数据，根据数据长度确定运算级数M，运算总点N=2M，不足补0处理。然后对读入 数据进行数据倒序操作。运算时，先算出该级不同旋转因子的个数(也是该级中各个蝶形运算两输入数据的间距)，再从R=0开始按序计算，直到R=B-1结束。每个R对应的旋转因子指数P=