DSP第4章快速付里叶变换FFT

1、第四章快速付里叶变换(FFT)Fast FourierTransforming弟P引言、快速付里叶变换FFT有限反序列通过离散傅里叶变换(DFT)将其频域离 散化成有限K序列但其计算量太大(与N的平方成 正比)，很难实时地处理问题，因 此引出了快速傅 里叶变换(FFT) FFT并不是一种新的变换形式，它只是DFT的一 种快速算法并且根据对序列分解与选取方法的不 同而产生了 FFT的多种算法. FFT在离散傅里叶反变换、线性卷积和线性相关 等方面也有重耍应用。:、FFT产生故事当时加文(Garwin)在自已的研究中极需要一个计算 付 里叶变换的快速方法。他注意到图基(J.W.Turkey)iE在

2、写有 关付里叶变换的文章，因此详细询问了图基关 于计算付里 叶变换的技术知识。图基概括地文寸加文介绍了一种方法， 它实质上就是后来的著名的库利(Cooley J.W)图基算法。 在加文的迫切要求下，库利很快设计出一个计算机程序。 1965年库利-图基在v计算 数学、Mathematic ofComputation杂志上发表了著乞的“机器计算付里级数的 一种算法”文章，提出一种快速计算DFT的方法和计算机 程序-揭开了 FFT发展 史上的第一页，促使FFT算法产牛 原因还有1967年至1968年间FFT的数字硬件制成，电子 数字计算机的条 件，使DFT的运算大简化了。、本章主要内容 1 立接计算

3、DFT算法存在的问题及改进途径。 2多种DFT算法（时间抽取算法DIT算法，频 率抽取算法DIF算法，线性调频Z变换即CZT 法） 3.FFT的应用第二节直接计算6 FT算法存在的问题及改进逐径'直接计算DFT计算量问题提出：设有限长序列x(n),非零值长度为 N,计算对x(n)进行一次DFT运算，共需多大的 运算工作量？1 比较DFT与IDFT之间的运算量N1x(n) dft>x 伙)二工上二0,1,N-1n=0N-X 伙)u)n>x(n)= VX 伙)A2 = 0,1, N -1 k=0其中x(n)为复数，W严之G”也为复数所以DFT与IDFT二者计算量相同。2以DFT

4、为例，计算DFT复数运算量计算一个X(k)(一个频率成分)值，运算量为N-例“ *予)昭耍进行N次复数乘法+(N-1)次复数加法所以，要完成整个DFT运算，其计算量为：3一次复数乘法换算成实数运算量复数运算要比加法运算复杂，需要的运算时间长。一个复数乘法包括4个实数乘法和2个实数加 法。(a4-jb)(c+jd)=(ac-bd)+j(bc 丈 ad)2次实4次实数乘法4.计算DFT需要的实数运算量N-1X 伙)二工(Re x(«) Re Wf-Im x(«) Im Wf) /»=0+ j(Rex(/i) Im n7 + Im x(«) Re W? )每运

5、算一个X(k)的值，需耍进行4N次实数相乘和2N+2(N-1 )=2(2N-1)次实数相加.整个DFT运算量为：4N2次实数相乘和2N(2N1)次实数相加.由此看出：直接计算DFT时，乘法次数与加法次数 都 是和N2成比例的。当N很大时，所需工作量非常可 观。例子例1:当N=1024点时，直接计算DFT需要:n2=220=i048576次，即一百多万次的复乘运算 这文寸实时 性很强的信号处理(如雷达信号处理)来 讲，它对计算速 度有十分苛刻的要求-迫切 需要改进DFT的计算方 法，以减少总的运算 次数。例2：石汕勘探，24道记录，每道波形记录长 度5秒，若每秒抽样500点/秒， 每道总抽样点数

6、=500*5=2500点24道总抽样点数=24*2500=6万点 DFT 运算时间=N2=(60000)2=36*108次:、改善DFT运算效率的基本途径利用DFT运算的系数吟的固有对称性和周期性，改 善DFT的运算效率。1 合并法：合并DFT运算中的某些项。3.分解法：将长序列DFT利用对称性和周期性，分解 为短序列DFT0利用DFT运算的系数的固有对称性和 周期性，改善DFT的运算效率的对称性：=亚咏因为：()=©八)=/v 1弋=0,1, wy的周期性:=wa')a =wAk _.2£efJ2A = 1()=2 F'由此可得出:+l) = _w()=es=1 比1N(W； (A) = WJN一心二 W；族(w：）二幺 a/2 =cosA-jsin 7i-例子,例：w9=w(4 =