logo资料库

FFT毕业论文.doc

第1页 / 共31页
第2页 / 共31页
第3页 / 共31页
第4页 / 共31页
第5页 / 共31页
第6页 / 共31页
第7页 / 共31页
第8页 / 共31页
资料共31页,剩余部分请下载后查看
第一章绪论
1.1.引言
1.2 FFT算法的研究与发展
第二章基本理论
2.1 FFT算法的基本概念
2.1.1离散傅里叶变换(DFT)
设x(n) 是一个长度为 N 的有限长序列,定义x(n) 的 N 点离散傅立叶变换为
(2.2.1)
2.2.FFT算法的分类
第四章FFT算法的分析
第五章 总结与展望
参考文献
致谢
学号: 24061900250 毕业设计 题 目 : FFT 算 法 的 研 究 与 Matlab 编 程 实 现 作 系 者 别 指导老师 完成时间 2010.05 届 专 职 别 业 电子信息工程 称 1
摘 要 快速傅里叶变 (|Fas Fourier Tranformation,FFT)是将一个大点数 N 的 DFT 分解为若干小点的 D F T 的组合。将用运算工作量明显降低, 从而大大提高 离 散傅里叶变换(D F T) 的计算速度。因各个科学技术领域广泛的使用了 FFT 技术 它大大推动了信号处理技术的进步,现已成为数字信号处理强有力的工具,本论 文将比较全面的叙述各种快速傅里叶变换算法原理、特点,并完成了基于 MATLAB 的实现。 关键词:离散傅立叶变换;快速傅立叶变换;蝶形单元;MATLAB 1
Abstract Keyword: 2
目 录 第一章 绪 论 ................................................................ 4 1.1 FFT 算法的意义 .....................................错误!未定义书签。 1.2 研究目标、内容 ........................................................ 5 第二章 基本理论 ............................................................... 6 2.1 FFT 算法基本概念 ...................................................... 6 2.1.1 离散傅里叶变换(DFT) ........................................... 7 2.1.2 快速傅里叶变换(FFT) 2.2 FFT 算法分类 .......................................................... 8 2.2.1 基 2、DIT-FFT(按时间抽取) 2.2.2 基 2、DIF-FFT(按频率抽取) 2.2.3 基 4、DIF-FFT(按频率抽取) 2.2.4 分裂基 FFT 算法 2.2.5 N 为组合数的 FFT——混合基算法 2.2.6 Chirp-z 变换 2.3 MATLAB 的应用 ........................................................ 14 2.3.1MATLAB 主要功能 ................................................. 23 2.4 基本概念 ............................................................... 2.4.1 .............................................错误!未定义书签。 2.4.2 ................................................................. 2.4.2 ................................................................. 2.4.4 ................................................................. 第三章 FFT 的 MATLAB 设计与实现 ............................ 错误!未定义书签。 3.1 ................................................... 错误!未定义书签。 3.2. .................................................. 错误!未定义书签。 3.3 ................................................... 错误!未定义书签。 3.4 ........................................................................ 3.5 ........................................................................ 第四章 FFT 的分析 ............................................................. 27 4.1 ................................................... 错误!未定义书签。 4.2 ................................................... 错误!未定义书签。 4.3 ................................................... 错误!未定义书签。 第五章 总结与展望 ........................................................... 28 参考文献 ..................................................................... 28 致谢 ......................................................................... 29 3
第一章绪论 1.1. 引言 1965 年,库利(J.W.Cooley)和图基(J.W.Tukey)在《计算数学》杂 志上发表了“机器计算傅立叶级数的一种算法”的文章,这是一篇关于计算 DFT 的一种快速有效的计算方法的文章。它的思路建立在对 DFT 运算内在规律的认识 之上。这篇文章的发表使 DFT 的计算量大大减少,并导致了许多计算方法的发现。 这些算法统称为快速傅立叶变换(Fast Fourier Transform),简称 FFT,1984 年, 法国的杜哈梅尔(P.Dohamel)和霍尔曼(H.Hollmann)提出的分裂基快速算法, 使运算效率进一步提高。FFT 即为快速傅氏变换,是离散傅氏变换的快速算法, 它是根据离散傅氏变换的奇、偶、虚、实等特性,对离散傅立叶变换的算法进行 改进获得的。它对傅氏变换的理论并没有新的发现,但是对于在计算机系统或者 说数字系统中应用离散傅立叶变换,可以说是进了一大步。 随着科学的进步,FFT 算法的重要意义已经远远超过傅里叶分析本身的应 用。FFT 算法之所以快速,其根本原因在于原始变化矩阵的多余行,此特性也适 用于傅里叶变换外的其他一些正交变换,例如,快速沃尔什变换、数论变换等等。 在 FFT 的影响下,人们对于广义的快速正交变换进行了深入研究,使各种快速变 换在数字信号处理中占据了重要地位。因此说 FFT 对数字信号处理技术的发展起 了重大推动作用。[2] 4
1.2 FFT 算法的研究与发展 近十多年来数字信号处理技术同数字计算机、大规模集成电路等先进技术一 样,有了突飞猛进的发展,日新月异,已经形成了一门具有强大生命力的技术科 学。由于它本身具有一系列的优点,所以能有效地促进各工程技术领域的技术改 造和学科发展,应用领域也更加广泛、深入,越来越受到人们的重视。 在数字信号处理中,离散傅里叶变换(Discrete Fourier Transform, DFT)是常用 的变换方法,它在各种数字信号处理系统中扮演着重要的角色。快速傅里叶变换 〔Fast Fourier Transfonn, FFT〕并不是与离散傅里叶变换不同的另一种变换,而 是为了减少 DFT 计算次数的一种快速有效的算法。 傅里叶变换已有一百多年的历史了,我们知道频域分析常常比时域分析更优 越,不仅简单,且易于分析复杂信号。但用较精确的数字方法,即 DFT 进行谱 分析,在 FFT 出现以前是不切实际的。这是因为 DFT 计算量太大。直到 1965 年 出现了 FFT。 应该指出,当时电子数字计算机的条件也促成了这个算法的提出。1967 年至 1968 年间 FFT 的数字硬件就制成了。至此 DFT 的运算大为简化,运算时间一 般可降低 1-2 个数量级。因而各个科学技术领域广泛地采用了 FFT 技术,它大 大推动了近 30 年来信号处理技术的发展,成为数字信号处理应用领域强有力的 工具,广泛应用于雷达、声纳、通信、地质劫探、图像处理、生物医学等领域中。 Sande 提出了按照频率抽取的 FFT 算法,Bergland 提出了采用高基数结构的算 法,Winograd 博士提出的,可以称为 WFTA 算法,Rader 和 Brenner 提出的余割 因子算法,王中德提出的对称分解法,Vetlerli 和 Nussbaumer 提出的 DFT DCT 算法,其中最具代表性的是法国的 Duhamel 和 Hollman 提出的分裂基算法。各 NW 的周期性和对称性,通过将一个大点数 N 的 种 DFT 的快速算法,都利用了 DFT 分解为若干小点数的 DFT 的组合,来减少运算量 nk 5
第二章 基本理论 2.1 FFT 算法的基本概念 离散傅立叶变换(DFT)是信号分析与处理中的一种重要的变换。DFT 的计 算,需要作 N2 次复数乘法运算和 N(N-1)次复数加法运算,当 N 较大时,计 算量太大,为了快速计算 DFT,近半个世纪以来,人们对离散傅立叶变换的计算 进行了大量的研究,提出了很多有效的快速计算 DFT 的方法。这些算法,称之为 快速傅立叶变换(Fast Fourier Transform,FFT)。快速博里叶变换并不是与 DF T 不同的另外一种变换,而是为减少 DFT 计算次数的一种快速有效的算法。其突 出的优点在于能快速高效地和比较精确地完成 DFT 的计算。 2.1.1离散傅里叶变换(DFT) 随着科学技术的进步,人们越来越正视频率分析技术的发展与应用。以前要 进行一次频率分析,其计算的工作量大的惊人。现在,电子计算机的飞速发展使 得计算的速度加快。但是,电子计算机不可能对连续的信号进行处理,它只能处 理有限的离散数据。为了便于利用电子计算机进行傅立叶级数与傅立叶积分交换 的运算,需要对连续信号进行采样,从而得到一系列离散数据。这种对离散量的 傅立叶变换,称为离散傅立叶变换,记作 DFT。 DFT 的定义: 设 x(n) 是一个长度为 N 的有限长序列,定义 x(n) 的 N 点离散傅立叶变换为   ( ) X k DFT x n [ ( )] 其中 k=0,1,…,N-1 X (k) 的傅立叶反变换为 N 1   n  0  j 2  N nk ( ) x n e  N 1   n  0 ( ) x n W nk N (2.2.1) ( ) x n  IDFT X k ( )] [  1 N 其中 n= 0,1,…,N-1 N 1   k  0 ( ) X k e j 2  N nk  N 1   k  0 ( ) x k W nk  N (2.2.2) 在(2-2-1)式和(2-2-2)式中, x(n) 和 X(k)均可以是复数。因为在(2-2-1)式和 (2-2-2)式的右边仅在 WN 指数上差一个符号,并相差一个比例因子 1/N,所以 有关(2-2-1)式计算步骤的讨论稍加修改可以直接用于(2-2-2)式。 DFT 隐含周期性,在 DFT 变换对中,x(n) 和 X(k)均为有限长序列,设 6 nk NW 
2j  Ne nk = nk NW  ,由 的周期性,使得 x(n) 和 X(k)隐含周期性,且周期为 N。 2.1.2 快速傅里叶变换(FFT) 从前一节的讨论中知道,DFT 的计算,需要作 N2 次复数乘法运算和 N(N -1)次复数加法运算,运算量大。为了快速计算 DFT,近半个世纪以来,人们 对离散傅立叶变换的计算进行了大量的研究,提出了很多有效的快速计算 DFT 的方法。这些算法,称之为快速傅立叶变换(Fast Fourier Transform,FFT)。快速 博里叶变换并不是与 DF T 不同的另外一种变换,而是为减少 DFT 计算次数的 一种快速有效的算法。其突出的优点在于能快速高效地和比较精确地完成 DFT 的计算。 2.2.FFT 算法的分类 DFT 分解法基本上分为两类:一类是将时间序列 x(n) (n 为时间标号)进行 逐次分解,由此得到的 FFT 算法称为按时间抽取(Decimation-in-time)算法,另 一类是 将 傅 立 叶 变 换 序 列 X(k) (k 为 频率标号)进行分 解 ,叫做按频 率抽取(Decimation-in-frequency)算法。对这两种算法,库利—图基和桑德- 图基进行了理论的推导,故又称为库利—图基〔Cooley-Tukey〕算法和桑德—图 基(Sande-Tukey)算法。对每一算法,按基本的蝶形运算的构成又可分为基 2、 基 4、基 8 以及任意因子等的 FFT 算法。不同基的 FFT 算法所需的计算量略有 差异。之所以说略有差异是指并无数量级的差别,甚至无成倍的差别。只是某种 基的算法比另一种省几分之几而已。表 2.2.1 列出了 N=4096 时各种基的 FFT 算法所需运算量的比较。 算法 基 2 基 4 基 8 基 16 实数乘法次数 实数加法次数 81 924 57 348 49 156 48 132 139 266 126 978 126 978 125 422 (表 2.2.1 算法运算量的比较) 表 2.2.1 给出了 N 是 2 的任意次乘方时所需的运算量。这里假定每一种算法 都以最有效的方法来完成尽可能多的计算。 7
分享到:
收藏