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

1、精选优质文档-倾情为你奉上精选优质文档-倾情为你奉上专心-专注-专业专心-专注-专业精选优质文档-倾情为你奉上专心-专注-专业 MACROBUTTON MTEditEquationSection2 SEQ MTEqn r h * MERGEFORMAT SEQ MTSec r 2 h * MERGEFORMAT SEQ MTChap r 2 h * MERGEFORMAT 离散傅里叶变换及其快速算法摘要离散傅里叶变换(DFT)在数字信号处理等许多领域中起着重要作用。本文由离散傅里叶级数导出离散傅里叶变换定义及其计算方法。但DFT计算量太大，实际应用中有困难。为了减少运算次数，提高算法效率，常用

2、快速傅里叶变换，文中简要介绍了几种方法。关键词：离散傅里叶变换；快速傅立叶变换；改进方法The discrete Fourier transform and fast Fourier TransformABSTRACTDiscrete Fourier Transform plays an important role in many fields of the digital signal processing. In this article, we deduced the definition and computing methods of Discrete Fourier Transf

3、orm 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 reduce the computing complexity, Fast Fourier Transform are commonly used. Few methods of Fast Fourier Transform are introduced in t

4、he text.Key Words: Discrete Fourier Transform; Fast Fourier Transform; improvement approach目录 TOC o 1-3 h z u 1引言连续时间傅里叶变换是一种积分变换，很难在实际中得到应用。离散傅里叶变换是为了适应利用计算机分析傅里叶变换而规定的一种专门运算，他是对连续时间信号频谱分析的逼近。由于大多数文献中很少详细地探讨连续傅里叶变换与离散傅里叶变换之间的关系，因此人们对离散傅里叶变换存在着模糊的理解。11程佩青数字信号处理教程M北京：清华大学出版社，2007:110155有限长序列在数字信号处理中非

5、常重要，当然可以用z变换和傅里叶变换来研究它，但可以导出反映它的有限长特点的一种有用工具是离散傅里叶变换。因此，DFT的计算在数字信号处理中非常有用。例如，在FIR滤波器设计中会遇到从h(n)求H(k)或由H(k)求h(n)，这就要计算DFT。再由，信号的频谱分析对通信、图像传输、雷达、声呐等都是很重要的。此外，在系统的分析、设计和实现中都会用到DFT的计算。22孙大飞,刘浩,刘彬,陈务深离散傅里叶变换的进一步探析J电子技术2006，11：1 但在相当长的时间里,由于DFT的计算量太大，即使采用计算机也很难对问题实时处理，所以没有得到真正的应用。直到1965年J.W.Cooley和J.W.Tu

6、key巧妙地利用因子的周期性和对称性，构造了 DFT 的快速算法，即快速离散傅里叶变换(FFT),在计算数学杂志上发表了著名的“机器计算傅里叶级数的一种算法”的文章，情况才发生改变。经过改进对算法的改进，发展和完善了一套高速有效的运算方法，使DFT的计算大大简化，运算时间可缩短一、二个数量级，从而使DFT的运算在实际当中真正得到了广泛的应用。在以后的几十年中，FFT 算法有了进一步的发展，目前较常用的是基-2算法和分裂基算法。3GUELACHVILI G傅里叶变换光谱M北京3GUELACHVILI G傅里叶变换光谱M北京:北京大学出版社，1990. 55-934吕乃光，陈家壁. 傅里叶光学M北

7、京：科学出版社， 1985. 144-1895张光昭傅里叶变换光谱学M广州：中山大学出版社，1988. 221-2512离散傅里叶变换(DFT)的基本原理2.1引出离散傅里叶变换的必要性有限长序列的离散傅里叶变换和周期序列的离散傅里叶变换（DFS）本质上是一样的，为了更好地理解DFT，需要讨论DFS。对离散时间信号的频谱分析，可以用离散时间傅里叶变换，即DTFT。DTFT使我们能够在数字域频率分析信号的频谱和离散系统的频率响应特性，但对于DTFT仍然存在两个实际问题。数字域频率是一个连续变量，不利于用计算机进行计算。为了便于用数字的方法进行离散时间信号与系统的频域分析和处理，仅仅在时间域进行离

