第三章-离散傅里叶变换(DFT)及其快速算法(FFT)2.ppt

《第三章-离散傅里叶变换(DFT)及其快速算法(FFT)2.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、13.4DFT的快速算法——快速傅里叶变换(FFT)DFT使计算机在频域处理信号成为可能，但是当N很大时，直接计算N点DFT的计算量非常大。快速傅里叶变换（FFT，FastFourierTransform）可使实现DFT的运算量下降几个数量级，从而使数字信号处理的速度大大提高，工程应用成为可能。人们已经研究出多种FFT算法，它们的复杂度和运算效率各不相同。本章主要介绍最基本的基2FFT算法及其编程方法。23.4.1直接计算DFT的特点及减少运算量的基本途径DFT计算量：长度为N的序列x(n)的N点DFT为计算X(k)的每一个值需要计算N次复数乘法和N-1次复数加法，那么计算X(k)的N个值需要

2、N2次复数乘法和(N-1)N次复数加法运算。当N>>1时，N点DFT的复数乘法和复数加法运算次数均与N2成正比。3DFT减少运算量的基本途径：长序列分为短序列：由于N点DFT的运算量随N2增长，因此，当N较大时，减少运算量的途径之一就是将N点DFT分解为几个较短的DFT进行计算，则可大大减少其运算量。的周期性和对称性：的周期性：的对称性：4快速傅里叶变换就是不断地将长序列的DFT分解为短序列的DFT，并利用的周期性和对称性及其一些特殊值来减少DFT运算量的快速算法。5时间域抽取：频率域抽取：基2时间抽取(Decimationintime)DIT-FFT算法基2频率抽取(Decimationi

3、nfrequency)DIF-FFT算法长序列分解为短序列的方法63.4.2基2DIT-FFT算法基2FFT要求DFT变换区间长度N=2M，M为自然数。DIT-FFT算法序列x(n)的N点DFT为将上面的和式按n的奇偶性分解为7上式说明，按n的奇偶性将x(n)分解为两个N/2长的序列x1(l)和x2(l)，则N点DFT可分解为两个N/2点DFT来计算。(3.4.4)(3.4.5)(3.4.6)8将式(3.4.5)和式(3.4.6)代入式(3.4.4)，并利用X1(k)、X2(k)的隐含周期性可得到这样，就将N点DFT的计算分解为计算两个N/2点离散傅里叶变换X1(k)和X2(k)，再计算式(3

4、.4.7)。(3.4.7)(3.4.4)(3.4.5)(3.4.6)9蝶形图蝶形图及运算功能8点DFT一次时域抽取分解运算流图10运算量讨论两个N/2点DFT、N/2个蝶形N/2点DFT(N/2)2次复数乘法(N/2-1)(N/2)次复数加法蝶形1次复数乘法和两次复数加法可见,经过一次抽取分解,当N>>1时，N点DFT运算量近似下降一半。118点DIT-FFT运算流图N=8122.DIT-FFT的运算效率DIT-FFT与DFT所需乘法次数比较曲线13由8点DIT-FFT运算流图可见，N=2M时，其DIT-FFT运算流图由M级蝶形构成，每级有N/2个蝶形。因此，每级需要N/2次复数乘法运算和N次

5、复数加法运算，M级蝶形所需复数乘法次数CM(2)和复数加法次数CA(2)分别为直接计算N点DFT的复数乘法次数为N2，复数加法次数为(N-1)N。当N>>1时，N2/CM(2)>>1，所以N越大，DIT-FFT运算效率越高。DIT-FFT算法与DFT所需乘法次数与N的关系曲线见前页图示。14例如N=210=1024时，DIT-FFT的运算效率为而当N=211=2048时有DFT的乘法次数DIT-FFT的乘法次数153.DIT-FFT的运算规律及编程思想（1）原位计算（2）旋转因子的变化规律（3）蝶形运算规律（4）序列的倒序（5）编程思想16（1）原位计算N=2M点的FFT共进行M级运算，每级由

6、N/2个蝶形运算组成。同一级中，每个蝶形的两个输入数据只对计算本蝶形有用，而且每个蝶形的输入、输出数据节点又同在一条水平线上，这就意味着计算完一个蝶形后，所得输出数据可立即存入原输入数据所占用的存储单元。这样，经过M级运算后，原来存放输入序列数据的N个存储单元(A(0),A(1),…,A(N-1))中便依次存放X(k)的N个值。这种利用同一存储单元存储蝶形计算输入、输出数据的方法称为原位（址）计算。节约内存单元，降低设备成本17（2）旋转因子的变化规律N点DIT-FFT运算流图中，每级都有N/2个蝶形。每个蝶形都要乘以因子，称其为旋转因子，p称为旋转因子的指数。由于各级的旋转因子和循环方式都有

7、所不同。为了编写计算程序，应先找出旋转因子与运算级数的关系。用L表示从左到右的运算级数（L=1,2,…,M）。18由8点DIT-FFT运算流图可以发现，第L级共有2L-1个不同的旋转因子。N=23=8时的各级旋转因子表示如下:L=1时L=2时L=3时…对N=2M的一般情况，第L级的旋转因子为这样，就可按上面两个式子确定第L级运算的旋转因子。实际编程序时，L为最外层循环变量19（3）蝶形运算规律设序