北京交通大学：《数字信号处理》课程教学课件（讲稿）第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的 矩阵表示：

基2时间抽取FFT算法原理如何利用基2时间抽取FFT计算8点序列的DFT?8点序列DFT，可由2个4点DFT合成u每个4点序列DFT，可由2个2点DFT合成11通过2点序列DFT将时域变换到频域u两点序列的DFT x[K]=(x[O],x[1]]X[0] = x[0]+ x[1]éX[O]u él 1 uéx[O]u X[1] = x[0] - x[1]

如何利用基2时间抽取FFT计算8点序列的DFT？ u 8点序列DFT，可由2个4点DFT合成 u 每个4点序列DFT，可由2个2点DFT合成 u 通过2点序列DFT将时域变换到频域 基2时间抽取FFT算法原理 两点序列的DFT x[k]={x[0], x[1]}

基2时间抽取FFT算法原理短序列DFT合成长序列DFTuiewoéd1 éX[m]üO iéX,[m]u20018X[m+ N / 218w"1ex,[m)!0时域到频域éX[o]uel1 uéx[0]uC-188m1x11FFT算法蕴含的对称关系，为后续学习其他基FFT算法提供了有效的认知途径

基2时间抽取FFT算法原理 -1 1 短序列DFT合成长序列DFT 时域到频域 FFT算法蕴含的对称关系，为后续学习其他基FFT算法提供了有效的认知途径

m = 0,1X[m|= X[m]+W"X,[m],m = 0.,1X[m +2]= X[m]- W"X,[m],X,[0]x[0]X[0]2点DETw!X,[1]x[2]X[1]-1waX,[0]x[1] X[2]2点DFTWiWoX2[1]x[3] X[3]-1-1

x[0] x[2] x[1] x[3] X1 [0] X1 [1] X2 [0] X2 [1] 2 点DFT 2 点DFT - 1 - 1 - 1 - 1 X [0] X [1] X [2] X [3] 基 2时间抽取FFT算法流图

m = 0.1.2.3X[m]= X,[m]+W"X,[m],X[m + 4l= X[m]- WmX,[m].m = 0,1,2,3X,[0]X[0]x[0]X[1]X[1]x[2]X,[2]4点DFTx[4]X[2]X,[3]x[6]X[3]X2[0]Wx[1]X[4]X2[1]Wx[3]X[5]X2[2] W4点DFTx[5]X[6]X[3] wx[7]X[7]

基 2时间抽取FFT算法流图 4点DFT 4点DFT x[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 - 1

基2时间抽取FFT算法流图Xn[0]X,[0]x[0]X[0]WoXi[1]X[1]x[2]0X,[2]412[0X[2]x[4]X,[3]MX[3]x[6]X,[O]X21[0]SX[4]x[1]1W.X2[1]4X21[1]X[5]x[3]10WX2[2]X22[0]x[5]X[6]WX2[3] W322x[7]X[7]

4 点DFT x[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 - 1 基 2时间抽取FFT算法流图 4点DFT