快速付里叶变换fftfastfouriertransforming

《快速付里叶变换fftfastfouriertransforming》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、变换的快速方法。他注意到图基(J.W.Turkey)正在写有关付里叶变换的文章，因此详细询问了图基关于计算付里叶变换的技术知识。图基概括地对加文介绍了一种方法，它实质上就是后来的著名的库利(CooleyJ.W)图基算法。在加文的迫切要求下，库利很快设计出一个计算机程序。1965年库利--图基在<计算数学>、MathematicofComputation杂志上发表了著名的“机器计算付里级数的一种算法”文章，提出一种快速计算DFT的方法和计算机程序--揭开了FFT发展史上的第一页，促使FFT算法产生原因还有1967年至1968年间F

3、FT的数字硬件制成，电子数字计算机的发明，使DFT的运算大大简化了。三、本章主要内容1.直接计算DFT算法存在的问题及改进途径。2.多种DFT算法(时间抽取算法DIT算法，频率抽取算法DIF算法，线性调频Z变换即CZT法)3.FFT的应用第二节直接计算DFT算法存在的问题及改进途径一、直接计算DFT计算量问题提出：设有限长序列x(n),非零值长度为N,计算对x(n)进行一次DFT运算，共需多大的运算工作量?1.比较DFT与IDFT之间的运算量其中x(n)为复数，也为复数所以DFT与IDFT二者计算量相同。2.以DFT为例，计算

4、DFT复数运算量计算一个X(k)(一个频率成分)值，运算量为例k=1则要进行N次复数乘法+(N-1)次复数加法所以，要完成整个DFT运算[X(k)有N个点]，其计算量为：N*N次复数相乘和N*(N-1)次复数加法3.一次复数乘法换算成实数运算量复数运算要比加法运算复杂，需要的运算时间长。一个复数乘法包括4次实数乘法和2次实数加法。(a+jb)(c+jd)=(ac-bd)+j(bc+ad)4次实数乘法2次实数加法4.计算DFT需要的实数运算量每运算一个X(k)的值，需要进行4N次实数相乘和2N+2(N-1)=2(2N-1)次实数相

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

6、24*2500=6万点DFT运算时间=N2=(60000)2=36*108次作业P200页，第1题二、改善DFT运算效率的基本途径利用DFT运算的系数的固有对称性和周期性，改善DFT的运算效率。1.合并法：合并DFT运算中的某些项。2.分解法：将长序列DFT利用对称性和周期性，分解为短序列DFT。利用DFT运算的系数的固有对称性和周期性，改善DFT的运算效率的对称性：的周期性：因为：由此可得出：例子例:利用以上特性,得到改进DFT直接算法的方法.(1)合并法：步骤1-分解成虚实部合并DFT运算中的有些项对虚实部而言所以代入DFT

7、中：(1)合并法：步骤2-代入DFT中展开：(1)合并法：步骤3-合并有些项根据：有：(1)合并法：步骤4-结论由此找出其它各项的类似归并方法：乘法次数可以减少一半。例：2、将长序列DFT利用对称性和周期性分解为短序列DFT--思路因为DFT的运算量与N2成正比的如果一个大点数N的DFT能分解为若干小点数DFT的组合，则显然可以达到减少运算工作量的效果。2、将长序列DFT利用对称性和周期性分解为短序列DFT--方法把N点数据分成二半：其运算量为：再分二半：+=+++=这样一直分下去，剩下两点的变换。2、将长序列DFT利用对称性和

8、周期性分解为短序列DFT--结论快速付里时变换(FFT)就是在此特性基础上发展起来的，并产生了多种FFT算法，其基本上可分成两大类：按抽取方法分：时间抽取法(DIT);频率抽取法(DIF)按“基数”分：基-2FFT算法；基-4FFT算法；混合基FFT算法；分裂基