《数字信号处理_10.ppt》由会员分享，可在线阅读，更多相关《数字信号处理_10.ppt（40页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1本节课内容本节课内容按按频率抽选频率抽选的基的基-2FFT算法算法*23.2 按频率抽取(DIF)的基-2FFT 算法 桑德-图基算法一、算法原理设序列点数N=2L，L为整数。将Xm按m的奇偶分组前，先将输入xk按k的顺序分成前后两半：前面的按时间抽取FFT算法是把输入序列xk按其顺序是偶数还是奇数来分解为越来越短的序列，这里讨论另一种FFT算法，称为按频率抽取(DIF)FFT算法，它是把输出序列Xm(也是N点序列)按其顺序的偶、奇来分解为越来越短的序列。34 按m的奇偶将Xm分成两部分：x1kx2k5则X2r和X2r+1分别是x1k和x2k的 N/2点DFT，记为X1m和X2m，碟形运算为
2、：令-1WNk6x10 x11x12x13x20 x21x22x23N/2点DFTN/2点DFTx0 x7x1x2x3)x4x5x6X10=X0X11=X2X12=X4X13=X6X20=X1X21=X3X22=X5X23=X7-1-1-1-13NW-1-12NW-1-11NW-1-10NW-1-1x0 x4x1x5x2x6x3x74点点DFTX0X6X2X44点点DFTX1X3X5X78N/2仍为偶数，进一步分解：N/2 N/49x30 x40 x31x41N/4点DFTN/4点DFTx10 x11x12x13X30=X10=X0X31=X12=X4X40=X11=X2X41=X13=X6-
3、1-110同理：其中：X0X6X4X2X1X5X3X70NW1NW2NW3NW-1-1-1-1-1-1-1-1x0 x3x1x2x4x5x6x70NW2NW2点点DFT-1-1-1-12NW0NW-1-1-1-12点点DFT2点点DFT2点点DFT12逐级分解，直到2点DFT当N=8时，即分解到x3k，x4k，x5k，x6k，k=0,1130NW1NW2NW3NW-1-1-1-1-1-1-1-1x0 x3x1x2x4x5x6x70NW2NW2NW0NWX0X6X4X2X1X5X3X70NW0NW0NW0NW-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1已知有限已知有限长长序列
4、序列xk 数数值为值为 1,2,-1,3，请按频率抽选的基，请按频率抽选的基-2FFT(快速傅里叶变换快速傅里叶变换)运算过程求运算过程求Xm，并画出蝶形流程图，并画出蝶形流程图 解：解：解：解：m=0,1,2,3 当m=2r为偶数时(r=0,1)令：得：已知有限已知有限长长序列序列xk 数数值为值为 1,2,-1,3，请按频率抽选的基，请按频率抽选的基-2FFT(快速傅里叶变换快速傅里叶变换)运算过程求运算过程求Xm，并画出蝶形流程图，并画出蝶形流程图 解：解：解：解：当m=2r为偶数时(r=0,1)得：由：已知有限已知有限长长序列序列xk 数数值为值为 1,2,-1,3，请按频率抽选的基，
5、请按频率抽选的基-2FFT(快速傅里叶变换快速傅里叶变换)运算过程求运算过程求Xm，并画出蝶形流程图，并画出蝶形流程图 已知有限已知有限长长序列序列xk 数数值为值为 1,2,-1,3，请按频率抽选的基，请按频率抽选的基-2FFT(快速傅里叶变换快速傅里叶变换)运算过程求运算过程求Xm，并画出蝶形流程图，并画出蝶形流程图 画出蝶形流程图19二、算法特点1.原位计算L级蝶形运算，每级N/2个蝶形。2.蝶形运算距离对N=2L点FFT，输入自然序，输出倒位序，两节点距离：2L-n=N/2n例如 N=23=8：(1)n=1 时的距离为 8/2=4；(2)n=2 时的距离为 8/4=2;(3)n=3 时
6、的距离为 8/8=1。20(1).相同点 (a).进行原位运算；(b).运算量相同，均为(N/2)Log2N次复乘，NLog2N次复加。(2).不同点 (a).DIT输入为倒位序，输出为自然顺序；DIF输入为自然顺序，输出为倒位序；3.DIF法与DIT法的异同21(b).蝶形运算不同1).(DIT)用矩阵表示=11222).(DIF)(DIF)用矩阵表示=1123(c)两种蝶形运算的关系 互为转置(矩阵)；将算法流图的所有支路方向都反向，交换输入和输出，即可得到另一种蝶形。(DIT)1111(DIF)24FFT算法应用算法应用 利用利用N点复序列的点复序列的FFT，计算两，计算两个个N点实序列
7、点实序列FFT 利用利用N点复序列的点复序列的FFT，计算，计算2N点序列的点序列的FFT 利用利用FFT计算计算IFFT25利用利用N点复序列的点复序列的FFT算法算法计算两个计算两个N点实序列点实序列FFTx1k,x2k是是实序列实序列实序列实序列，将其构成将其构成复序列复序列复序列复序列y y k k=x x1 k k+j j x x2 k k DFTx1k+j x2k=YR m+jYI m26 例：设x1k和x2k都是N点的实数序列，试用一次N点DFT运算来计算它们各自的DFT:27283.3 利用利用N点复序列的点复序列的FFT计算计算2N点序列的点序列的FFTyk是一个长度为是一个
8、长度为2N的序列的序列例：例：例：例：试利用试利用N=4基基2时间抽取的时间抽取的FFT流图计算流图计算8点序列点序列xk=1,-1,1,-1,2,1,1,2的的DFT。解：解：解：解：根据基根据基2时间抽取时间抽取FFT算法原理，算法原理，8点序列的点序列的DFT Xm可由两个可由两个4点序列的点序列的DFT X1m和和X2m表达。如果表达。如果按照序列按照序列xk序号的奇偶分解为序号的奇偶分解为x1k和和 x2k，则存在，则存在 其中其中x1k=1,1,2,1，x2k=-1,-1,1,2，X1m和和X2m可通过可通过4点的点的FFT来计算。来计算。例：例：例：例：试利用试利用N=4基基2时
9、间抽取的时间抽取的FFT流图计算流图计算8点序列点序列xk=1,-1,1,-1,2,1,1,2的的DFT。解：解：解：解：X1m=5,-1,1,-1,X2m=1,-2+3j,1,-2-3j利用上述公式，可得序列利用上述公式，可得序列xk的的DFT Xm为为Xm=6,-0.293+3.535j,1+j,-1.707+3.535j,4,-1.707-3.535j,1-j,-0.293-3.535j313.4 利用利用FFT实现实现IFFT 步骤：步骤：步骤：步骤：(1)将X m取共轭(3)对(2)中结果取共轭并除以N32IDFTIDFT的快速计算方法的快速计算方法1.稍微变动稍微变动FFT程序和参
10、数可实现程序和参数可实现IFFT33另外，可以将常数1/N分配到每级运算中，也就是每级蝶形运算均乘以1/2。比较两式可知，只要DFT的每个系数换WNkm成WN-mk，最后再乘以常数1/N就可以得到IDFT的快速算法-IFFT。34DIF方法352.不改不改(FFT)的程序直接实现的程序直接实现IFFT 36 这就是说，先将Xm取共轭，即将Xm的虚部乘-1，直接利用FFT程序计算DFT；然后再取一次共轭；最后再乘1/N，即得xk。所以FFT，IFFT可用一个子程序。37共轭共轭FFT乘1/N直接调用FFT子程序计算IFFT的方法：38本章小结本章小结直接计算直接计算直接计算直接计算DFTDFT所
11、需要的复数乘法加法次数；所需要的复数乘法加法次数；所需要的复数乘法加法次数；所需要的复数乘法加法次数；采用基采用基采用基采用基-2FFT-2FFT所需要的复数乘法加法次数；所需要的复数乘法加法次数；所需要的复数乘法加法次数；所需要的复数乘法加法次数；FFTFFT的基本思想的基本思想的基本思想的基本思想(将将将将长序列长序列长序列长序列DFTDFT分解为分解为分解为分解为短序列短序列短序列短序列的的的的DFT)DFT)，利用旋转因子，利用旋转因子，利用旋转因子，利用旋转因子WWN Nkmkm 的的的的周期性周期性周期性周期性、对称对称对称对称性性性性、可约性可约性可约性可约性。FFTFFT的特点
12、的特点的特点的特点(蝶形运算、原位计算、倒位蝶形运算、原位计算、倒位蝶形运算、原位计算、倒位蝶形运算、原位计算、倒位)39解决问题的方法解决问题的方法 将时域序列逐次将时域序列逐次将时域序列逐次将时域序列逐次分解分解分解分解为一组为一组为一组为一组子序列子序列子序列子序列，利用，利用，利用，利用旋转因旋转因旋转因旋转因子的特性子的特性子的特性子的特性，由子序列的，由子序列的，由子序列的，由子序列的DFTDFT来实现整个序列的来实现整个序列的来实现整个序列的来实现整个序列的DFTDFT。基基基基2 2时间抽取时间抽取时间抽取时间抽取(Decimation in(Decimation in time)FFTtime)FFT算法算法算法算法 基基基基2 2频率抽取频率抽取频率抽取频率抽取(Decimation in(Decimation in frequency)FFTfrequency)FFT算法算法算法算法40作业作业 P117 3-4 3-7 3-9