学号:
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