8、散化还不够，还必须在频谱进行离散化。数字化方法处理的序列只能为有限长的，所以，要专门讨论有限长序列的频谱分析问题。2.2离散傅里叶变换的定义根据以上要求，引出了有限长序列的离散傅里叶变换的概念。首先应指出，离散傅里叶变换使针对有限长序列或周期序列才存在的；其次，它相当于把序列的连续傅里叶变换加以离散化（抽样），频域的离散化造成时间函数也呈周期，故级数应限制在一个周期之内。有限长序列的离散傅里叶变换，简称为离散傅里叶变换，即DFT(Discrete Fourier Transform)。设是周期为N的一个周期序列，在范围内,令 它的离散傅里叶级数对如下： MACROBUTTON MTPlaceR

9、ef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 2. SEQ MTSec c * Arabic * MERGEFORMAT 2. SEQ MTEqn c * Arabic * MERGEFORMAT 1) MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 2. SEQ MTSec c * Arabic * MERGEFORMAT 2

10、. SEQ MTEqn c * Arabic * MERGEFORMAT 2)把长度为N的有限长序列看成周期为N的周期序列的一个周期，利用DFS计算周期序列的一个周期，也就是计算了有限长序列。设有限长序列，点数为N，即只在有值，其他n时，。把它看成周期为N的周期序列的一个周期，而把看成的以N为周期的周期延拓。令，则它们的关系表示为 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 2. SEQ MTSec c * Arabic * MERGEF

11、ORMAT 2. SEQ MTEqn c * Arabic * MERGEFORMAT 3) MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 2. SEQ MTSec c * Arabic * MERGEFORMAT 2. SEQ MTEqn c * Arabic * MERGEFORMAT 4)同理，对频域的周期序列可以看成是对有限长序列的周期延拓，而有限长序列看成周期序列的主值序列，即 MACROBUTTON MTPlaceRef * M

12、ERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 2. SEQ MTSec c * Arabic * MERGEFORMAT 2. SEQ MTEqn c * Arabic * MERGEFORMAT 5) MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 2. SEQ MTSec c * Arabic * MERGEFORMAT 2. SEQ

13、MTEqn c * Arabic * MERGEFORMAT 6)由(2.2.5)与(2.2.6)以上两式可以看出，求和是只限定在n=0到N-1及k=0到N-1的主值区间进行的，故完全适用于主值序列与，即有限长序列的离散傅里叶变换定义 正变换: MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 2. SEQ MTSec c * Arabic * MERGEFORMAT 2. SEQ MTEqn c * Arabic * MERGEFORMAT

14、7)反变换: MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 2. SEQ MTSec c * Arabic * MERGEFORMAT 2. SEQ MTEqn c * Arabic * MERGEFORMAT 8) MACROBUTTON MTEditEquationSection2 SEQ MTEqn r h * MERGEFORMAT SEQ MTSec h * MERGEFORMAT MACROBUTTON MTEditEquati

15、onSection2 SEQ MTEqn r h * MERGEFORMAT SEQ MTSec r 3 h * MERGEFORMAT SEQ MTChap h * MERGEFORMAT MACROBUTTON MTEditEquationSection2 SEQ MTEqn r h * MERGEFORMAT SEQ MTSec r 1 h * MERGEFORMAT SEQ MTChap h * MERGEFORMAT 两式构成离散傅里叶变换对。注意不要把离散傅里叶变换DFT和离散时间傅里叶变换DTFT混淆了。DTFT是对任意序列的傅里叶变换，它的频谱是一个连续函数，而DFT是对有限长

