数字信号处理ppt课件.ppt

《数字信号处理ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

数字信号处理(DigitalSignalProcessing)1 第3章离散傅里叶变换快速算法(FFT)内容提要问题的提出解决问题的思路与方法基2时间抽取FFT算法基2频率抽取FFT算法FFT算法的实际应用——实序列的DFT计算，IDFT的快速计算方法2 学习要求掌握基2时间抽取和基2频率抽取FFT算法的基本思想和方法。了解基4时间抽取FFT算法的基本原理。掌握实序列FFT计算，以及由N点序列FFT计算2N点序列FFT的方法。掌握利用FFT计算IDFT的过程，以及IFFT实现的原理。3 重点和难点本章的重点是基2时间抽取FFT算法的基本原理，FFT蝶形运算流图本章的难点是由短序列的DFT表达相应长序列的DFT的基本原理及方法4 目录ch3_1时间抽取FFTch3_2频率抽取FFTch3_3FFT应用5 问题的提出4点序列{2，3，3，2}DFT的计算复杂度复数加法N(N-1)复数乘法N2如何提高DFT的运算效率?6 解决问题的思路1.将长序列DFT分解为短序列的DFT2.利用旋转因子的周期性、对称性、可约性。7 旋转因子的性质(1)周期性(2)对称性(3)可约性8 解决问题的方法将时域序列逐次分解为一组子序列，利用旋转因子的特性，由子序列的DFT来实现整个序列的DFT。基2时间抽取(Decimationintime)FFT算法基2频率抽取(Decimationinfrequency)FFT算法9 基2时间抽取FFT算法基2时间抽取FFT算法推导基2时间抽取FFT算法流图基2时间抽取FFT算法的计算复杂度基2时间抽取FFT算法流图规律10 基2时间抽取FFT算法推导11 基2时间抽取FFT算法推导因此有:12 基2时间抽取FFT算法流图N=2x[k]={x[0],x[1]}13 4点基2时间抽取FFT算法流图x[0]x[2]x[1]x[3]X1[0]X1[1]X2[0]X2[1]2点DFT2点DFT-1-1-1-1X[0]X[1]X[2]X[3]14 4点基2时间抽取FFT算法流图15 8点基2时间抽取FFT算法流图4点DFT4点DFTx[0]x[2]x[4]x[6]x[1]x[3]x[5]x[7]X1[0]X1[1]X1[2]X1[3]X2[0]X2[1]X2[2]X2[3]X[0]X[1]X[2]X[3]X[4]X[5]X[6]X[7]-1-1-1-116 4点DFT4点DFTx[0]x[2]x[4]x[6]x[1]x[3]x[5]x[7]X1[0]X1[1]X1[2]X1[3]X2[0]X2[1]X2[2]X2[3]X[0]X[1]X[2]X[3]X[4]X[5]X[6]X[7]-1-1-1-18点基2时间抽取FFT算法流图17 第一级第二级第三级8点基2时间抽取FFT算法流图18 算法的计算复杂度复乘次数复乘次数NN219 基2时间抽取FFT算法流图第一级第二级第三级20 FFT算法流图旋转因子规律第二级的蝶形系数为，蝶形节点的距离为2。第一级的蝶形系数均为，蝶形节点的距离为1。第三级的蝶形系数为，蝶形节点的距离为4。第M级的蝶形系数为，蝶形节点的距离为N/2。21 倒序k0k1k2x[k2k1k0]x[000]x[100]x[010]01011]12x[kk0]x[k2k101x[110]x[001]x[101]x[011]x[111]0101010122 例：试利用N=4基2时间抽取的FFT流图计算8点序列x[k]={1,-1,1,-1,2,1,1,2}的DFT。解：根据基2时间抽取FFT算法原理，8点序列的DFTX[m]可由两个4点序列的DFTX1[m]和X2[m]表达。如果按照序列x[k]序号的奇偶分解为x1[k]和x2[k]，则存在其中x1[k]={1,1,2,1}，x2[k]={-1,-1,1,2}，X1[m]和X2[m]可通过4点的FFT来计算。23 例：试利用N=4基2时间抽取的FFT流图计算8点序列x[k]={1,-1,1,-1,2,1,1,2}的DFT。解：X1[m]={5,-1,1,-1},X2[m]={1,-2+3j,1,-2-3j}利用上述公式，可得序列x[k]的DFTX[m]为X[m]={6,-0.293+3.535j,1+j,-1.707+3.535j,4,-1.707-3.535j,1-j,-0.293-3.535j}24 离散傅里叶变换快速算法(FFT)问题的提出解决问题的思路与方法基2时间抽取FFT算法基2频率抽取FFT算法FFT算法的实际应用——实序列的DFT计算，IDFT的快速计算方法25 基2频率抽取FFT算法26 3NW-12NW-11NW-10NW-1x[0]x[4]x[1]x[5]x[2]x[6]x[3]x[7]4点DFTX[0]X[6]X[2]X[4]4点DFTX[1]X[3]X[5]X[7]27 X[0]X[6]X[4]X[2]X[1]X[5]X[3]X[7]0NW1NW2NW3NW-1-1-1-1x[0]x[3]x[1]x[2]x[4]x[5]x[6]x[7]0NW2NW2点DFT-1-12NW0NW-1-12点DFT2点DFT2点DFT28 0NW1NW2NW3NW-1-1-1-1x[0]x[3]x[1]x[2]x[4]x[5]x[6]x[7]0NW2NW2NW0NWX[0]X[6]X[4]X[2]X[1]X[5]X[3]X[7]0NW0NW0NW0NW-1-1-1-1-1-1-1-129 离散傅里叶变换快速算法(FFT)问题的提出解决问题的思路与方法基2时间抽取FFT算法基2频率抽取FFT算法FFT算法的实际应用——实序列的DFT计算，IDFT的快速计算方法30 FFT算法应用利用N点复序列的FFT，计算两个N点实序列FFT利用N点复序列的FFT，计算2N点序列的FFT利用FFT计算IFFT31 利用N点复序列的FFT算法计算两个N点实序列FFTx1[k],x2[k]是实序列，将其构成复序列y[k]=x1[k]+jx2[k]DFT{x1[k]+jx2[k]}=Y[m]32 利用N点复序列的FFT计算2N点序列的FFTy[k]是一个长度为2N的序列问题：如何利用N点FFT，计算4N点序列的FFT？33 利用FFT实现IFFT步骤：(1)将X[m]取共轭。(3)对步骤(2)中结果取共轭并除以N。34 此课件下载可自行编辑修改，供参考！感谢您的支持，我们努力做得更好！