毕业论文-快速傅里叶变换算法及其在信号处理中的应用(2)

武汉工程大学毕业设计(论文)说明书

由于DFT的计算量太大，即使运用计算机也很难对问题进行实时的有效处理，所以DFT并没有得到真正的应用。直到1965年库利（J.W.Cooly）和图基（J.W.Tukey）首次发现DFT的一种快速算法，局面才发生根本性的变化。继库利和图基算法出来之后，桑德（G.Sander）等快速算法也相继出现，又经过其他学者一步步改进，很快就出现了通用型的快速傅里叶变换，简称FFT。快速傅里叶变换（Fast Fourier Transform，FFT）并非与离散傅里叶变换完全不同的另一种变换，而是为了减少DFT计算次数而诞生的一种快速、有效的算法。应当指出的是，也是因为当时电子数字计算机的“落后”条件也促成了这个算法的提出。它使得DFT的运算量大大的缩小简化，它推动了近30年来信号处理技术止步不前的前进发展，成为了数字信号处理应用领域里强有力的工具，为DFT乃至数字信号处理技术的实际应用创造了良好的条件，从而使DFT在实际使用中得以广泛的应用[2]。

数字信号处理器（DSP），是一种可编程的高性能处理器。近年来发展尤为迅速，它不仅应用于数字信号处理方面，而且在图像处理、语音处理、通信等领域得到广泛的应用。之前通用的微处理器在运算速度上已经很难适应信号实时处理的高要求。DSP处理器中集成了高速的乘法硬件，能快速、准确地进行大量数据的乘法以及加法的运算。数字信号处理区别于普通的科学计算与分析，它强调运算的实时性。除了需要普通微处理器所强调的高速运算和控制能力之外，鉴于实时数字信号处理的特点，在处理器结构、指令系统、指令流程上做了很大程度上的改进。

1. 2 课题研究的意义

如上所述，基于对DSP的快速傅里叶变换算法的研究，从而使FFT算法能够有效地在DSP芯片上实现。DSP芯片的出现，使FFT的实现更加方便。多数的DSP芯片都能够在一个指令周期内完成一次乘法和加法，并且提供了专门的FFT指令，完成一次指令的周期只需10ns，使得FFT算法在DSP芯片上实现的速度更加快速。快速傅里叶变换为频谱分析、卷积、相关数字滤波器设计与实现与功率谱计算、传递函数建模、图像处理等，提供了快速有效的运算方法。FFT技术应用DSP芯片，从而可以提供使调制、解调、压缩、解压缩的数据传输更为高效的信号处理解决方案，因而广泛应用于雷达、图像处理、通信、生物医学和声纳领域。

2

武汉工程大学毕业设计(论文)说明书

2.快速傅里叶变换原理及性质

数字信号中的傅里叶变换,通常是采用离散型傅里叶变换(DFT)。DFT 存在的

缺点就是计算量太大,不易进行实时处理。比如，计算一个N 点的DFT ,一般需要N次复数乘法和N(N-1)次复数加法运算.因此,当N较大或要求对信号进行实时处理时,往往很难实现达到所需的运算速度。1965年,J.W.Cooly和J.W.Tukey发现了DFT的一种快速算法,经过后来学者的进一步改进, 很快便形成了一套高效的运算方法,即现在通用的快速傅里叶变换, 简称FFT( The Fast Fourier

nkWNTransform)。快速傅里叶变换的实质是利用式(3-1)中的权函数的对称性和

2周期性,把N点DFT进行一系列分解和组合,使整个DFT的计算过程变成一系列叠代运算过程,使DFT的运算量大大简化,为DFT及数字信号的实时处理和应用创造了非常良好的条件[3]。 2. 1 快速傅里叶变换原理

快速傅里叶变换原理：

1. 将长序列DFT分解为短序列的DFT

2. 利用旋转因子的对称性、周期性、可约性。将时域序列逐次分解为一组子序列，依据旋转因子的特性，由子序列的DFT来实现整个序列的DFT[4]。

其中：快速傅里叶变换分为两种，分为基2时间抽取算法和基2频率抽取算法

基2-时间抽取(Decimation in time)FFT算法

?x[2r]x[k]???x[2r?1]N?1

其中:r=0,1,2? 2 （2-1）

基2-频率抽取(Decimation in frequency)FFT算法

?X[2m]X[m]???X[2m?1] （2-2）

3

武汉工程大学毕业设计(论文)说明书

2. 2 快速傅里叶变换的优越性

设xn为N项的复数序列，依据DFT变换，任一

x(m)的计算都需要有N次复

数乘法和（N?1）次复数加法，而且一次复数乘法等同于四次实数乘法和两次实数加法，同样的，一次复数加法等同于两次实数加法，即使我们把一次复数乘法和一次复数加法定义成一次“运算”（四次实数乘法和四次实数加法），那么求出N项复数序列的

x(m)2, 即N点DFT变换大约就需要N次运算。当N?1024点

甚至更多的时候，需要N2=1048576次运算。在FFT中，利用WN的对称性和周期性，把一个N项序列（设N?2k,k为正整数），分为两个N/2项的子序列，而且每个N/2点的DFT变换需要?N/2?次运算，再运用N次运算把两个N/2点的

