离散傅里叶变换及其快速算法

《离散傅里叶变换及其快速算法》由会员分享，可在线阅读，更多相关《离散傅里叶变换及其快速算法（15页珍藏版）》请在装配图网上搜索。

1、精选优质文档-倾情为你奉上离散傅里叶变换及其快速算法摘要离散傅里叶变换(DFT)在数字信号处理等许多领域中起着重要作用。本文由离散傅里叶级数导出离散傅里叶变换定义及其计算方法。但DFT计算量太大，实际应用中有困难。为了减少运算次数，提高算法效率，常用快速傅里叶变换，文中简要介绍了几种方法。关键词：离散傅里叶变换；快速傅立叶变换；改进方法专心-专注-专业The discrete Fourier transform and fast Fourier TransformABSTRACTDiscrete Fourier Transform plays an important role in many

2、 fields of the digital signal processing. In this article, we deduced the definition and computing methods of Discrete Fourier Transform from Discrete Fourier Series. But there are many difficulties in the practical application, owing to the large amount of computation .To improve the efficiency and

3、 reduce the computing complexity, Fast Fourier Transform are commonly used. Few methods of Fast Fourier Transform are introduced in the text.Key Words: Discrete Fourier Transform; Fast Fourier Transform; improvement approach目录1引言连续时间傅里叶变换是一种积分变换，很难在实际中得到应用。离散傅里叶变换是为了适应利用计算机分析傅里叶变换而规定的一种专门运算，他是对连续时间信

4、号频谱分析的逼近。由于大多数文献中很少详细地探讨连续傅里叶变换与离散傅里叶变换之间的关系，因此人们对离散傅里叶变换存在着模糊的理解。1程佩青数字信号处理教程M北京：清华大学出版社，2007:110155有限长序列在数字信号处理中非常重要，当然可以用z变换和傅里叶变换来研究它，但可以导出反映它的有限长特点的一种有用工具是离散傅里叶变换。因此，DFT的计算在数字信号处理中非常有用。例如，在FIR滤波器设计中会遇到从h(n)求H(k)或由H(k)求h(n)，这就要计算DFT。再由，信号的频谱分析对通信、图像传输、雷达、声呐等都是很重要的。此外，在系统的分析、设计和实现中都会用到DFT的计算。2孙大飞

5、,刘浩,刘彬,陈务深离散傅里叶变换的进一步探析J电子技术2006，11：1 但在相当长的时间里,由于DFT的计算量太大，即使采用计算机也很难对问题实时处理，所以没有得到真正的应用。直到1965年J.W.Cooley和J.W.Tukey巧妙地利用因子的周期性和对称性，构造了 DFT 的快速算法，即快速离散傅里叶变换(FFT),在计算数学杂志上发表了著名的“机器计算傅里叶级数的一种算法”的文章，情况才发生改变。经过改进对算法的改进，发展和完善了一套高速有效的运算方法，使DFT的计算大大简化，运算时间可缩短一、二个数量级，从而使DFT的运算在实际当中真正得到了广泛的应用。在以后的几十年中，FFT 算

6、法有了进一步的发展，目前较常用的是基-2算法和分裂基算法。3GUELACHVILI G傅里叶变换光谱M北京:北京大学出版社，1990. 55-934吕乃光，陈家壁. 傅里叶光学M北京：科学出版社， 1985. 144-1895张光昭傅里叶变换光谱学M广州：中山大学出版社，1988. 221-2512离散傅里叶变换(DFT)的基本原理2.1引出离散傅里叶变换的必要性有限长序列的离散傅里叶变换和周期序列的离散傅里叶变换（DFS）本质上是一样的，为了更好地理解DFT，需要讨论DFS。对离散时间信号的频谱分析，可以用离散时间傅里叶变换，即DTFT。DTFT使我们能够在数字域频率分析信号的频谱和离散系统

