信号分析与处理（修订版） 课件 吴京 【ch010】快速傅里叶变换

高等院校公共课系列精品教材第十章快速傅里叶变换高等院校公共课系列精品教材电子信息科学与工程类改进DFT计算的方法0101改进DFT计算的方法一、直接计算DFT的特点根据定义,长度为N的有限长序列x(n)的DFT为由上式看出DFT的计算中只包含乘法和加法运算。如果x(n)为复数序列,则根据上式完成N点X(k)的运算次数分析如表10.1所示。01改进DFT计算的方法可见,一次复数乘法包括了四次实数乘法和二次实数加法；一次复数加法则需要二次实数加法。所以对某一k值,计算X(k)需要4N次实数乘法2N+2(N-1)=2(2N-1)次实数加法。一个完整的

N点DFT运算共需要4N2次实数乘法和2N(2N-1)次实数加法。当N较大时,计算DFT需要消耗大量

的时间,很难满足系统的实时性要求。所以改进DFT算法,提高运算效率是非常必要的。一、直接计算DFT的特点复数运算是由实数运算来完成的,可以写成01改进DFT计算的方法二、减少运算量的方法的特点，可以减少DFT的运算次数。观察DFT运算可以看出,利用旋转因子有如下特性。(1)对称性：周期性：可约性：(4)特殊值：按时间抽取(DIT)的FFT算法0202按时间抽取(DIT)的FFT算法一、算法原理设序列长度为N=2M(M为整数)。如果给定长度不满足这个条件,可以通过补零满足要求。这种长度N为2的整数幂的FFT,称为基2-FFT。根据其形状又称其为蝶形运算单元。图中左侧X1(k)和X2(k)为输入,右侧为输出。可以看出,每个蝶形运算单元，需要一次复数乘法及两次复数加(减)法。完成一个蝶形运算需要一次复数乘法和两次复数加法。02按时间抽取(DIT)的FFT算法二、时间抽取FFT的运算量由8点时间抽取FFT流图可见,一个N=2M点序列的DFT经过M次分解,可以分解成M级蝶

形运算,每一级都由N/2个蝶形运算组成。因此全部N点的FFT共有号N/2×M个蝶形运算。每个蝶形运算需要一次复数乘法和二次复数加法运算。所以N点的FFT所需的运算次数如下。复数乘法：复数加法：而直接计算DFT需要N2次复数乘法和N(N-1)次复数加法。02按时间抽取(DIT)的FFT算法三、时间抽取法的运算特点1.蝶形运算一个N=2M点序列的DFT经过M次分解,全部运算都变为蝶形运算。每个蝶形运算单元完成下述基本递推运算：2.原位运算原位运算就是将蝶形运算的结果仍然保存在原输入量的存储单元中。即某一列的

N个数据送到存储器后,经蝶形运算,其结果为另一列数据,它们以蝶形为单位仍存储在这一组存储器中，直到最后输出,中间无需其他存储器。每列的N/2个蝶形运算全部完成后,再开始下一列的蝶形运算。02按时间抽取(DIT)的FFT算法三、时间抽取法的运算特点倒位序所谓倒位序,就是将二进制数的最高有效位到最低有效位的位序进行颠倒排列而得到的二进制数。倒位序的二进制数通常又称倒序数。蝶形运算两节点间距离第m级蝶形运算可写成的确定在时域抽取法的FFT运算流图中,每一级都有N/2个蝶形运算，每个蝶形运算都要乘以旋转因子 。每一级旋转因子都不相同,但排列却很有规律。按频率抽取(DIF)的FFT算法0303按频率抽取(DIF)的FFT算法每个蝶形运算需要一次复数乘法和二次复数加法运算。所以频率抽取法运算量与时间抽取法相同,都需要复数乘法 次，复数加法：NM=Nlog2N次。一、算法原理03按频率抽取(DIF)的FFT算法二、运算特点频率抽取法的运算特点与时间抽取法基本相同,都是通过蝶形运算完成,也是原位运算，其输人是正常位序,输出为倒位序。按流图转置定理,即将流图的所有支路方向取反,交换输入输出，系数保持不变,可得到流图的转置形式。频率抽取法和时间抽取法是两种等价的FFT运算。FFT算法流图并不唯一,在上面两种FFT的算法流图的基础上稍作变换,可以得到其他形式的FFT流图。这是因为对任何流图只要保证各节点所连