《基于matlabfft算法设计》由会员分享，可在线阅读，更多相关《基于matlabfft算法设计（35页珍藏版）》请在金锄头文库上搜索。
1、唐唐 山山 学学 院院数字信号处理数字信号处理课课 程程 设设 计计题题目目基于基于 MATLAB 的的 FFT 算法的设计算法的设计系系(部部)智能与信息工程学院智能与信息工程学院班班级级13 电信电信本本 1 班班姓姓名名李玉娇李玉娇学学号号4130220204指导教师指导教师王超王超张雅静张雅静2016 年年2 月月29日至日至3 月月11日日共共2周周2016 年年3 月月11 日日目录1 引言12 设计任务和原理22.1 设计任务.22.2 设计原理.23 软件介绍.53.1 软件概述.53.2 界面基本操作.53.3 MATLAB 主要特点84 MATLAB 程序实现.94.1 程
2、序流程图.94.2 程序分析.94.2.1 原始图像程序及分析.94.2.2 灰度图像程序及分析.104.2.3 自建的 FFT 程序及分析114.2.4 自建的 IFFT 程序及分析.124.2.5 内置的 FFT 程序及分析124.2.6 内置的 IFFT 程序及分析.134.3 程序运行结果.134.4 自建 FFT 与内置 FFT 图形及比较.144.5 IFFT 结果与原灰度图形及比较155 GUI 界面.165.1 GUI 简介.165.2 界面设计.165.3 运行调试.196 总结体会.20参考文献21附录 FFT 算法的程序.22附录 GUI 设计的程序.26课程设计说明书课
3、程设计说明书11 引言数字信号处理（Digital Signal Processing，DSP）是一门涉及许多学科而又广泛应用于许多领域的新兴学科，是一种通过使用数学技巧执行转换或提取信息，来处理显示信号的方法，这些信号由数字序列表示。随着信息时代，数字时代的到来，数字信号处理已经成为一门极其重要的学科和技术领域。以 DSP 为核心芯片的处理系统日益变成了数字信号处理系统的主流。它广泛用于电子信息、通信、图像处理、语音处理、生物医学、自动控制、地质探测等领域，受到工程设计和使用人员的青睐。FFT（Fast Fourier Transformation），即为快速傅立叶变换，是离散傅立叶变换的快
4、速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步，在实际应用中，FFT 是最常见的数字信号处理算法，它在各种数字信号处理系统中扮演重要的角色。在信号处理过程中。频域分析往往比时域分析方便和高效，FFT是时域和频域转换的基本运算。正是鉴于 DFT 极为复杂的时间复杂度，1965 年 J.W.Cooley 和 J.W.Tukey 巧妙的利用 WN因子的周期性和对称性，提出了一个 DFT 的快速算法，即快速傅立叶变换（FFT），从而使得 DFT 在信号
5、处理中才得到真正的广泛应用。DFT 是一种应用广泛的数学变换工具，MATLAB 是一款功能强大的科学计算语言。MATLAB 提供的 FFT 函数解决了 DFT 的快速计算问题，但由于它是内建函数而不能了解到软件实现的过程。本文以按时间抽取的基 2FFT 算法为例，根据快速傅立叶变换的原理和规律，绘出了算法实现的程序框图，列出了MATLAB 环境下软件实现的程序，建立了从算法理论到程序实现的完整概念。在信号处理中，DFT（离散傅立叶变换）的计算具有举足轻重的地位。但是基于其复杂的计算，直接应用起来十分麻烦，基于此，本文利用 MATLAB 软件对有限长度信号的 DFT 进行改进，提出 FFT（快速
6、傅立叶变换），并利用 FFT对所给连续时间和离散时间信号做了频谱分析。图像信号的处理主要是用 MATLAB 作为工具平台，设计中涉及到图像的选取、存储和读取、灰度处理、FFT 变换、IFFT 变换、频谱分析。通过数字信号处理课程的理论知识的综合运用，以及选做系统人机对话界面，用 GUI 界面完成人机交互使用，从实践上初步实现对数字信号的处理。课程设计说明书课程设计说明书22 设计任务和原理2.1 设计任务所设计的 FFT 算法应完成以下功能：(1)在 MATLAB 环境下编写 FFT 算法（不调用系统现有函数）；(2)实现对选定图片进行 FFT 计算、还原（IFFT 计算），并与系统 FFT
7、函数做对比，进行分析；(3)设计 GUI 界面。设计要求：1.根据题目要求进行算法 GUI 总体设计。2.完成算法具体部分的设计。(1)算法原理图。(2)算法原理说明。3.算法程序的设计。(1)对选定图片进行自编 FFT 计算与还原，并与自带函数进行对比；(2)完整源程序。2.2 设计原理对于有限长序列 x(n)， 若要求其 N 点的傅里叶变换(DFT)需要经过2N次复数乘法运算和 N*(N-1)次复数加法运算。随着 N 的增加，运算量将急剧增加，而在实际问题中，N 往往是较大的，如当 N=1024 时，完成复数乘法和复数加法的次数分别为百万以上，无论是用通用计算机还是用 DSP 芯片，都需要
8、消耗大量的时间和机器内存，不能满足实时的要求。因此，DFT 的这种运算只能进行理论上的计算，不适合对实时处理要求高的场合。因此，研究作为 DSP 的快速算法的 FFT 是相当必要的， 快速傅里叶变换(FFT)是为提高 DFT 运算速度而采用的一种算法，快速算法的种类很多，而且目前仍在改进和提高，它是根据离散傅里叶变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。基于本学期所学的 DIT-FFT 的运算规律和编程思想以及 MATLAB 的学习和使用， 本课设要求在 MATLAB 环境下编写基-2DIT-FFT 算法实现对离散信号的快速傅里叶变换， 再与 MATLAB 软件自带的
9、FFT 函数实现对离散信号的傅里叶变换进行比较，如果得到的频谱相同，那么我们编写的程序就是正确的。其中离散信号是自己选取的图像信号， 用 MATLAB 处理得到频谱图以及选用系统人机对话界面，用 GUI 界面完成人机交互。快速傅立叶变换（FFT）是为提高 DFT 运算速度而采用的一种算法。课程设计说明书课程设计说明书3对一个有限长度序列x(n)的 N 点的 DFT 为：10Xk(n),0,1, 2,., N1NnkN nxkW（） =101X(k),n0,1,2,.,N 1NnkN kxNW（n）=所以，要求 N 点的 DFT，需 N2的复数乘法运算，) 1(*NN次复数乘法运算。随着 N 的
10、增加，运算量将急剧增加，而在实际问题中，N 往往是较大的，如当 N=1024 时，完成复数乘法和复数加法的次数分别为百万以上，无论是用通用计算机还是用 DSP 芯片，都需要消耗大量的时间，不能满足事实的要求，不适合对实时处理要求高的场合。为了能实时处理 DFT，要想减少 DFT 的运算量可以有两个途径：一是降 N，N 的值减小了，运算量就减少了；第二是利用旋转因子的周期性，对称性和可约性。利用这两个途径实现 DFT 的快速傅立叶变换（FFT），FFT 算法基本上可分为按时间抽取的 FFT 算法（FFT）和按频率抽取的 FFT 算法（FFT）。旋转因子的性质：周期性(k N)n(n N)Nknk
11、NNWWW共轭对称性( k)n( n)N*knkNNWWW可约性WkmmnkNnNW,/Wkmmk nNN nW本次课设要求用基 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/4 点序列，最后，将原序列划分为多个 2 点
12、序列，将计算量大大降低。按时间下标的奇偶将 N 点 x(n)分别抽取组成两个 N/2 点序列， 分别记为 x1(n)和 x2(n)，将的 DFT 转化为 x1(n)和 x2(n)的 DFT 的计算。12, 1 , 0,)() 12()()2(21 Nrrxrxrxrx课程设计说明书课程设计说明书4利用旋转因子的可约性，即：用蝶形运算可表示为如图 2-1 所示：以此类推，还可以按 n 值的奇偶分为两个序列，这样就达到了降 N 的目的，从而减少了运算量。FFT 和 DFT 的数学运算量改进。直接采用 DFT 进行运算， 运算量为2N次复数乘法和) 1( NN次复数乘法。当采用 M 次 FFT 时，
13、由MN2求得logMN，运算流图有 M 级蝶形，每一级都由 N/2 个蝶形运算构成， 这样每一级蝶形运算都需要 N/2 次复数乘法和 N次复数加法。M 级运算共需要复数乘法次数为2/ )*(MNC ，复数加法次数为MNC。当 N 值较大时，FFT 减少运算量的特点表现的越明显。 1N 021NN 0,2,4.1,3,5.1122212 NN 0,10,11122212 1N2N 0,10,1221N nknNN nknknnNNrkrkrrNNrkrkrrX kx n Wx n Wx n Wxr WxrWx r Wxr W2j2j2222eerkNrkrkrkN NNWW 1122122200
14、12, 01NNrkkrk NNN rrk NX kxr WWxr WXkW XkN（ ）（k）图 2-1 DIT-FFT 蝶形运算流图符号课程设计说明书课程设计说明书53 软件介绍3.1 软件概述MATLAB 是矩阵实验室（Matrix Laboratory）的简称，是美国 MathWorks公司出品的商业数学软件，主要包括 MATLAB 和 Simulink 两大部分。MATLAB 主要面对科学计算、可视化以及交互式程序设计的高科技计算环境。它将数值分析、矩阵计算、科学数据可视化以及非线性动态系统的建模和仿真等诸多强大功能集成在一个易于使用的视窗环境中，为科学研究、工程设计以及必须进行有效
15、数值计算的众多科学领域提供了一种全面的解决方案， 并在很大程度上摆脱了传统非交互式程序设计语言的编辑模式， 代表了当今国际科学计算软件的先进水平。MATLAB 在数学类科技应用软件中在数值计算方面首屈一指。 MATLAB 可以进行矩阵运算、绘制函数和数据、实现算法、创建用户界面、连接其他编程语言的程序等，主要应用于工程计算、控制设计、信号处理与通讯、图像处理、信号检测、金融建模设计与分析等领域。MATLAB 的基本数据单位是矩阵，它的指令表达式与数学、工程中常用的形式十分相似，故用 MATLAB 来解算问题要比用 C、FORTRAN 等语言完成相同的事情简捷得多， 并且MATLAB也吸收了像M
16、aple等软件的优点， 使MATLAB成为一个强大的数学软件。用户可以直接调用，用户也可以将自己编写的实用程序导入到 MATLAB 函数库中方便自己以后调用，此外许多的 MATLAB 爱好者都编写了一些经典的程序，用户可以直接进行下载就可以用。3.2 界面基本操作1 启动 MATLAB双击桌面上的 MATLAB 快捷方式或选择程序菜单中的 MATLAB 选项，即可进入。启动打开界面如图 3-1 所示：图 3-1 MATLAB 启动界面课程设计说明书课程设计说明书62 工作环境界面 打开界面后，产生的工作环境界面如图 3-2 所示，它包含一个工作栏、三个 区域、四个工作窗口。其中四个工作窗口分别为指令窗口（Command Windows） 、 指令历史窗口（Command history）、工作空间窗口（workspace