7、的频率响应特性，但对于DTFT仍然存在两个实际问题。数字域频率是一个连续变量，不利于用计算机进行计算。为了便于用数字的方法进行离散时间信号与系统的频域分析和处理，仅仅在时间域进行离散化还不够，还必须在频谱进行离散化。数字化方法处理的序列只能为有限长的，所以，要专门讨论有限长序列的频谱分析问题。2.2离散傅里叶变换的定义根据以上要求，引出了有限长序列的离散傅里叶变换的概念。首先应指出，离散傅里叶变换使针对有限长序列或周期序列才存在的；其次，它相当于把序列的连续傅里叶变换加以离散化（抽样），频域的离散化造成时间函数也呈周期，故级数应限制在一个周期之内。有限长序列的离散傅里叶变换，简称为离散傅里叶变

8、换，即DFT(Discrete Fourier Transform)。设是周期为N的一个周期序列，在范围内,令 它的离散傅里叶级数对如下： 把长度为N的有限长序列看成周期为N的周期序列的一个周期，利用DFS计算周期序列的一个周期，也就是计算了有限长序列。设有限长序列，点数为N，即只在有值，其他n时，。把它看成周期为N的周期序列的一个周期，而把看成的以N为周期的周期延拓。令，则它们的关系表示为 同理，对频域的周期序列可以看成是对有限长序列的周期延拓，而有限长序列看成周期序列的主值序列，即 由(2.2.5)与(2.2.6)以上两式可以看出，求和是只限定在n=0到N-1及k=0到N-1的主值区间进行

9、的，故完全适用于主值序列与，即有限长序列的离散傅里叶变换定义 正变换: 反变换: 两式构成离散傅里叶变换对。注意不要把离散傅里叶变换DFT和离散时间傅里叶变换DTFT混淆了。DTFT是对任意序列的傅里叶变换，它的频谱是一个连续函数，而DFT是对有限长序列的离散傅里叶变换，DFT的特点是无论在时域还是在频谱都是离散的，而且都是有限长的。2.3离散傅里叶变换的性质线性 设两个有限长序列为和，则 对称性 设是长度为n的实序列，且，则 循环移位特性 有限长序列为，若 ，则 循环卷积特性 若，则 3快速傅里叶变换3.1直接计算DFT的特点及减少运算量的基本途径长度为N的有限长序列的DFT为 考虑为复数序

10、列的一般情况，对某一个k值，直接按式计算值需要N次复数乘法、(N-1)次复数加法。 N点DFT的复乘次数等于N2。显然，把N点DFT分解为几个较短的DFT，可使乘法次数大大减少。另外，旋转因子WmN具有明显的周期性和对称性。其周期性表现为 其对称性表现为 利用这些特性，是FFT运算中有些项可以合并；利用的对称性、周期性，可以将长序列的FFT分解为短序列的DFT。FFT算法基本上分为两大类：按时间抽选法 (Decimation In Time ,简称DIT)和频域抽取法(Decimation In Frequency,简称DIF)。下面只介绍DIT算法。3.2按时间抽选的（DIT）的基-2FFT

11、算法 设序列的长度为N，且满足。如果不满足这个条件，可以人为地加若干零值点，使之达到要求。这种N为2的整数幂的FFT也称为基-2FFT。按n的奇偶把分解为两个N/2点的子序列 则的DFT为 由于,上式可表示成 其中和分别为和的N/2点DFT，即 由于和均以N/2为周期，且，所以X(k)又可表示为 (3.2.5)式和(3.2.6)式的运算可用图3-1的蝶形运算符号表示。图3-1 蝶形算法运算符号采用这种表示方法，可将上述分解过程表示于图3-2中。此图表示N=8的情况，其中输出值 到由式(3.2.5)给出，而输出值到是由式(3.2.6)给出的。图3-2 N点DFT的一次时域抽取分解图(N=8)与第

