1、1学号：毕 业 设 计题 目 ： FFT 算 法 的 研 究 与 Matlab 编 程 实现作 者 届 别系 别 专 业 电子信息工程指导老师 职 称完成时间 1摘 要快速傅里叶变 (|Fas Fourier Tranformation，FFT)是将一个大点数 N的DFT分解为若干小点的 D F T的组合。将用运算工作量明显降低， 从而大大提高 离散傅里叶变换(D F T) 的计算速度。因各个科学技术领域广泛的使用了FFT 技术它大大推动了信号处理技术的进步，现已成为数字信号处理强有力的工具，本论文将比较全面的叙述各种快速傅里叶变换算法原理、特点，并完成了基于 MATLAB的实现。关键词：离散
2、傅立叶变换；快速傅立叶变换；蝶形单元；MATLAB2目 录第一章 绪 论 .41.1 FFT算法的意义 .41.2 研究目标、内容 .4第二章 基本理论 .62.1 FFT算法基本概念 .62.1.1离散傅里叶变换（DFT） .62.1.2 快速傅里叶变换（FFT） 2.2 FFT算法分类 .72.2.1基 2、DIT-FFT（按时间抽取） 2.2.2基 2、DIF-FFT（按频率抽取） 2.23 基 4、DIF-FFT(按频率抽取) 2.24 分裂基 FFT算法 2.2.5 N为组合数的 FFT混合基算法 2.2.6 Chirp-z变换 2.3 MATLAB的应用 .132.3.1MATLA
3、B主要功能 .212.4基本概念 .2.4.1.302.4.2.2.4.2.2.4.4.第三章 FFT 的 MATLAB设计与实现 .223.1 .223.2. .223.3 .253.4 .3.5 .第四章 FFT 的分析 .314.1 .314.2 .314.3 .31第五章 总结与展望 .33参考文献 .34致谢 .353第一章绪论1.1 引言1965年，库利（J.W.Cooley）和图基（J.W.Tukey）在计算数学杂志上发表了“机器计算傅立叶级数的一种算法”的文章，这是一篇关于计算DFT的一种快速有效的计算方法的文章。它的思路建立在对 DFT运算内在规律的认识之上。这篇文章的发表使
4、 DFT的计算量大大减少，并导致了许多计算方法的发现。这些算法统称为快速傅立叶变换（Fast Fourier Transform） ，简称FFT，1984 年，法国的杜哈梅尔（P.Dohamel）和霍尔曼（H.Hollmann）提出的分裂基快速算法，使运算效率进一步提高。FFT 即为快速傅氏变换，是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。随着科学的进步，FFT 算法的重要意义已经远远超过傅里叶分析本身的应用。FFT 算法
5、之所以快速，其根本原因在于原始变化矩阵的多余行，此特性也适用于傅里叶变换外的其他一些正交变换，例如，快速沃尔什变换、数论变换等等。在 FFT的影响下，人们对于广义的快速正交变换进行了深入研究，使各种快速变换在数字信号处理中占据了重要地位。因此说 FFT对数字信号处理技术的发展起了重大推动作用。241.2 FFT 算法的研究与发展近十多年来数字信号处理技术同数字计算机、大规模集成电路等先进技术一样，有了突飞猛进的发展，日新月异，已经形成了一门具有强大生命力的技术科学。由于它本身具有一系列的优点，所以能有效地促进各工程技术领域的技术改造和学科发展，应用领域也更加广泛、深入，越来越受到人们的重视。在
6、数字信号处理中，离散傅里叶变换(Discrete Fourier Transform, DFT)是常用的变换方法，它在各种数字信号处理系统中扮演着重要的角色。快速傅里叶变换Fast Fourier Transfonn, FFT并不是与离散傅里叶变换不同的另一种变换，而是为了减少 DFT 计算次数的一种快速有效的算法。傅里叶变换已有一百多年的历史了，我们知道频域分析常常比时域分析更优越，不仅简单，且易于分析复杂信号。但用较精确的数字方法，即 DFT 进行谱分析，在 FFT 出现以前是不切实际的。这是因为 DFT 计算量太大。直到 1965 年出现了 FFT。应该指出，当时电子数字计算机的条件也促
7、成了这个算法的提出。1967 年至 1968 年间 FFT 的数字硬件就制成了。至此 DFT 的运算大为简化，运算时间一般可降低 1-2 个数量级。因而各个科学技术领域广泛地采用了 FFT 技术，它大大推动了近 30 年来信号处理技术的发展，成为数字信号处理应用领域强有力的工具，广泛应用于雷达、声纳、通信、地质劫探、图像处理、生物医学等领域中。Sande 提出了按照频率抽取的 FFT 算法，Bergland 提出了采用高基数结构的算法,Winograd 博士提出的，可以称为 WFTA 算法，Rader 和 Brenner 提出的余割因子算法，王中德提出的对称分解法，Vetlerli 和 Nus
8、sbaumer 提出的 DFT DCT 算法，其中最具代表性的是法国的 Duhamel 和 Hollman 提出的分裂基算法。各种 DFT 的快速算法，都利用了 的周期性和对称性，通过将一个大nkNW点数 N 的 DFT 分解为若干小点数的 DFT 的组合,来减少运算量5第二章 基本理论2.1 FFT 算法的基本概念离散傅立叶变换（DFT）是信号分析与处理中的一种重要的变换。DFT 的计算，需要作 N2 次复数乘法运算和 N（N1）次复数加法运算，当 N较大时，计算量太大，为了快速计算 DFT，近半个世纪以来，人们对离散傅立叶变换的计算进行了大量的研究，提出了很多有效的快速计算 DFT 的方法
9、。这些算法，称之为快速傅立叶变换（Fast Fourier Transform，FFT） 。快速博里叶变换并不是与DF T 不同的另外一种变换，而是为减少 DFT 计算次数的一种快速有效的算法。其突出的优点在于能快速高效地和比较精确地完成 DFT 的计算。2.1.1离散傅里叶变换（DFT）随着科学技术的进步，人们越来越正视频率分析技术的发展与应用。以前要进行一次频率分析，其计算的工作量大的惊人。现在，电子计算机的飞速发展使得计算的速度加快。但是，电子计算机不可能对连续的信号进行处理，它只能处理有限的离散数据。为了便于利用电子计算机进行傅立叶级数与傅立叶积分交换的运算，需要对连续信号进行采样，从
10、而得到一系列离散数据。这种对离散量的傅立叶变换，称为离散傅立叶变换，记作 DFT。DFT 的定义：设 x(n) 是一个长度为 N 的有限长序列，定义 x(n) 的 N 点离散傅立叶变换为（22.1）21100()()()()NjnknknXkDFTxexW其中 k=0，1, ，N1X (k) 的傅立叶反变换为（22.2）21100()()()()NNjnknkkxnITXex其中 n= 0,1,N-1在(2-2-1)式和(2-2-2)式中， x(n) 和 X(k)均可以是复数。因为在 (2-2-1)式和(2-2-2)式的右边仅在 WN 指数上差一个符号，并相差一个比例因子 1N ，所以6有关(
11、2-2-1)式计算步骤的讨论稍加修改可以直接用于(2-2-2) 式。DFT 隐含周期性，在 DFT 变换对中，x(n) 和 X(k)均为有限长序列，设nkNW= ，由 的周期性，使得 x(n) 和 X(k)隐含周期性，且周期为 N。2jenkN2.1.2 快速傅里叶变换（FFT）从前一节的讨论中知道，DFT 的计算，需要作 N2 次复数乘法运算和 N（N1）次复数加法运算，运算量大。为了快速计算 DFT，近半个世纪以来，人们对离散傅立叶变换的计算进行了大量的研究，提出了很多有效的快速计算 DFT 的方法。这些算法，称之为快速傅立叶变换（ Fast Fourier Transform，FFT ）
12、 。快速博里叶变换并不是与 DF T 不同的另外一种变换，而是为减少 DFT 计算次数的一种快速有效的算法。其突出的优点在于能快速高效地和比较精确地完成 DFT 的计算。2.2.FFT 算法的分类DFT 分解法基本上分为两类：一类是将时间序列 x(n) (n 为时间标号)进行逐次分解，由此得到的 FFT 算法称为按时间抽取(Decimation-in-time)算法，另一类是 将 傅 立 叶 变 换 序 列 X(k) (k 为 频率标号)进行分 解 ，叫做按频率抽取（Decimation-in-frequency）算法。对这两种算法，库利图基和桑德图基进行了理论的推导，故又称为库利图基Cool
13、eyTukey算法和桑德图基(SandeTukey)算法。对每一算法，按基本的蝶形运算的构成又可分为基 2、基 4、基 8 以及任意因子等的 FFT 算法。不同基的 FFT 算法所需的计算量略有差异。之所以说略有差异是指并无数量级的差别，甚至无成倍的差别。只是某种基的算法比另一种省几分之几而已。表 2.2.1 列出了 N=4096 时各种基的 FFT 算法所需运算量的比较。算法 实数乘法次数 实数加法次数基 2 81 924 139 266 基 4 57 348 126 978基 8 49 156 126 978基 16 48 132 125 422（表 2.2.1 算法运算量的比较）7表 2
14、.2.1 给出了 N 是 2 的任意次乘方时所需的运算量。这里假定每一种算法都以最有效的方法来完成尽可能多的计算。从表格可以看出，一般地说，基数越高，总计算量愈少。但是我们不能光从运算量的角度来简单地判断说基数越高的算法越好。判断一个算法不仅要从计算量而且还应从算法的复杂性方面来加以考察。一般来说，基数愈高，算法本身也愈复杂。所以，选择算法要依据具体情况进行考虑。如考虑用何种语言设计程序，在什么机器上运行程序，或者采用何种逻辑器件和系统结构来构成 FFT硬件等等。2.2.1 基 2、DIT-FFT（按时间抽取）-10/21/21(21)/21/21/2/2()() ()()()()Nknnkk
15、nNNnNkrkrrnNkr krNr nXkxWxxWxW偶 数 奇 数0000令 ， 则有/211/2()()NkrNrxX0/12/()()krr X012(/)()kNXkW蝶形运算单元如下所示：82.2.2 基 2、DIF-FFT（按频率抽取） -10/21/2/211(/2)/21/2/21 /2()() ()()(/)()(/)()()()()NknnNkknnNk knNNnnkknNnNrnnXkxWxxWxXrx0000/21 /2/)nrNnW0则有 12()(/2)nNxx蝶形运算单元如下所示：9由前面的分析可知，DIT（按时间抽取）算法与 DIF（按频率抽取）算法没有
16、本质上的区别，只是复数加减法与旋转因子乘法的次序有区别，两种方法的运算量是一样的。在基 2 算法中，每个蝶形运算单元都包括 1 次复数乘法、2 次复数加法。N（N= ）点序列的运算流图应有 M 级蝶形，每一级都由 N/2 个蝶形运算组成，M所以 N 点序列的基 2FFT 算法，总的运算量为 次复数乘法， 次logN2logN复数加法。直接 DFT 运算量为 次复数乘法、 次复数加法。可见，2()FFT 算法大大减少了运算量，当 N 越大时，FFT 算法的优越性越明显。2.23 基 4、DIF-FFT(按频率抽取)10/4/213/411/4/23/4/1 /(4) (/2)00 0(3/4)()( )() )( (/)NknnNNNkknknknnNk k kNNNn nknXkxWxxWxx /4/1 / /23/40/4/4/1 /0(/)(/)()/4)3(/2)()(42)NkNkNkNnn rnN rNnxxxWXr nnxjxjxr /4 2/4/1 3/0)/4)/3(/2)()nrN rNn nNnXxjxjxW 令： 01 22 33()(/4)(/)(/4) /2/()()()()nNnxnnjxxNjxnxj j则有
