第三章离散傅里叶变换和快速付里叶变换ppt课件.ppt

《第三章离散傅里叶变换和快速付里叶变换ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、3.4快速傅立叶变换FFT产生1965年，库利--图基在《计算数学》（MathematicofComputation）杂志上发表了著名的“机器计算傅里级数的一种算法”文章，提出一种快速计算DFT的方法和计算机程序--揭开了FFT发展史上的第一页。本节主要内容•直接计算DFT算法存在的问题及改进途径。•FFT算法(基－2时间抽取算法）•FFT的应用直接计算DFT计算量问题提出：设有限长序列x(n)，非零值长度为N，计算对x(n)进行一次DFT运算，共需多大的运算工作量?一、直接计算DFT算法存在的问题及改进途径(1)以DFT为例，计算

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

3、为：4N2次实数相乘和2N(2N-1)次实数相加.由此看出：直接计算DFT时，乘法次数与加法次数都是和N2成比例的。当N很大时，所需工作量非常可观。当N=1024点时，直接计算DFT需要：N2=220=1048576次，即一百多万次的复乘运算。这对实时性很强的信号处理(如雷达信号处理)来讲，它对计算速度有十分苛刻的要求迫切需要改进DFT的计算方法，以减少总的运算次数。(4)比较DFT与IDFT之间的运算量其中x(n)为复数，也为复数所以DFT与IDFT二者计算量相同。2.改善DFT运算效率的基本途径利用DFT运算的系数的固有对称性和

4、周期性，改善DFT的运算效率。•合并法：合并DFT运算中的某些项。•分解法：将长序列DFT利用对称性和周期性，分解为短序列DFT。利用DFT运算的系数的固有对称性和周期性，改善DFT的运算效率的对称性：的周期性：因为：由此可得出：例:利用以上特性,得到改进DFT直接算法的方法.将长序的DFT利用对称性和周期性分解为短序列DFTDFT的运算量与N2成正比如果一个大点数N的DFT能分解为若干小点数DFT的组合，则显然可以达到减少运算工作量的效果。方法把N点数据分成二半：其运算量为：再分二半：+=+++=这样一直分下去，剩下两点的变换。

5、结论快速付里时变换(FFT)就是在此特性基础上发展起来的，并产生了多种FFT算法，其基本上可分成两大类：按抽取方法分：时间抽取法(DIT)；频率抽取法(DIF)按“基数”分：基-2FFT算法；基-4FFT算法；混合基FFT算法；分裂基FFT算法其它方法：线性调频Z变换(CZT法)二、基--2按时间抽取的FFT算法Decimation-in-Time(DIT)1算法原理设输入序列长度为N=2M(M为正整数，将该序列按时间顺序的奇偶分解为越来越短的子序列，称为基2按时间抽取的FFT算法。也称为Coolkey-Tukey算法。其中基数2-

6、---N=2M，M为整数。若不满足这个条件，可以人为地加上若干零值（加零补长）使其达到N=2M。例子设一序列x(n)的长度为L=9，应加零补长为N=24=16应补7个零值。0123456789101112131415nx(n)2算法推导（1）分组DFT变换：先将x(n)按n的奇偶分为两组，作变量置换:当n=偶数时，令n=2r；当n=奇数时，令n=2r+1；得到：x(2r)=x1(r);x(2r+1)=x2(r)；r=0,…,N/2-1；(2)代入DFT中生成两个子序列x(0),x(2)…x(2r)奇数点x(1),x(3)…x(2r+

7、1)偶数点代入DFT变换式：(3)求出子序列的DFT上式得：(4)结论1一个N点的DFT被分解为两个N/2点DFT。X1(k),X2(k)这两个N/2点的DFT按照：再应用W系数的周期性，求出用X1(k),X2(k)表达的后半部的X(k+N/2)的值。（5）求出后半部的表示式后半部的k值所对应的X1(k)，X2(k)则完全重复了前半部分的k值所对应的X1(k),X2(k)的值。(6)结论2频域中的N个点频率成分为：结论：只要求出（0~N/2-1）区间内的各个整数k值所对应的X1(k)，X2(k)值，即可以求出(0~N-1)整个区间内

8、全部X(k)值，这就是FFT能大量节省计算的关键。(7）结论3由于N=2M，因此N/2仍为偶数，可以依照上面方法进一步把每个N/2点子序列，再按输入n的奇偶分解为两个N/4点的子序列，按这种方法不断划分下去，直到最后剩下的是2点DFT