基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,1N / 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