北京交通大学：《数字信号处理》课程教学课件（PPT讲稿）第三章 快速傅里叶算法FFT（小结）

第三章离散傅里叶变换快速算法FFT的提出基2时间抽取FFT基2频率抽取FFT任意基时间抽取FFTFFT算法中的对称关系混合基FFTFFT算法应用

第三章 离散傅里叶变换快速算法 ⚫ FFT的提出 ⚫ 基2时间抽取FFT ⚫ 基2频率抽取FFT ⚫ 任意基时间抽取FFT ⚫ FFT算法中的对称关系 ⚫ 混合基FFT ⚫ FFT算法应用

FFT算法思想FFT算法的基本思想：长序列DFT分解为短序列的DFT旋转因子的性质W(k+N)m =Wk(m+N) =Wkm(1）周期性NNmk+N"=Wmk(2)对称性=-Wmk2WNN=Wmk/MWmk=WMmk(3）可约性WmkN/M为整数NNIM"NMN

FFT算法的基本思想：长序列DFT分解为短序列的DFT FFT算法思想 ( ) ( ) k N m k m N km WWW NNN + + (1) 周期性 = = (2) 对称性 ( ) km mk W W N N  − = (3) 可约性 2 N mk mk W W N N + = − mk Mmk W W N MN = / / , / mk mk M W W N M N N M = 为整数 旋转因子的性质

基2时间抽取FFT算法基2时间抽取FFT算法的原理、过程、矩阵表示、流图形式原理：在时域按照奇偶拆分的形式将长序列逐渐分解为两组子序列，计算两点序列的DFT将时域转换到频域，由两组短序列的DFT逐次合成长序列的DFT。N-1x[k]=x[2k]N2x[kjwknX[m] = x[k] -k =0,1,2[x2[k]=x[2k+1]k=0N/2-N/2-Zx[2k + 1JW(2k+1)mx[2k]W2km+X[m]= X,[m] +W"X,[m]NNk=0k=0X[m+N /2]=X,[m]-WmX,[m]2N/2-1Zx[2k +1] WN7?x[2k] Wk72"+W"Nm= 0,1Lk=0k=02

基2时间抽取FFT算法的原理、过程、矩阵表示、流图形式 基2时间抽取FFT算法 原理：在时域按照奇偶拆分的形式将长序列逐渐分解为两组子序列，计算两点序 列的DFT将时域转换到频域，由两组短序列的DFT逐次合成长序列的DFT。 /2 1 /2 1 /2 /2 0 0 [ 2 ] [2 1] N N km m km N N N k k x k x k W W W − − = = = +   + 1 0 [ ] [ ] − = =  N km N k X m x k W /2 1 /2 1 2 (2 1) 0 0 [2 ] [2 1] N N km k m N N k k x k W x k W − − + = = = + +   1 2 [2 [ ] ] 0,1, , 1 [ ] [ ] [ 1 2 ] 2 x k x x k x k N x k k k  = → =  = +  − 1 2 [ ] [ ] [ ] m X m X m W X m N = +1 2 [ / 2] [ ] [ ] m X m N X m W X m + = − N 0,1 1 2 N m = − L

基2时间抽取FFT算法短序列DFT合成长序列DFTX[m]X,[m]x[0X[O]X[m+ N /2]Wm X,[m]x[2]XT11时域到频域X[2]x[1][8] - X[3]x[3]

基2时间抽取FFT算法 0 1 2 [ ] 1 1 0 [ ] [ / 2] 1 1 0 [ ] N m N X m W X m X m N W X m = + −                   短序列DFT合成长序列DFT [0] [0] [1] [ 1 1 1 1 1] X x X x      =             −  时域到频域 −1 −1 −1 −1 −j x[0] x[3] x[2] x[1] X[3] X[2] X[1] X[0]

基2时间抽取FFT算法计算N=16点的DFT，直接计算DFT计算量是多少？如果用基2时间抽取FFT算法，计算量是多少？直接计算DFT：N2=1621og, N =161og, 16= 32基2时间抽取FFT：?

基2时间抽取FFT算法 计算N=16点的DFT，直接计算DFT计算量是多少？ 如果用基2时间抽取FFT算法，计算量是多少？ 直接计算DFT：N2=162 基2时间抽取FFT： 2 log 2 N N 2 16log 16 32 2 = =