目录1 引言 (1)2 基于MATLAB的FFT算法实现 (2)2.1系统总体流程图 (2)2.2 FFT运算规律及编程思想 (2)2.2.1图像信号的采集 (2)2.2.2 DIT-FFT算法的基本原理 (3)2.2.3 FFT算法的运算规律及编程思想 (5)3 Matlab程序实现 (7)3.1程序运行结果 (7)3.2对比结果分析 (8)4 系统人机对话界面 (9)4.1 GUI简介 (9)4.2 界面设计 (9)4.3 运行调试 (10)5 Matlab软件简介 (11)6 心得体会 (12)参考文献 (13)附录Ⅰ (14)附录Ⅱ (18)1 引言MATLAB是矩阵实验室（Matrix Laboratory）的简称，是美国MathWorks 公司出品的商数学软件，用于算法开发、数据可视化、数据分析以及数值计算的高级技术计算语言和交互式环境，主要包括MATLAB和Simulink两大部分。
MATLAB 的应用范围非常广，包括信号和图像处理、通讯、控制系统设计、测试和测量、财务建模和分析以及计算生物学等众多应用领域。
附加的工具箱（单独提供的专用MATLAB 函数集）扩展了MATLAB 环境，以解决这些应用领域内特定类型的问题。
它以矩阵运算为基础，把计算、可视化、程序设计融合在一个简单易用的交互式工作环境中，是一款数据分析和处理功能都非常强大的工程适用软件。
它可以将声音文件变换为离散的数据文件，然后利用其强大的矩阵运算能力处理数据，如数据滤波、傅立叶变换、时域和频域分析、声音回放以及各种图的呈现等，它的信号处理与分析工具箱位语音信号分析提供了十分丰富的功能函数，利用这些功能函数可以快捷而又方便的完成语音信号的处理和分析以及信号的可视化。
数字信号处理是MATLAB重要应用的领域之一。
对于有限长序列x(n),若要求其N点的傅里叶变换（DFT）需要经过2N次复数乘法运算和N*(N-1)次复数加法运算。
随着N的增加，运算量将急剧增加，而在实际问题中，N往往是较大的，如当N=1024时，完成复数乘法和复数加法的次数分别为百万以上，无论是用通用计算机还是用DSP芯片，都需要消耗大量的时间和机器内存，不能满足实时的要求。
因此，DFT的这种运算只能进行理论上的计算，不适合对实时处理要求高的场合。
因此，研究作为DSP的快速算法的FFT是相当必要的，快速傅里叶变换（FFT）是为提高DFT运算速度而采用的一种算法，快速算法的种类很多，而且目前仍在改进和提高，它是根据离散傅里叶变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。
基于本学期所学的DIT-FFT的运算规律和编程思想以及Matlab的学习和使用，本课设要求在Matlab环境下编写基2 DIT-FFT算法实现对离散信号的快速傅里叶变换，再与Matlab软件自带的FFT函数实现对离散信号的傅里叶变换进行比较，如果得到的频谱相同，那么我们编写的程序就是正确的。
本次课程设计是实现对选定图片进行FFT计算、还原（IFFT计算），并与系统FFT函数做对比，进行分析。
如果有能力可以选做系统人机对话界面。
用GUI界面完成人机交互方便使用的。
本课程设计主要是对数字信号的分析。
2 基于MATLAB的FFT算法实现2.1系统总体流程图本设计要求找到一张明暗对比较大的图片；在Matlab环境下编写基FFT算法；利用自己编写的算法对已选择的图片信号进行计算，并显示出计算的结果，将计算的结果与Matlab数字信号处理工具箱中自带的fft函数进行对比研究，验证自编算法的正确性。
系统的总体设计流程图如图2-1所示：图2-1 系统的总体设计流程图2.2 FFT运算规律及编程思想2.2.1图像信号的采集图像信号最好采用明暗对比比较大的灰度图像进行分析，这样实验结果对比比较明显。
在Matlab中用语句：[filename, pathname]=uigetfile({'*.jpg;*.tif;*.bmp;*.gif' },'File Selector');image=imread(strcat(pathname,filename));用于读取图片的信号，Matlab 图像分析支持多种格式的图像信号，用上述语句时，在Matlab 中分析图像的时候可以系统自动检索所需分析的图片。
语句：image=rgb2gray(image);可以对图像进行灰度处理。
当我们要将图片显示出来的的时候只需要用语句： imshow(image)；本次课程设计就是分析灰度图像。
通过用两种不同的方法对灰度图像的FFT 计算和IFFT 计算，来得到我们想要的结果。
采集到图像信号之后，就可以对图像信号进行分析和计算了。
2.2.2 DIT-FFT 算法的基本原理快速傅里叶变换（FFT ）是为提高DFT 运算速度而采用的一种算法。
对一个有限长度序列x(n)的N 点的DFT 为：所以，要求N 点的DFT,需要N2次的复数乘法运算,N*(N-1)次复数乘法运算算。
随着N 的增加，运算量将急剧增加，而在实际问题中，N 往往是较大的，如当N=1024时，完成复数乘法和复数加法的次数分别为百万以上，无论是用通用计算机还是用DSP 芯片，都需要消耗大量的时间，不能满足实时的要求,，不适合于对实时处理要求高的场合。
为了能实时处理DFT,要想减少DFT 的运算量可以有两个途径：第一是降N ，N 的值减小了，运算量就减少了；第二是利用旋转因子的周期性，对称性和可约性。
利用这两个途径实现DFT 的快速傅里叶变换（FFT ），FFT 算法基本上可分为按时间抽取的FFT 算法（DIT-FFT ）和按频率抽取的FFT 算法（DIF-FFT ）。
旋转因子的性质： （1）周期性 （2）共轭对称性 （3）可约性本次课设要求用用基2的按时间抽取的FFT 算法（DIT-FFT ）实现FFT 功能，设序列x(n)的长度为N ，且N 满足N=2M,M 为正整数。
若N 不能满足上述关系，可以将序列x(n)补零实现。
按时间抽取基2-FFT 算法的基本思路是将N 点序列按时间下标的奇偶分为两个N/2点序列，计算这两个N/2点序列的N/2点DFT ，计算量可减小约一半；每一个N/2点序列按照同样的划分原则，可以划分为两个)()(N n k N n N k N kn N W W W ++==*)(*)(][][n k N n k N kn N W W W --==mkn mN kn N mkn mN kn N W W W W //,==N/4点序列，最后，将原序列划分为多个2点序列，将计算量大大降低。
按时间下标的奇偶将N点x(n)分别抽取组成两个N/2点序列，分别记为x1(n)和x2(n)，将x(n)的DFT转化为x1(n)和x2(n)的DFT的计算。
利用旋转因子的可约性，即：用蝶形运算可表示为如图2-2所示：以此类推，还可以把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。
()()()()()()()()()()1N21N N0,2,4...1,3,5...1122212N N0,10,111222121N2N0,10,1221NnknN Nnk nkn nN Nr krkr rN Nr krkr rX k x n Wx n W x n Wx r W x r Wx r W x r W-=--==--+==--+====+=++=+∑∑∑∑∑∑∑2j2j2222e erkNrkrk rkNN NW Wππ--===()()()112212220012,01N Nrk k rkN N Nr rkNX k x r W W x r WX k W X k N--===+=+≤≤-∑∑（）（k）图2-2 DIT-FFT蝶形运算流图符号12,,1,0,)()12()()2(21-=⎭⎬⎫=+=Nrrxrxrxrx当N 值较大时，FFT 减少运算量的特点表现的越明显。
2.2.3 FFT 算法的运算规律及编程思想为了编写DIT-FFT 算法的运算程序，首先要分析其运算规律，总结编程思想并绘出程序框图。
1. 原位计算对MN 2=点的FFT 共进行M 级运算，每级由N/2个蝶形运算组成。
在同一级中，每个蝶的输入数据只对本蝶有用，且输出节点与输入节点在同一水平线上，这就意味着每算完一个蝶后，所得数据可立即存入原输入数据所占用的数组元素(存储单元)，这种原位(址)计算的方法可节省大量内存。
2. 蝶形运算实现FFT 运算的核心是蝶形运算，找出蝶形运算的规律是编程的基础。
蝶形运算是分级进行的；每级的蝶形运算可以按旋转因子的指数大小排序进行；如果指数大小一样则可从上往下依次蝶算。
对MN 2=点的FFT 共有M 级运算，用L 表示从左到右的运算级数(L=1，2，…，M )。
第L 级共有12-=L B 个不同指数的旋转因子，用R 表示这些不同指数旋转因子从上到下的顺序(R=0，1，…，B-1)。
第R 个旋转因子的指数R P L M -=2，旋转因子指数为P 的第一个蝶的第一节点标号k 从R 开始，由于本级中旋转因子指数相同的蝶共有L M -2个，且这些蝶的相邻间距为L 2，故旋转因子指数为P 的最后一个蝶的第一节点标号k 为：R N R L L L M +-=+⋅--22)12(，本级中各蝶的第二个节点与第一个节点都相距B 点。
应用原位计算，蝶形运算可表示成如下形式：L A (J)= 1-L A (J)+ 1-L A (J+B)* PN WL A (J+B)= 1-L A (J)-1-L A (J+B)* PN W总结上述运算规律，可采用如下运算方法进行DIT-FFT 运算。
首先读入数据，根据数据长度确定运算级数M ，运算总点数MN 2=，不足补0处理。
然后对读入数据进行数据倒序操作。
数据倒序后从第1级开始逐级进行，共进行M 级运算。
在进行第L 级运算时，先算出该级不同旋转因子的个数12-=L B (也是该级中各个蝶形运算两输入数据的间距)，再从R=0开始按序计算，直到R=B-1结束。
每个R 对应的旋转因子指数R P L M -=2，旋转因子指数相同的蝶从上往下依次逐个运算，各个蝶的第一节点标号k 都是从R 开始，以L 2为步长，到R N L+-2(可简取极值N-2)结束。