信息学科立体化教材

《信息学科立体化教材》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第5章快速傅里叶变换5.1直接计算DFT算法存在的问题及改进途径5.2按时间抽取（DIT）的基-2FFT算法5.3蝶形、同址、变址运算5.4按频率抽取（DIF）的基-2FFT算法5.5快速傅里叶反变换（IFFT）5.6快速傅里叶变换FFT的应用5.7线性调频Z变换15.1直接计算DFT算法存在的问题及改进途径5.1.1直接计算DFT的运算量5.1.2改进途径25.1直接计算DFT算法存在的问题及改进途径快速傅里叶变换（FastFourierTransform，简称为FFT）并不是一种新的变换，而是离散傅里叶变换（DFT）的一种快速算法。由于有限长序列在其频域也可离散化为有限

2、长序列（DFT），因此离散傅里叶变换（DFT）在数字信号处理中是非常有用的。但是，在相当长的时间里，由于DFT的计算量太大，即使采用计算机也很难对问题进行实时处理，所以并没有得到真正的运用。直到1965年库利（J.W.Cooley）和图基（J.W.Tukey）首次提出了DFT运算的一种快速算法，后来又有桑德（G.Sande）和图基（J.W.Tukey）的快速算法相继出现以后，情况才发生了根本的变化。人们开始认识到DFT运算的一些内在规律，从而很快地发展和完善了一套高速有效的运算方法，这就是现在人们普遍称之为快速傅里叶变换（FFT）的算法。FFT出现后使DFT的运算大大简化，

3、运算时间一般可缩短一、二个数量级之多，从而使DFT的运算在实际中真正得到了广泛的应用。35.1.1直接计算DFT的运算量设x(n)为N点有限长序列，其DFT为k=0,1,…,N-1（5-1）反变换（IDFT）为n=0,1,…,N-1（5-2）二者的差别只在于WN的指数符号不同，以及差一个常数乘因子1/N，所以IDFT与DFT具有相同的运算工作量。下面我们只讨论DFT的运算量。4一般来说，x(n)和WNnk都是复数，X(k)也是复数，因此每计算一个X(k)值，需要N次复数乘法和N-1次复数加法。而X(k)一共有N个点（k从0取到N-1），所以完成整个DFT运算总共需要N2次

4、复数乘法及N(N-1)次复数加法。在这些运算中乘法运算要比加法运算复杂，需要的运算时间也多一些。因为复数运算实际上是由实数运算来完成的，这时DFT运算式可写成5.1.1直接计算DFT的运算量（5-3）5由此可见，一次复数乘法需用四次实数乘法和二次实数加法；一次复数加法需二次实数加法。因而每运算一个X(k)需4N次实数乘法和2N+2(N-1)=2(2N-1)次实数加法。所以，整个DFT运算总共需要4N2次实数乘法和2N(2N-1)次实数加法。上述统计与实际需要的运算次数稍有出入，因为某些WNnk可能是1或j，就不必相乘了，例如WN0=1，WNＮ／２=-1，WNN/4=-j等就

5、不需乘法。但是为了便于和其他运算方法作比较，一般都不考虑这些特殊情况，而是把WNnk都看成复数，当N很大时，这种特例的影响很小。从上面的统计可以看到，直接计算DFT，乘法次数和加法次数都是和N2成正比的，当N很大时，运算量是很可观的，有时甚至是无法忍受的。例如，当N=8时，DFT需64次复乘，计算量小，而当对一幅N×N点的二维图像进行DFT变换，N=1024时直接计算DFT所需复乘次数为（N2)2≈1012次，如用每秒可做10万次复数乘法的计算机，即使不考虑加法运算时间，也需要近3000小时。这对实时性很强的信号处理来说，要么提高计算机的计算速度，而这样，对计算速度的要求太

6、高了。另外，就只能通过改进对DFT的计算方法，以大大减少运算次数。5.1.1直接计算DFT的运算量6下面讨论减少运算量的途径。仔细观察DFT的运算就可看出，利用系数（旋转因子）的以下固有特性，就可减少运算量：（1）WNnk的对称性（2）WNnk的周期性5.1.2改进途径（3）WNnk的可约性另外7这样，利用这些特性，使DFT运算中有些项可以合并，并能将长序列DFT分解为短序列的DFT进行运算。而前面已经说到，DFT的运算量是与N2成正比的，所以N越小越有利，因而小点数序列的DFT比大点数序列的DFT的运算量要小。快速傅里叶变换算法正是基于这样的基本思想而发展起来的。它的算

7、法形式有很多种，但基本上可以分成两大类，即按时间抽取（Decimation-in-Time，缩写为DIT）法和按频率抽取（Decimation-in-Frequency，缩写为DIF）法。下面分别进行探讨。5.1.2改进途径85.2按时间抽取（DIT）的基-2FFT算法设序列点数为N＝2M，M为整数。若不满足这个条件，可以人为地加上若干个零值点，达到这一要求。这种N为2的整数幂的FFT称为基-2FFT。按时间抽取（DIT）的基-2FFT算法的基本出发点是，利用旋转因子WNnk的对称性和周期性，将一个长序列的DFT分