第4章快速傅里叶变换课件.ppt

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

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

2、算DFT的问题及改进的途径4.2.1直接计算DFT的运算量问题若x(n)是N点序列，实现x(n)的DFT，即求出N个X(k)，需要N2次复数乘法，N(N-1)次复数加法。例如：x(n)：N=1024，N2=1048576式中旋转因子(TwiddleFactor)：4一般情况下，信号序列x(n)及其频谱序列X(k)都是用复数来表示的，WN当然也是复数。因此，计算DFT的一个值X(k)需要进行N次复数乘法（与1相乘也包括在内）和N-1次复数加法；所以，直接计算N点的DFT需要进行N2次复数乘法和N(N-1)复数加法。显然，直接计算N点的IDFT所需的复乘和复加的次数也是这么多。当N足够

3、大时，N2≈N(N-1),因此，DFT与IDFT的运算次数与N2成正比，随着N的增加，运算量将急剧增加，而在实际问题中，N往往是较大的，因此有必要对DFT与IDFT的计算方法予以改进。解决耗时的乘法问题是将数字信号处理理论用于实际的关键问题。特别是40年前，计算机的速度相当慢。因此，很多学者对解决DFT的快速计算问题产生了极大的兴趣。CooleyJW,TukeyJW.AnalgorithmforthemachinecomputationofcomplexFourierseries.MathematicsofComputation,1965,pp297~301的正式开端！DSP84.

4、2.2改善途径FFT的思路：如何充分利用这些关系？对称性周期性9减少运算量的基本途径旋转因子的主要性质为：⑴周期性：⑵对称性：⑶可约性：(4)特殊点：DFT和IDFT的快速算法的导出主要是根据因子的特性。减少运算量的基本途径FFT算法核心思想：利用DFT系数的特性；合并DFT运算中的某些项；把长序列DFT转换成短序列DFT，从而减少运算量。把长序列变短序列原因：DFT运算量和N2成正比，N降低，运算量就大大下降。利用WNnk的对称性和周期性，将大点数的DFT分解成若干个小点数的DFT，FFT正是基于这个基本思路发展起来的。N点DFTN/2点DFTN/4点DFT2点DFT1个2个4个

5、N/2个12以四点DFT为例13几个乘法？14分为：按频率抽取（DIF——Decimation-In-Frequency）法；按时间抽取（DIT——Decimation-In-Time）法：其中：基-2FFT是最基本的FFT算法，它要求FFT的点数N=2L（L为正整数）；如果序列长度不满足这一条件，需要用后补零值点的方法来补齐。FFT是在时域将序列逐次分解为长度减半的奇序号子序列和偶序号子序列，用子序列的DFT来实现整个序列DFT；问题是如何分最有效？4.3按时间抽取（DIT）的基-2FFT算法4.3.1算法原理设序列x(n)长度为N＝2M，M为整数(若不满足，则在序列尾部补零)。

6、将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）则16蝶形运算20X1(k)、X2(k)都是N/2点的DFT，它们各自又可分成N/4点的DFT，如此继续分下去，直至两点DFT。两点DFT不需要乘法运算：2点DFT的运算流图由于每一步分解都是按输入序列在时间上的奇偶次序，分解成两个半长的子序列，所以称“按时间抽取算法”。第一级L=1第二级L=2第三级L=3蝶形运算单元对于N=2M点FFT，一共有M级（L=1,2,…,M）；每级有N/2个蝶形；每级有N/2L组。时域奇偶分频域对半分

7、284.3.2运算量比较对N=2M，共可分M次，即m=0,1…M-1，每一级有N/2个如下的蝶形单元一个蝶形单元只需一次复数乘法，两次复数加法。总共复数乘法：复数加法：可以共享29直接计算DFT与FFT算法的计算量之比为如：N=1024：运算效率大大提高.N越大，优势越明显!314.3.3算法特点1）蝶形运算2）原位运算两点构成一个蝶形单元，并且这两点不再参与别的蝶形单元的运算。所谓原位运算，就是当数据输入到存储器后，每一级运算的结果仍然贮存在这同一组存储器中，直到最