12、一次分解相同，将x1(r)按奇偶分解成两个N/4长的子序列x03(l)和x4(l)，即 那么，X1(k)又可表示为 式中 同理，由和的周期性和的对称性，最后得到: 用同样的方法可计算出 其中 将系数统一为，则一个N=8的点DFT就可分解为四个 的点DFT，这样可以得图3-3所示的流程图。图3-3 N点DFT的第二次时域抽取分解图(N=8)3.3DITFFT算法与直接计算DFT运算量的比较每一级运算都需要N/2次复数乘和N次复数加(每个蝶形需要两次复数加法)。所以，L级运算总共需要的复数乘次数为 复数加次数为 由于计算机上乘法运算所需时间比加法时间多得多，故以乘法为例，说明FFT算法和DFT算法

13、运算量的比较。直接计算DFT与FFT算法的运算量之比为 图3-4是直接计算DFT与FFT算法所需运算量分别与点数N的关系曲线，可以更直观地看出FFT算法的优越性，尤其是当点数N越大时，FFT的优点更突出。图3-4 直接计算DFT与FFT算法所需乘法次数的比较3.4提高快速傅里叶变换运算效率的方法分裂基FFT算法从基-2按时间和频率抽选的推导过程中看出。每级抽选时。每组的偶序号部分都不乘旋转因子，旋转因子都出现在奇序号上，考虑到基-4比基-2FFT算法更有效，因此对偶序号使用基-2FFT算法，对奇序号使用基-4算法。分裂基FFT算法是针对 的算法中具有最少乘法次数，且具有基-2算法同样好的同址运

14、算结构，因此被认为是最好的FFT算法。改进型位序倒置算法逐次分解会带来位序倒置问题，为进行同址运算，在蝶形计算之前或之后，重新编排标号。它修正了经典的位序倒置算法中外循环变量的初值和终值，从而减少了循环次数，采用基于裂基分解理论的算法，将N点实离散傅里叶变换逐渐分解为一系列长度较短的复离散傅里叶变换，调用经典的FFT子程序便得到原始实序列的离散傅里叶变换，计算量可以显著减少。6曹钧提高快速傅里叶变换算法效率的方法J微电子学与计算机，1994，5：13基于线性插值原理的改进FFT和基于抛物线插值原理的改进FFT采用线性插值原理和抛物线插值原理对模拟信号的采样数据进行处理,然后采用分部积分法导出了

15、两种高精度频谱分析的基本计算公式, 通过实例计算证明,这两种方法可降低对采样频率的要求,因而减少了大量的采样数据处理时间,明显提高了计算速度。7李庚银，陈志业，宁宇快速傅里叶变换的两种改进算法J电力系统自动化1997，21：12最佳递归傅里叶变换算法这里的递归算法采用的是戈泽尔算法，其优点是:计算一个频率分量x(引仅需要一个复数系数W万和N次递归运算.如果不要求计算全部N个频率分量，而仅要求计算少数(如个)频率分量，在 时，戈译尔算法比FFT算法需用的乘法次数还要少。但是戈泽尔算法仍需用(N一l)个复数系数来计算全部N个频率分量.质数长度的离散傅里叶变换的递归算法有一个很重要的性质:只要用一个

16、系数即可计算全部N个频率分量。这就使算法的硬件实现简化。8张彦仲最佳递归傅里叶变换算法J信号处理，1987，3：24总结离散傅里叶变换的重要性在于,他使得人们在进行连续时间信号的谱分析时不需积分运算而只需要使用简单的加法和乘法运算,这样便于在计算机上进行信号的频谱分析。本文通过对离散傅里叶变换的原理介绍，并介绍了几种提高快速傅里叶变换效率的方法,目的是加深了人们对离散傅里叶变换的理解,从而对其有更深入的理解，并加强对其运用。DFT提供了使用计算机或DSP芯片来分析信号与系统的一种方法，尤其是DFT的快速算法FFT，在许多科学技术中得到了广泛的应用，并推动了数字信号处理技术及相关学科的迅速发展。参考文献