7§4-2按时间抽取(IT)的FFT算法 库利-图基算法 算法原理(基2FFT) (一)N/2点DFT 1.先将x(n)按n的奇偶分为两组作DFT,设N=2L, 不足时,可补些零。这样有: n为偶数时:x(2r)=x()2r=01…y n为奇数时:x(2-+1)=x2(r),r=0,1…,y-1 因此,X()=DFx(m)=∑x(n)§4-2 按时间抽取(DIT)的FFT算法 —库利-图基算法 一.算法原理(基2FFT) (一)N/2点DFT 1.先将 按n的奇偶分为两组作DFT,设N=2 L , 不足时,可补些零。这样有: n为偶数时: n为奇数时: (2 1) ( ), 0,1, , 1 (2 ) ( ), 0,1, , 1 2 2 1 2        N N x r x r r x r x r r       1 0 ( ) [ ( )] ( ) N n nk n WN 因此，X k DFT x n x x(n)