快速傅里叶变换ppt课件.pptx

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

1、第7章快速傅里叶变换2第7章快速傅里叶变换7.1引言7.2直接计算DFT的问题及改进的途径7.3.1按时间抽取（DIT）的基-2FFT算法7.3.2按频率抽取（DIF）的基-2FFT算法补充内容：IDFT的高效算法补充内容：实序列的FFT算法37.1引言有限长序列通过离散傅里叶变换（DFT）将其频域离散化成有限长序列，但其计算量太大，很难实时处理，因此引出了快速傅里叶变换（FFT）。FFT并不是一种新的变换形式，它只是DFT的一种快速算法，并且根据对序列分解与选取方法的不同产生了多种算法。FFT在离散傅里叶反变换、线性卷积和线性相关等方面也有重要应用。447.2直接计算DF

2、T的问题及改进的途径7.2.1直接计算DFT的运算量问题若x(n)是N点序列，实现x(n)的DFT，即求出N个X(k)，需要N2次复数乘法，N(N-1)次复数加法。55一个复数乘法包括4个实数乘法和2个实数加法。一次复数加法需二次实数加法。例如：x(n)N=1024，N2=1048576因而每运算一个X(k)需4N次实数乘法和2N+2(N-1)=2(2N-1)次实数加法。所以，整个DFT运算总共需要4N2次实数乘法和2N(2N-1)次实数加法。(a+jb)(c+jd)=(ac-bd)+j(bc+ad)6解决耗时的乘法问题是将数字信号处理理论用于实际的关键问题。特别是40年前，计算

3、机的速度相当慢。因此，很多学者对解决DFT的快速计算问题产生了极大的兴趣。CooleyJW,TukeyJW.AnalgorithmforthemachinecomputationofcomplexFourierseries.MathematicsofComputation,1965,pp297~301的正式开端！DSP77.2.2改善途径FFT的思路：如何充分利用这些关系？对称性周期性8以四点DFT为例9几个乘法？10利用WNnk的对称性和周期性，将大点数的DFT分解成若干个小点数的DFT，FFT正是基于这个基本思路发展起来的。分类：按时间抽取（DIT）算法和按频率抽取（DIF）

4、算法。问题是如何分最有效？FFT的核心思想：N点DFTN/2点DFTN/4点DFT2点DFT1个2个4个N/2个DecimationinTimeDecimationinFrequency11的周期性的对称性127.3.1按时间抽取（DIT）的基-2FFT算法1.算法原理设序列x(n)长度为N＝2M，M为整数，将x(n)（n=0,1…N-1）按n的奇偶分解成两组N/2点的子序列x1(r)=x(2r)x2(r)=x(2r+1)r=0,1…N/2-1（长度为N/2）则13蝶形运算X1(k)、X2(k)都是N/2点的DFT，它们各自又可分成N/4点的DFT，如此继续分下去，直至两点DFT

5、。两点DFT不需要乘法运算：2点DFT的运算流图注意长度为N/2！15由于每一步分解都是按输入序列在时间上的奇偶次序，分解成两个半长的子序列，所以称“按时间抽取算法”。第一级第二级第三级蝶形运算单元162.运算量比较对N=2M，共可分M次，即m=0,1…M-1，每一级有N/2个如下的蝶形单元一个蝶形单元只需一次复数乘法，两次复数加法。总共复数乘法：复数加法：可以共享17直接计算DFT与FFT算法的计算量之比为183.算法特点1）原位运算两点构成一个蝶形单元，并且这两点不再参与别的蝶形单元的运算。所谓原位运算，就是当数据输入到存储器后，每一级运算的结果仍然贮存在这同一组存储器中，直

6、到最后输出，中间无需其它存储器。192）旋转因子的变化规律(4.2.13)如上所述，N点DIT―FFT运算流图中，每级都有N/2个蝶形。每个蝶形都要乘以因子，称其为旋转因子，p称为旋转因子的指数。不难发现，第L级共有2L-1个不同的旋转因子。N=23=8时的各级旋转因子表示如下：一般情况，第L级的旋转因子指数为L为从左到右的运算级数，编程时L为循环变量。20如果蝶形运算的两个输入数据相距B个点，应用原位运算，则式中B——两蝶形节点的“距离”（蝶距）3）蝶形运算214）倒位序输入序列x(n)的排列次序不符合自然顺序。此现象是由于按n的奇偶分组进行DFT运算而造成的，这种排列方式称为

7、“倒位序”。所谓“倒位序”，是指按二进制表示的数字首尾位置颠倒，重新按十进制读数。22倒位序的实现在实际运算时，先按自然顺序将输入序列存入存储单元，再通过变址运算将自然顺序变换成按DIT-FFT算法要求的顺序。变址的过程可以用程序安排加以实现--称为“整序”或“重排”（采用码位倒读）注意:(1)当I=J时，数据不必调换；(2)当I≠J时，必须将原来存放数据x(I)送入暂存器R，再将x(J)送入x(I)，R中内容送x(J)，进行数据对调。(3)为了避免再次调换已调换过的数据，保证调