2DFT 变换重新组合成一个N点的DFT变换。如此变换以后，总的运算次数就变成了N?2(N/2)2?N?N2/2。承接上面的例子，当N?1024时，总的运算次数就变成了525312次，这样看来，节省了大约50%的运算量。而如果我们将这种“一分为二”的思想不断进行下去，直到分成两两一组的DFT运算单元，那么N点的 DFT变换就只需要Nlog2次的运算，N在1024点时，运算量仅有10240次，是先前的直接算法的1%，点数越多，运算量的节约就越大，这就是 FFT的优越性.当然，FFT提高了运算速度,但是,也对参与运算的样本序列作出了限制,即要求样本数为2^N点.离散傅里叶变换DFT则无上述限制[5]。 2. 3 快速傅里叶变换的意义

傅立叶变换的物理意义：傅立叶变换是数字信号处理技术领域一项很重要的算法。要知道傅立叶变换算法的意义，首先要了解傅立叶变换原理的意义。傅立叶变换原理表明：任何连续测量的时序或信号，都能够表示成为不同频率的正弦波信号的无限叠加。而利用该原理而创立的傅立叶变换算法则利用直接能测量到的原始信号，并以累加方式来计算该信号中不同正弦波信号的频率、相位和振幅。

与傅立叶变换算法对应的是反傅立叶变换算法。该反变换从本质上说也就是一种累加处理，这样便可以将单独改变的正弦波信号转换成一个信号。因此，也可以说，傅立叶变换将原来难以处理的时域信号转换成了易于分析的频域信号（信号的频谱），我们可以利用一些专业工具对这些频域信号进行加工、处理。

4

n武汉工程大学毕业设计(论文)说明书

最后还可以利用傅立叶反变换将这些频域信号转换成原来的时域信号。

从现代数学的眼光来看，傅里叶变换其实就是一种特殊的积分变换。它能够将满足一定条件下的某个函数表示成为正弦基函数的线性组合或者积分形式。在不同的研究领域里，傅里叶变换具有多种形式各异的变体形式，如连续傅里叶变换和离散傅里叶变换。

在数学领域，尽管最初傅立叶分析是作为热过程的解析分析的工具，但是其思想方法仍然具有典型的还原论和分析主义的特征。\任意\的函数通过一定的分解，都能够表示为正弦函数的线性组合的形式，而正弦函数在物理上是被充分研究而相对简单的函数类：1. 傅立叶变换是线性算子,若赋予适当的范数,它还是酉算子;2. 傅立叶变换的逆变换容易求出,而且形式与正变换非常类似;3. 正弦基函数是微分运算的本征函数,从而使得线性微分方程的求解可以转化为常系数的代数方程的求解.在线性时不变杂的卷积运算为简单的乘积运算,从而提供了计算卷积的一种简单手段;4. 离散形式的傅立叶的物理系统内,频率是个不变的性质,从而系统对于复杂激励的响应可以通过组合其对不同频率正弦信号的响应来获取;5. 著名的卷积定理指出:傅立叶变换可以化复变换可以利用数字计算机快速的算出(其算法称为快速傅立叶变换算法(FFT))。

正是由于上述的良好性质,傅里叶变换在物理学、数论、组合数学、信号处理、概率、统计、密码学、声学、光学等领域都有着广泛的应用[6]。

5

武汉工程大学毕业设计(论文)说明书

3. 快速傅里叶变换的算法

3.1 快速傅里叶变换算法

快速傅里叶变换FFT 是离散傅里叶变换DFT 的一种快速算法，只有FFT 才能在现实中有实际应用的意义。

错误！未找到引用源。X(n)??x0(k)eN;n?0,1,2?N?1

K?0

(3-1)

由(3-1)式可知，对每一个n，计算X(ｎ)须作N次复数乘法及N-1次复数加法，要完成这组变换共需N2错误！未找到引用源。次乘法及N(N-1)次复数加法。但以下介绍的快速傅里叶变换的算法，可大大减少运算次数，提高工作效率。

当N?2r时，n和k可用二进制数表示：

r?1r?2n?2n?2nr?2?r?1

N?1?nk?n0?nr?1nr?2n0错误！未找到引用源。

(3-2)

r?1r?2k?2k?2kr?2?r?1

?k0?kr?1kr?2k0 （3-3）

又记 W?e X(nr?1nr?2???N,则（3-1）式可改写为

10?0n0)??k?1k1?0?1kr?1?0x0(kr?1kr?2k0)Wp （3-4）

式中：P?nk?(2r?1kr?1?2r?2kr?2? WP?W(2 W因为W2rr?1?k0)?(2r?1nr?1?2r?2nr?2??n0)

nr?1?2r?2nr?2??n0)2r?1kr?1W(2r?1nr?1?2r?2nr?2??n0)2r?2kr?2

K0(2r?1nr?1?2r?2nr?2??n0) (3-5)

???W2r?[eN]N?1所以（3-2）可改成Z

10?0X(nr?1nr?2n0)?k?11k1?0?1kr?1?0x0(kr?1kr?2k0)W(2r?1nr?1?2r?2nr?2??n0)2r?1kr?1W(2r?1nr?1?2r?2nr?2??n0)2r?2kr?2WK0(2r?1nr?1?2r?2nr?2??n0) （3-6）

x2(n0n1kr?3k0)??kr?2?0x0(n0kr?2k0)W(2n1?n0)2r?2kr?2 (3-7)

X(nr?1nr?2n0)?xr(n0n1nr?1)

6

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库毕业论文-快速傅里叶变换算法及其在信号处理中的应用(2)在线全文阅读。