《数字信号处理》课程教学课件（PPT讲稿）ch3_2 频率抽取FFT

基2频率抽取FFT算法N/2-1N-1Zx[k]Wukx[kWmkXIml=?k=0k=N/2N/2-1N/2-1ZZx[k + N / 2]Wm(k+N/2)X[k]Wmk+一NNk=0k=0N/2-1Z(x[k]+(-1)" x[k + N /2)W*-k=0N/2-12 (x[k]+ x[k + N /2)WN/2X[2r] =k=0N/2-1Z(x[k]- x[k + N / 2])WWN/2X[2r +1] =k=02025/7/2崔丽珍通信与电子信息系

2025/7/2 通信与电子信息系 崔丽珍 基2频率抽取FFT算法 mk N N k N mk N N k X[m] x[k]W x[k]W 1 / 2 / 2 1 0   − = − = = + ( / 2) / 2 1 0 / 2 1 0 [ ] [ / 2] m k N N N k mk N N k x k W x k N W + − = − = =  +  + ( ) mk N m N k x[k] ( 1) x[k N / 2] W / 2 1 0 =  + − + − = ( ) r k N N k X r x k x k N W / 2 / 2 1 0 [2 ] =  [ ]+ [ + / 2] − = ( ) r k N k N N k X r x k x k N W W / 2 / 2 1 0 [2 +1] =  [ ]− [ + / 2] − =

N/2-1(x[K)+ x[k+ N /2)W/2Zr = 0,1...N/2-1X[2r] =k=0N/2-1Z(x[k]-x[k+ N /2])WkWn/2X[2r +1] =k=0x[0]X[0]x[1]X[2]4点DFTx[2]X[4]x[3]X[6]Wx[4]X[1]Wx[5]X[3]4点WADFTx[6]X[5]W202[7/2X[7]-1丽珍通信与电

2025/7/2 通信与电子信息系 崔丽珍 ( ) r k N Nk X r x k x k N W / 2 / 2 1 0 [2 ] =  [ ]+ [ + / 2] − = ( ) r k N kN Nk X r x k x k N W W / 2 / 2 1 0 [2 +1] =  [ ]− [ + / 2] − = r = 0,1N / 2 − 1 3 WN - 1 2 WN - 1 1 WN - 1 0 WN - 1 x[0] x[4] x[1] x[5] x[2] x[6] x[3] x[7] 4 点 DFT X[0] X[6] X[2] X[4] 4 点 DFT X[1] X[3] X[5] X[7]

x[0]X[0]一2点DFT一X[4]x[1]Wx[2]X[2]--12点WDFTx[3]X[6]一-1Wx[4]X[1]2点WDFTx[5]X[5]一WWx[6]X[3]12点-1/-1WWDFTx[7]一 X[7]-1-1崔丽珍2025/7/2通信与电子信息系

2025/7/2 通信与电子信息系 崔丽珍 X[0] X[6] X[4] X[2] X[1] X[5] X[3] X[7] 0 WN1 WN2 WN3 WN - 1 - 1 - 1 - 1 x[0] x[3] x[1] x[2] x[4] x[5] x[6] x[7] 0 WN2 WN 2 点 DFT - 1 - 1 2 WN0 WN - 1 - 1 2 点 DFT 2点 DFT 2点 DFT

x[0]X[0]一Wx[1]X[4]-1Wx[2]X[2]-1WWx[3]X[6]-1-1Wx[4]X[1]1WWx[5]X[5]-1WWx[6]X[3]一-1-1/WWWYx[7]X[7]-1-1-1崔丽珍2025/7/2通信与电子信息系

2025/7/2 通信与电子信息系 崔丽珍 0 WN1 WN2 WN3 WN -1-1-1-1 x[0] x[3] x[1] x[2] x[4] x[5] x[6] x[7] 0 WN2 WN2 WN0 WN X[0] X[6] X[4] X[2] X[1] X[5] X[3] X[7] 0 WN0 WN0 WN0 WN - 1- 1 - 1 - 1 - 1 - 1 - 1 - 1

FFT算法应用利用N点复序列的FFT计算两个N点实序列FFT■利用N点复序列的FFT，计算2N点序列的FFT利用FFT计算IFFT崔丽珍2025/7/2通信与电子信息系

2025/7/2 通信与电子信息系 崔丽珍 FFT算法应用 ◼ 利用N点复序列的FFT计算两个N点实序列FFT ◼ 利用N点复序列的FFT，计算2N点序列的FFT ◼ 利用FFT计算IFFT

利用N点复序列的FFT算法计算两个N点实序列FFTxi[k],x2[k]是实序列,DFTx[A]=?将其构成复序列y[k]=xi[k]+j x2[kDFTx[K]=?DFT(xi[K]+j x2[K]}=YR [m]+jY, [m]DFT(xi[K] - jx2[k]}= Yr[(-m)]- jY,[(-m) ]DFT(x[K])=(YR[m) + YR[(-m)n ]+ j(Y,[m] -Y,[(-m) ~ D)(Yr[m] -Yr[(-m)~ ] + j(Y,[m]+ Y,[(-m)~ D)DFT(x2[k]]=一0221

2025/7/2 通信与电子信息系 崔丽珍 利用N点复序列的FFT算法计算 两个N点实序列FFT x1 [k], x2 [k]是实序列， 将其构成复序列y[k]=x1 [k]+j x2 [k] DFT{x1 [k]+j x2 [k]}=YR [m]+jYI [m]  [ ] ? DFT x1 k =  [ ] ? DFT x2 k = DFTx1 [k]− jx2 [k]= [( ) ] [( ) ] R N I m N Y −m − jY −    [ ] [( ) ] ( [ ] [( ) ]) 2 1 [ ] 1 R R N YI m YI m N DFT x k = Y m + Y −m + j − −    [ ] [( ) ] ( [ ] [( ) ]) 2 1 [ ] 2 R R N YI m YI m N Y m Y m j j DFT x k = − − + + −

利用N点复序列的FFT，计算2N点序列的FFTy[K]是一个长度为2N的序列xi[k] = y[2k][k] -→k=0.1...N-1X2[k] = [2k + 1]Y[m]=X,[m]+W2MX,[m]m=0,1,....N-1Y[m+N]=X[m]-W2X2[m]问题：如何利用N点FFT，计算4N点序列的FFT？崔丽珍2025/7/2通信与电子信息系

2025/7/2 通信与电子信息系 崔丽珍 利用N点复序列的FFT，计算2N点序列的FFT y[k]是一个长度为2N的序列 0,1, 1 [ ] [2 1] [ ] [2 ] [ ] 2 1 = −    = + = → k N x k y k x k y k y k  0,1, , 1 [ ] [ ] [ ] [ ] [ ] [ ] 1 2 2 1 2 2 = − + = − = + m N Y m N X m W X m Y m X m W X m m N m N  问题：如何利用N点FFT，计算4N点序列的FFT？

利用FFT实现IFFTX[m] = DFT (x[k])=lx[k]Wmkk=01-NX[m]W"mkx[k] = IDFT(X[m]]:2X"[m]Wwkx[k] =Nm=0步骤：A】将X[m]取共轭B）用FFT流图计算DFT(X*[m]C）对B)中结果取共轭并除以N2025/7/2通信与电子信息系崔丽珍

2025/7/2 通信与电子信息系 崔丽珍 利用FFT实现IFFT   m k N N k X[m] DFT x[k] x[k]W 1 0  − = = =   m k N N m X m W N x k IDFT X m − − = = =  [ ] 1 [ ] [ ] 1 0   − =         =  m k N N m X m W N x k [ ] 1 [ ] 1 0 步骤：A) 将X [m]取共轭 B) FFT DFT{X [m]} 用 流图计算  C) 对B)中结果取共轭并除以N