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

河北大学2014届本科生学年论文（课程设计）I离散傅里叶变换及其快速算法摘要离散傅里叶变换(DFT)在数字信号处理等许多领域中起着重要作用。本文由离散傅里叶级数导出离散傅里叶变换定义及其计算方法。但DFT计算量太大，实际应用中有困难。为了减少运算次数，提高算法效率，常用快速傅里叶变换，文中简要介绍了几种方法。关键词：离散傅里叶变换；快速傅立叶变换；改进方法河北大学2014届本科生学年论文（课程设计）IIThediscreteFouriertransformandfastFourierTransformABSTRACTDiscreteFourierTransformplaysanimportantroleinmanyfieldsofthedigitalsignalprocessing.Inthisarticle,wededucedthedefinitionandcomputingmethodsofDiscreteFourierTransformfromDiscreteFourierSeries.Buttherearemanydifficultiesinthepracticalapplication,owingtothelargeamountofcomputation.Toimprovetheefficiencyandreducethecomputingcomplexity,FastFourierTransformarecommonlyused.FewmethodsofFastFourierTransformareintroducedinthetext.KeyWords:DiscreteFourierTransform;FastFourierTransform;improvementapproach河北大学2014届本科生学年论文（课程设计）III目录1引言............................................12离散傅里叶变换(DFT)的基本原理...................22.1引出离散傅里叶变换的必要性......................22.2离散傅里叶变换的定义...........................22.3离散傅里叶变换的性质...........................43快速傅里叶变换..................................53.1直接计算DFT的特点及减少运算量的基本途径..........53.2按时间抽选的（DIT）的基-2FFT算法................53.3DIT―FFT算法与直接计算DFT运算量的比较..........84总结............................................11参考文献...........................................12河北大学2014届本科生学年论文（课程设计）11引言连续时间傅里叶变换是一种积分变换，很难在实际中得到应用。离散傅里叶变换是为了适应利用计算机分析傅里叶变换而规定的一种专门运算，他是对连续时间信号频谱分析的逼近。由于大多数文献中很少详细地探讨连续傅里叶变换与离散傅里叶变换之间的关系，因此人们对离散傅里叶变换存在着模糊的理解。[1]有限长序列在数字信号处理中非常重要，当然可以用z变换和傅里叶变换来研究它，但可以导出反映它的有限长特点的一种有用工具是离散傅里叶变换。因此，DFT的计算在数字信号处理中非常有用。例如，在FIR滤波器设计中会遇到从h(n)求H(k)或由H(k)求h(n)，这就要计算DFT。再由，信号的频谱分析对通信、图像传输、雷达、声呐等都是很重要的。此外，在系统的分析、设计和实现中都会用到DFT的计算。[2]但在相当长的时间里,由于DFT的计算量太大，即使采用计算机也很难对问题实时处理，所以没有得到真正的应用。直到1965年J.W.Cooley和J.W.Tukey巧妙地利用NW因子的周期性和对称性，构造了DFT的快速算法，即快速离散傅里叶变换(FFT),在《计算数学》杂志上发表了著名的“机器计算傅里叶级数的一种算法”的文章，情况才发生改变。经过改进对算法的改进，发展和完善了一套高速有效的运算方法，使DFT的计算大大简化，运算时间可缩短一、二个数量级，从而使DFT的运算在实际当中真正得到了广泛的应用。在以后的几十年中，FFT算法有了进一步的发展，目前较常用的是基-2算法和分裂基算法。[3][4][5]河北大学2014届本科生学年论文（课程设计）22离散傅里叶变换(DFT)的基本原理2.1引出离散傅里叶变换的必要性有限长序列的离散傅里叶变换和周期序列的离散傅里叶变换（DFS）本质上是一样的，为了更好地理解DFT，需要讨论DFS。对离散时间信号的频谱分析，可以用离散时间傅里叶变换，即DTFT。DTFT使我们能够在数字域频率分析信号的频谱和离散系统的频率响应特性，但对于DTFT仍然存在两个实际问题。⑴数字域频率是一个连续变量，不利于用计算机进行计算。为了便于用数字的方法进行离散时间信号与系统的频域分析和处理，仅仅在时间域进行离散化还不够，还必须在频谱进行离散化。⑵数字化方法处理的序列只能为有限长的，所以，要专门讨论有限长序列的频谱分析问题。2.2离散傅里叶变换的定义根据以上要求，引出了有限长序列的离散傅里叶变换的概念。首先应指出，离散傅里叶变换使针对有限长序列或周期序列才存在的；其次，它相当于把序列的连续傅里叶变换加以离散化（抽样），频域的离散化造成时间函数也呈周期，故级数应限制在一个周期之内。有限长序列的离散傅里叶变换，简称为离散傅里叶变换，即DFT(DiscreteFourierTransform)。设xn是周期为N的一个周期序列，在01nN范围内,令2jNNWe它的离散傅里叶级数对如下：10,01NnkNnXkDFSxnxnWkN(2.2.1)101W,01NnkNnxnIDFSXkXknNN(2.2.2)把长度为N的有限长序列xn看成周期为N的周期序列的一个周期，利用DFS计算周期序列的一个周期，也就是计算了有限长序列。河北大学2014届本科生学年论文（课程设计）3设有限长序列xn，点数为N，即xn只在0~1nN有值，其他n时，0xn。把它看成周期为N的周期序列xn的一个周期，而把xn看成xn的以N为周期的周期延拓。令10nN-10,nNRn，其它，则它们的关系表示为Nxnxn(2.2.3)NNNxnxnRkxnRn(2.2.4)同理，对频域的周期序列Xk可以看成是对有限长序列Xk的周期延拓，而有限长序列Xk看成周期序列Xk的主值序列，即NXkXk(2.2.5)NNNXkXkRkXkRk(2.2.6)由(2.2.5)与(2.2.6)以上两式可以看出，求和是只限定在n=0到N-1及k=0到N-1的主值区间进行的，故完全适用于主值序列xn与Xk，即有限长序列的离散傅里叶变换定义正变换:10kN-1NnkNNnXkDFTxnxnWXkRk,0(2.2.7)反变换:101,N-1NnkNNnxnIDFTXkxnWxnRnnN0(2.2.8)两式构成离散傅里叶变换对。注意不要把离散傅里叶变换DFT和离散时间傅里叶变换DTFT混淆了。DTFT是对任意序列的傅里叶变换，它的频谱是一个连续函数，而DFT是对有限长序列的离散傅里叶变换，DFT的特点是无论在时域还是在频谱都是离散的，而且都是有限长的。河北大学2014届本科生学年论文（课程设计）42.3离散傅里叶变换的性质⑴线性设两个有限长序列为1xk和2xk，则1212DFTaxnbxnaXkbXk(2.3.1)⑵对称性设xn是长度为n的实序列，且DFTxnXk，则*XkXNk(2.3.2)⑶循环移位特性有限长序列为xn，若mNNxnxnmRn，则mkmmNNNXkDFTxnDFTxnmRnWXk(2.3.3)⑷循环卷积特性若12ynxnxn，则121YkXnXnN(2.3.4)河北大学2014届本科生学年论文（课程设计）53快速傅里叶变换3.1直接计算DFT的特点及减少运算量的基本途径长度为N的有限长序列xn的DFT为10()(),0,1,,1NknNnXkxnWkN(3.1.1)考虑xn为复数序列的一般情况，对某一个k值，直接按式(3.1.2)计算xn值需要N次复数乘法、(N-1)次复数加法。N点DFT的复乘次数等于N2。显然，把N点DFT分解为几个较短的DFT，可使乘法次数大大减少。另外，旋转因子WmN具有明显的周期性和对称性。其周期性表现为mlNmNNWW(3.1.3)其对称性表现为2[],NmNnkNnknknkmNNNNNN或者(3.1.4)利用这些特性，是FFT运算中有些项可以合并；利用nkNW的对称性、周期性，可以将长序列的FFT分解为短序列的DFT。FFT算法基本上分为两大类：按时间抽选法(DecimationInTime,简称DIT)和频域抽取法(DecimationInFrequency,简称DIF)。下面只介绍DIT算法。3.2按时间抽选的（DIT）的基-2FFT算法设序列xn的长度为N，且满足2,LNL为整数。如果不满足这个条件，可以人为地加若干零值点，使之达到要求。这种N为2的整数幂的FFT也称为基-2FFT。按n的奇偶把xn分解为两个N/2点的子序列12()(2),0,1,1()(21)2xrxrNrxrxr(3.2.1)则xn的DFT为河北大学2014届本科生学年论文（课程设计）6CABA＋BCA－BC1100/21/212(21)00/21/21221200()()()(2)(21)()W()NNknnkNNnnNNkrkrNNrrNNrkkrkNNNrrXkxnWxnWxrWxrWxrWxrW偶数奇数(3.2.2)由于222222/2jkrNjkrkrkrNNNWeeW,上式可表示成/21/211/22/21200()()()()()NNkrkkrkNNNNrrXkxrWWxrWXkWXk(3.2.3)其中1xn和2xn分别为1xn和2xn的N/2点DFT，即/2111/210()()[()]NkrNrXkxrWDFTxr(3.2.4)/2122/220()()[()]NkrNrXkxrWDFTxr(3.2.5)由于1xn和2xn均以N/2为周期，且2NkkNNWW，所以X(k)又可表示为12()()()0,1,12kNNXkXkWXkk(3.2.6)12()()()0,1,122kNNNXkXkWXkk(3.2.7)(3.2.5)式和(3.2.6)式的运算可用图3-1的蝶形运算符号表示。图3-1蝶形算法运算符号采用这种表示方法，可将上述分解过程表示于图3-2中。此图表示N=8的情况，其中输出值0x到3x由式(3.2.5)给出，而输出值4x到7x是由式(3.2.6)给出河北大学2014届本科生学年论文（课程设计）7N/2点DFTWN0N/2点DFTWN1WN2WN3x(0)X1(0)x