华侨大学自动化专业数字信号处理ppt3.ppt
第3章 离散傅里叶变换的 快速算法（FFT）一、基2时间抽取FFT算法二、基2频率抽取FFT算法三、FFT算法的实际应用四、基4时间抽取FFT算法五、混合基FFT算法问题的提出N点序列DFT的计算复杂度复数加法 N(N-1)复数乘法 N 2如何提高DFT的运算效率？解决问题的思路1.将长序列DFT分解分解为短序列的DFT，再将短序列的DFT合成合成为长序列的DFT2.利用旋转因子 的周期性周期性、对称性对称性、可约性可约性。旋转因子 的性质(1)周期性(2)对称性(3)可约性一、基2时间抽取FFT算法1.基2时间抽取FFT算法原理2.基2时间抽取FFT算法流图3.基2时间抽取FFT算法的计算复杂度4.基2时间抽取FFT算法结构特点1.基2时间抽取FFT算法原理（1）分解）分解将长度为N的时域时域序列x分解为两个两个长度为N/2的短序列x1、x2偶数点序列奇数点序列这两个短序列的N/2点DFT为（2）合成）合成2.基2时间抽取FFT算法流图n基2时间抽取蝶形运算蝶形运算的信号流图X1mX2mXmXm+N/2-12点序列DFT运算流图N=2xk=x0,x14点基点基2时间抽取时间抽取FFT算法流图算法流图x0 x2x1x3X10X11X20X212点DFT2点DFT-1-1-1-1X 0X 1X 2X 34点基点基2时间抽取时间抽取FFT算法流图算法流图x0 x2x1x3X10X11X20X21-1-1-1-1X 0X 1X 2X 38点基点基2时间抽取时间抽取FFT算法流图算法流图4点DFT4点DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7-1-1-1-14点DFT4点DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7-1-1-1-18点基点基2时间抽取时间抽取FFT算法流图算法流图第一级第一级第二级第二级第三级第三级8点基点基2时间抽取时间抽取FFT算法流图算法流图3.基2时间抽取FFT算法的计算复杂度基2时间抽取FFT的复乘次数N 24.基2时间抽取FFT算法结构特点（1）序列原位运算（2）序列倒序运算（3）旋转因子分布规律（1）序列原位(in-place)运算：x0 x4x2x6x1x5x3x7A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)输入序列存储单元存储单元第一级输出第二级输入第二级输出第三级输入X110X111X120X121X210X211X220X221A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)X10X11X12X13X20X21X22X23A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)X 0X 1X 2X 3X 4X 5X 6X 7A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)第三级输出每级运算结果仍存储在原来位置，无需存储中间计算结果。（2）序列倒序运算k0k1k2xk2 k1k0 x00 0 x10 0 x01 00 01 10 01 1112 xk k0 xk2 k10 01 1x11 0 x001 x101 x01 1x111 0 01 10 01 10 01 10 01 1xk211xk200 xk210 xk201倒序的实现变址A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)存储单元存储单元x000 x001 x010 x011 x100 x101 x110 x111x000 x100 x010 x110 x001x101 x011 x111自然顺序输入倒序变址变址xk=xk2k1k0存储单元数据不对换存储单元数据对换例：已知xk=1,2,3,4，利用基2时间抽取FFT算法流图计算13244 6-2-2 10-2-2+2j-2-2jDFTxk=10,-2+2j,-2,-2-2j04W14Wx0 x3x1x2X3X1X2X0-1-1-1-1（3）旋转因子分布规律第二级的蝶形系数为 ，蝶形节点的距离为2。第一级的蝶形系数均为 ，蝶形节点的距离为1。第三级的蝶形系数为 ，蝶形节点的距离为4。第M级的蝶形系数为 ，蝶形节点的距离为N/2。每级蝶形系数的数目比前级增加一倍，节点间距离也增加一倍每级蝶形系数的数目比前级增加一倍，节点间距离也增加一倍推广到N=2M的一般情况：二、基2频率抽取FFT算法1.基2频率抽取FFT算法原理2.基2频率抽取FFT算法流图3.频率抽取与时间抽取的比较1.基2频率抽取FFT算法原理n将频域频域序列Xm分成偶数点序列和奇数点序列令则2.基2频率抽取FFT算法流图n基2频率抽取蝶形运算蝶形运算的信号流图xkxk+N/2x1kx2k-13NW-12NW-11NW-10NW-1x0 x4x1x5x2x6x3x74点点DFTX0X6X2X44点点DFTX1X3X5X78点基点基2频率抽取频率抽取FFT算法流图算法流图x10 x13x11x12x20 x21x22x23X0X6X4X2X1X5X3X70NW1NW2NW3NW-1-1-1-1x0 x3x1x2x4x5x6x70NW2NW2点点DFT-1-12NW0NW-1-12点点DFT2点点DFT2点点DFT0NW1NW2NW3NW-1-1-1-1x0 x3x1x2x4x5x6x70NW2NW2NW0NWX0X6X4X2X1X5X3X70NW0NW0NW0NW-1-1-1-1-1-1-1-1例：已知xk=1,2,3,4利用基2频域抽取流图，计算12344-262j10-2-2+2j-2-2jDFTxk=10,-2+2j,-2,-2-2j3.频率抽取与时间抽取的比较n计算复杂度相同n对每一种按时间抽取的FFT流图都存在一个按频率抽取的FFT流图，它们互为转置（将流图中的输入和输出交换并且将所有支路方向都反向）。区别区别频率抽取频率抽取时间抽取时间抽取蝶形运算方法复乘只在减法之后先作复乘后作加减法蝶形运算意义由时域长序列分解为两个短序列由两个短序列的DFT合成长序列的DFTFFT流图前面逐级分解为短序列，最后一级完成N/2个2点DFT计算第一级完成N/2个2点DFT计算，后面逐级合成长序列的DFTn频率抽取方法的输入为顺序、输出为倒序，时间抽取方法的输入为倒序、输出为顺序是否为两种FFT算法的本质区别？输入倒序输出顺序基2时间抽取FFT算法流图输入顺序输出倒序三、FFT算法的实际应用1.实序列的DFT计算2.IDFT的快速计算方法1.实序列的DFT计算由实数序列构造复数序列，利用DFT的对称性，进一步减少DFT的计算量（1）利用N点复序列的FFT，计算两个N点实序列DFT（2）利用N点复序列的FFT，计算2N点实序列的DFTxk,hk是是实序列实序列，将其构成将其构成复序列复序列yk=xk+j hkDFTxk+j hk=DFTyk=Y m（1）利用N点复序列的FFT算法 计算两个N点实序列DFT例3-1 已知两个4点实序列分别为xk=1,2,0,1,hk=2,2,1,1，试利用4点序列FFT算法同时计算两个实序列的DFT Xm和Hm。n构造复数序列ykn计算复数序列的4点FFT Ym，并计算n由前面的公式得到Xm和Hmyk是一个长度为是一个长度为2N的序列的序列问题：如何利用问题：如何利用N点点FFT，计算，计算4N点序列的点序列的FFT？（2）利用N点复序列的FFT 计算2N点实序列的DFT如果yk是实序列，则可由实序列x1k和x2k构成一个N点复序列，计算该N点复序列的DFT同时得到X1m和X2m2.IDFT的快速计算方法（1）类似FFT流图方法计算IFFT（2）直接由FFT计算IFFT（1）类似FFT流图方法计算IFFTn将系数 换成n最后一级乘以常数1/N 步骤：步骤：步骤：步骤：将X m取共轭。对步骤中结果取共轭并除以N。（2）直接由FFT计算IFFT 用FFT流图计算DFTX*mn例3-2 已知某4点序列xk的DFT为Xm=1+2j,2+3j,3+4j,4+5j，试利用基2时间抽取FFT流图计算其对应的序列xk，并通过IDFT定义公式验证计算结果。四、基4时间抽取FFT算法n将N点时间序列分解为4个N/4点的时间短序列n4个N/4点序列的频谱可通过下式 合成N点序列的频谱利用DFT的周期性以及旋转因子的特性,可得 基2时间抽取FFT算法的基本关系基3时间抽取FFT算法的基本关系基4时间抽取FFT算法的基本关系基p时间抽取FFT算法的基本关系序列xk长度为N=pq,将其按时间抽取方式分解为p个q点序列 由于Xpm隐含以q为周期，故可得 q点序列可以按照q=uv方式进一步分解 五、混合基FFT算法各级分解的基可以不同各级分解的基可以不同可以减少序列补可以减少序列补0的个数，提高的个数，提高FFT算法的效率算法的效率本章小结一、基一、基2时间抽取时间抽取FFT算法算法1.基2时间抽取FFT算法原理2.基2时间抽取FFT算法流图3.基2时间抽取FFT算法的计算复杂度4.基2时间抽取FFT算法结构特点二、基二、基2频率抽取频率抽取FFT算法算法1.基2频率抽取FFT算法原理2.基2频率抽取FFT算法流图3.频率抽取与时间抽取的比较三、三、FFT算法的实际应用算法的实际应用1.实序列的DFT计算2.IDFT的快速计算方法四、基四、基4时间抽取时间抽取FFT算法算法五、混合基五、混合基FFT算法算法
