北京交通大学：《数字信号处理》课程教学课件（讲稿）第3章 快速傅里叶算法FFT 3.2 基2时间抽取FFT算法原理

基2时间抽取FFT算法基2时间抽取FFT算法原理基2时间抽取FFT算法流图1基2时间抽取FFT算法流图特点11基2时间抽取FFT算法的复杂度1

u 基2时间抽取FFT算法原理 u 基2时间抽取FFT算法流图 u 基2时间抽取FFT算法流图特点 u 基2时间抽取FFT算法的复杂度 基2时间抽取FFT算法

基2时间抽取FFT算法原理N-1i x,[k] = x[2k]LX[m] =a x[kJW kmk = 0,1,Lx[k] ?Ni x2[k] = x[2k + 1]k=0N/2-1N/2-1N=2Maoa2kmx[2k + 1]W (2k+1)mx[2k ]W+Nk=0k=0N/2-N/2-aWkmoakm+WmWx[2k]x[2k + 1]二NN/2N/2k-0k=0N/2-1km记 X,[m]=ax,[k]WN/2Nk-01m = 0,1L2N/2- 1x,[kjw?X,[m]=a k-0

基2时间抽取FFT算法原理 N=2 M

基2时间抽取FFT算法原理N/2-1N/2- 1oaX,[k] Wkmx,[k] Wkm+WmaX[m]=N12NN /2k-0k=0N/2- 1记X[m]- a x[kjw?Nk=00.11m =2N/2- 1x,[kjW kmX,[m]= aN/2k-0因此有:Nm = 0,1LX[m] = X[m]+W"X,[m]2

因此有: 基2时间抽取FFT算法原理

基2时间抽取FFT算法原理Nm = 0,1LX[m]= X,[m]+WmX,[m]2将m加上N/2，代入X[m+N/2] = X,[m+N/2]+W"+N/2X,[m+N/2]由于X[ml和X[m|隐含有周期性，可得NX[m+ N /2] = X,[m]- W"X,[m] m = 0,1L2

由于X1 [m] 和X2 [m]隐含有周期性，可得 基2时间抽取FFT算法原理 将m加上N/2，代入

基2时间抽取FFT算法原理短序列DFT合成长序列DFTNm = 0,1LX[m] = X,[m]+W"X,[m]X[m+ N /2] = X,[m]- W"X,[m]蝶形图WX,[m]o-0 X[m]短序列DFT合成长序列DFT的矩阵表示：WwX2[m]00X[m+N/2]ü él lüéweX[m]o ueX,[mluX[m+N/2 -1u0 wx,[ml

基2时间抽取FFT算法原理 短序列DFT合成长序列DFT 蝶形图 短序列DFT合成长序列DFT的 矩阵表示：