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

基2频率抽取FFT算法基2频率抽取FFT算法原理基2频率抽取FFT算法流图门

u 基2频率抽取FFT算法原理 u 基2频率抽取FFT算法流图 基2频率抽取FFT算法

基2频率抽取FFT算法原理(N/2-1!N-N- 1N=2Mix[kJWmkix[k]Wmkaax[k]Wmk1X[m]=a NNN.k=0.ik=N/2)k=0N/2- 1N/2- 1x[k + N /2]Wm(k+N/2)x[k]Wmkaa+二Nk=0k=0N/2-1([k]+WmN/2x[k + N /2])wmkak=0N/2- 1(x[k] +(- 1)" x[k + N / 2])W mkak=0

基2频率抽取FFT算法原理 N=2M

基2频率抽取FFT算法原理N/2- 1(x[k]+(- 1)" x[k + N / 2])WmkX[m]= :a入k-0x[k]NN/2-1Wmkm = 0,1,LX[2m]= a(x[k] + x[k + N / 2])I2N/2k=0x2[k]N/2-NUmka(x[k]- x[k + N /2DWkm = 0.1,LX[2m +1] =N/22k=0N/2-1a"x,[k]wwh= X[m]X[2m]= k=0Nm =0,1LN/2-12X[2m +1]= a x,[kjWn/h = X,[m]k=0

基2频率抽取FFT算法原理 x1 [k] x2 [k]

基2频率抽取FFT算法原理长序列分解为两个短序列W10 xi[k]x[k]ox,[k]= x[k]+ x[k + N / 2]WkX2[k=(x[k]- x[k + N / 21WN-0 x2[k]x[k+N/2]0蝶形图éx[klu éwox[k]O üél1 uéur,[k1i"we le1-1x[k + N / 210

基2频率抽取FFT算法原理 长序列分解为两个短序列 蝶形图

基2频率抽取FFT算法原理如何利用基2频率抽取FFT计算8点序列的DFT?8点时域序列分解为2个4点时域1每个4点时域序列，再分解为2个2点时域序列电通过2点序列DFT将时域变换到频域1两点序列的DFT x[k]=(x[O],x[1]]éX[O]uél uéx[O]u

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

基2频率抽取FFT算法原理长序列x[k]分解为两组短序列xi[k]和x2[k]ewox[k]éx,[k]uuo ul1 téeeex,[k-11x[k + N / 218Aa0时域到频域éX[0]uiex[o]uBx[11- 118x[11

基2频率抽取FFT算法原理 长序列x[k]分解为两组短序列x1 [k]和x2 [k] -1 1 时域到频域

x,[k] = (x[kl+ x[k + N / 2]WN:x,[k]=(x[k]- x[k + N /2]WN第二级第三级第一级xi[0]X[0]. XTO]x[0] .2点xi[1]xu[1]DFT. X[4]x[1]1xi[2]X12[0].X[2]x[2] 2点01Wx12lxi[3]DFT.X[6]x[3] 1x2[0]X2i[0].X[1]x[4] 2点1DFTx2[1]X2i[1].X[5]x[5]°/1x2[2]X22[0].X[3]x[6]:2点1W2x2[3]DFT-x22[1].X[7]Yx[7]°口1

第一级 第二级 第三级

例：已知x[k]=[1,2,3,4}利用基2频率抽取流图，计算X]m]-DFT(x[k]} 。x[0]10XT01X[2]2x[1]-2+2jX[11x[2]2j-2-2jX[3]DFT(x[k]}=(10, -2+2j, -2, -2-2j)

例：已知x[k]={1,2,3,4}利用基2频率抽取流图，计算 X[m]=DFT{x[k]}。 1 2 3 4 4 -2 6 2j 10 -2 -2+2j -2-2j DFT{x[k]}={10, -2+2j，-2, -2-2j}

总结基2频率抽取FFT算法基本原理时域上将序列按照前后部分组合的方式分解为两个子序列，根据2点序列DFT计算将时域变换到频域，再由短序列的DFT合成得到长序列的DFT（分别对应长序列DFT的奇偶）。时域分解与频域合成：X[2m] = X[m]éx,[kluéwouex[k]O uélue:e8x,[k18W81 -1x[k + N / 210X[2m +1]= X2[m]

总结 基2频率抽取FFT算法基本原理： 时域上将序列按照前后部分组合的方式分解为两个子序列，根 据2点序列DFT计算将时域变换到频域，再由短序列的DFT合成 得到长序列的DFT（分别对应长序列DFT的奇偶）。 时域分解与频域合成：

总结基2频率抽取FFT算法流图：x[0]XTO1x[1]X[2]x[2]X[1]x[3]X[3]NN.M复数加法：复数乘法：2'M=Nlog,N109222

总结 基2频率抽取FFT算法流图： 复数乘法： 复数加法：