16、序列的离散傅里叶变换，DFT的特点是无论在时域还是在频谱都是离散的，而且都是有限长的。2.3离散傅里叶变换的性质 = 1 * GB2 线性 设两个有限长序列为和，则 MACROBUTTON MTEditEquationSection2 SEQ MTEqn r h * MERGEFORMAT SEQ MTSec r 1 h * MERGEFORMAT SEQ MTChap h * MERGEFORMAT MACROBUTTON MTEditEquationSection2 SEQ MTEqn r h * MERGEFORMAT SEQ MTSec r 3 h * MERGEFORMAT SEQ

17、MTChap r 2 h * MERGEFORMAT MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 2. SEQ MTSec c * Arabic * MERGEFORMAT 3. SEQ MTEqn c * Arabic * MERGEFORMAT 1) = 2 * GB2 对称性 设是长度为n的实序列，且，则 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT (

18、 SEQ MTChap c * Arabic * MERGEFORMAT 2. SEQ MTSec c * Arabic * MERGEFORMAT 3. SEQ MTEqn c * Arabic * MERGEFORMAT 2) = 3 * GB2 循环移位特性 有限长序列为，若 ，则 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 2. SEQ MTSec c * Arabic * MERGEFORMAT 3. SEQ MTEqn c *

19、 Arabic * MERGEFORMAT 3) = 4 * GB2 循环卷积特性 若，则 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 2. SEQ MTSec c * Arabic * MERGEFORMAT 3. SEQ MTEqn c * Arabic * MERGEFORMAT 4) MACROBUTTON MTEditEquationSection2 SEQ MTEqn r h * MERGEFORMAT SEQ MTSec r

20、 1 h * MERGEFORMAT SEQ MTChap h * MERGEFORMAT 3快速傅里叶变换3.1直接计算DFT的特点及减少运算量的基本途径长度为N的有限长序列的DFT为 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 3. SEQ MTSec c * Arabic * MERGEFORMAT 1. SEQ MTEqn c * Arabic * MERGEFORMAT 1)考虑为复数序列的一般情况，对某一个k值，直接按式 MA

21、CROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 3. SEQ MTSec c * Arabic * MERGEFORMAT 1. SEQ MTEqn c * Arabic * MERGEFORMAT 2)计算值需要N次复数乘法、(N-1)次复数加法。 N点DFT的复乘次数等于N2。显然，把N点DFT分解为几个较短的DFT，可使乘法次数大大减少。另外，旋转因子WmN具有明显的周期性和对称性。其周期性表现为 MACROBUTTON MTPlaceRe

22、f * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 3. SEQ MTSec c * Arabic * MERGEFORMAT 1. SEQ MTEqn c * Arabic * MERGEFORMAT 3)其对称性表现为 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 3. SEQ MTSec c * Arabic * MERGEFO

23、RMAT 1. SEQ MTEqn c * Arabic * MERGEFORMAT 4) MACROBUTTON MTEditEquationSection2 SEQ MTEqn r h * MERGEFORMAT SEQ MTSec r 2 h * MERGEFORMAT SEQ MTChap r 3 h * MERGEFORMAT 利用这些特性，是FFT运算中有些项可以合并；利用的对称性、周期性，可以将长序列的FFT分解为短序列的DFT。FFT算法基本上分为两大类：按时间抽选法 (Decimation In Time ,简称DIT)和频域抽取法(Decimation In Frequen

24、cy,简称DIF)。下面只介绍DIT算法。3.2按时间抽选的（DIT）的基-2FFT算法 设序列的长度为N，且满足。如果不满足这个条件，可以人为地加若干零值点，使之达到要求。这种N为2的整数幂的FFT也称为基-2FFT。按n的奇偶把分解为两个N/2点的子序列 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 3. SEQ MTSec c * Arabic * MERGEFORMAT 2. SEQ MTEqn c * Arabic * MERGE

25、FORMAT 1)则的DFT为 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 3. SEQ MTSec c * Arabic * MERGEFORMAT 2. SEQ MTEqn c * Arabic * MERGEFORMAT 2)由于,上式可表示成 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEF

26、ORMAT 3. SEQ MTSec c * Arabic * MERGEFORMAT 2. SEQ MTEqn c * Arabic * MERGEFORMAT 3)其中和分别为和的N/2点DFT，即 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 3. SEQ MTSec c * Arabic * MERGEFORMAT 2. SEQ MTEqn c * Arabic * MERGEFORMAT 4) MACROBUTTON MTPlac

27、eRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 3. SEQ MTSec c * Arabic * MERGEFORMAT 2. SEQ MTEqn c * Arabic * MERGEFORMAT 5) 由于和均以N/2为周期，且，所以X(k)又可表示为 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 3. SEQ MTSe

28、c c * Arabic * MERGEFORMAT 2. SEQ MTEqn c * Arabic * MERGEFORMAT 6) MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 3. SEQ MTSec c * Arabic * MERGEFORMAT 2. SEQ MTEqn c * Arabic * MERGEFORMAT 7)(3.2.5)式和(3.2.6)式的运算可用图3-1的蝶形运算符号表示。图3-1 蝶形算法运算符号采用这种

29、表示方法，可将上述分解过程表示于图3-2中。此图表示N=8的情况，其中输出值 到由式(3.2.5)给出，而输出值到是由式(3.2.6)给出的。图3-2 N点DFT的一次时域抽取分解图(N=8)与第一次分解相同，将x1(r)按奇偶分解成两个N/4长的子序列x03(l)和x4(l)，即 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 3. SEQ MTSec c * Arabic * MERGEFORMAT 2. SEQ MTEqn c * Ar

30、abic * MERGEFORMAT 8)那么，X1(k)又可表示为 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 3. SEQ MTSec c * Arabic * MERGEFORMAT 2. SEQ MTEqn c * Arabic * MERGEFORMAT 9)式中 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Ara

31、bic * MERGEFORMAT 3. SEQ MTSec c * Arabic * MERGEFORMAT 2. SEQ MTEqn c * Arabic * MERGEFORMAT 10) MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 3. SEQ MTSec c * Arabic * MERGEFORMAT 2. SEQ MTEqn c * Arabic * MERGEFORMAT 11)同理，由和的周期性和的对称性，最后得到: 用

32、同样的方法可计算出 其中 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 3. SEQ MTSec c * Arabic * MERGEFORMAT 2. SEQ MTEqn c * Arabic * MERGEFORMAT 12) MACROBUTTON MTEditEquationSection2 SEQ MTEqn r h * MERGEFORMAT SEQ MTSec r 3 h * MERGEFORMAT SEQ MTChap r

33、3 h * MERGEFORMAT 将系数统一为，则一个N=8的点DFT就可分解为四个 的点DFT，这样可以得图3-3所示的流程图。图3-3 N点DFT的第二次时域抽取分解图(N=8)3.3DITFFT算法与直接计算DFT运算量的比较每一级运算都需要N/2次复数乘和N次复数加(每个蝶形需要两次复数加法)。所以，L级运算总共需要的复数乘次数为 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 3. SEQ MTSec c * Arabic * M

34、ERGEFORMAT 3. SEQ MTEqn c * Arabic * MERGEFORMAT 1)复数加次数为 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 3. SEQ MTSec c * Arabic * MERGEFORMAT 3. SEQ MTEqn c * Arabic * MERGEFORMAT 2)由于计算机上乘法运算所需时间比加法时间多得多，故以乘法为例，说明FFT算法和DFT算法运算量的比较。直接计算DFT与FFT算法的运算量之比为 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTChap c * Arabic * MERGEFORMAT 3. SEQ MTSec c * Arabic * MERGEFORMAT 3. SEQ MTEqn c * Arabic * MERGEFORMAT 3)图3-4是直接计算DFT与FFT算法所需运算量