利用上述特性,可以将有些项合并,并 将DFT分解为短序列,从而降低运算次数,提 高运算速度.1965年,库利( cooley)和图基 ( Tukey)首先提出FFT算法对于N点DFT,仅需 (N/2)1og2N次复数乘法运算.例如N=1024-210时, 需要(1024/2)10g2210=512*10=5120次。 5120/1048576=4.88%,速度提高20倍
利用上述特性,可以将有些项合并,并 将DFT分解为短序列,从而降低运算次数,提 高运算速度.1965年,库利(cooley)和图基 (Tukey)首先提出FFT算法.对于N点DFT,仅需 (N/2)log2N 次复数乘法运算.例如N=1024=210 时， 需要(1024/2)log2 2 10 =512*10=5120次。 5120/1048576=4.88% ,速度提高20倍
§4-2换时间抽取(DT)的FF算法 一库利一图基算法 算法原理(基2FFT) (-)N/2点DFT 1.先将x(n)按n的奇偶分为两组作DFT,设N=2, 不足时,可补些零。这样有: n为偶数时:x(2r)=x1(T),r=0.1…,2-1 n为奇数时:x(2-+1)=x2(),r=01,…,-1 因此,X(k)=DFT[x(m)=∑x(n)Wx
§4-2 按时间抽取(DIT)的FFT算法 —库利-图基算法 一.算法原理(基2FFT) (一)N/2点DFT 1.先将 按n的奇偶分为两组作DFT,设N=2L , 不足时,可补些零。这样有: 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 n k WN 因此， X k DFT x n x n x(n)
X(k)=∑x(n)W+∑x(n)WM n=0(n为偶数)n=0(n为奇数) ∑x(2n)W3+∑x(2r+1)W21 (r)(W) k +w k ∑x2(m)(WN)y k N 2兀 由于:Wk=e j2() W 所以,上式可表示为 (6)=∑x(W+w∑x2(W=X()+W含X2(k) =0
由于: 所以,上式可表示为: − = − = − = + − = − = − = = + = + + = + 1 0 2 2 1 0 2 1 1 0 (2 1) 1 0 2 1 0 1 0 2 2 2 2 ( )( ) ( )( ) (2 ) (2 1) ( ) ( ) ( ) N N N N r r k N k N r r k N r r k N r r k N N n N n n k N n k N x r W W x r W x r W x r W X k x n W x n W (n为偶数) (n为奇数) 2 2 2 2 2 2 / ( ) N N W e N e W j j N = = = − − ( ) ( ) ( ) ( ) ( ) 1 2 1 0 2 1 0 1 2 2 2 2 X k x r W W x r W X k W X k k N r k r k N r r k N N N = N + = + − = − =
XI(k X,(rwA rk x(2r)WA k 其中 X2)=∑x2(W=∑x(+1) 0 2.两点结论 (1)X1(k),X2(k)均为N/2点的DFT (2)X(k)=X1(k)+kX2(k)只能确定出 Ⅹ(k)的k=0.1 A即一半的结排
其中, 2.两点结论: (1) X (k),X (k)均为N/2点的DFT。 (2) X(k)=X (k)+W X (k)只能确定出 X(k)的k= 个； 即前一半的结果。 1 2 1 2 k N − = − = − = − = = = + = = 1 0 1 0 2 2 1 0 1 0 1 1 2 2 2 2 2 2 2 2 ( ) ( ) (2 1) ( ) ( ) (2 ) N N N N N N N N r r k r r k r r k r r k X k x r W x r W X k x r W x r W 0,1, , 1 2 − N
3.X(k)的后一半的确定 r(k+ 由于V =W(周期性),所以 XG+k) r(2+k) X,(r)WA k N XI(k =0 同理y +k)=X2(k) 这就是说,(k,2(k)的后一半,分别 等于其前一半的值
同理, 这就是说,X1(k),X2(k)的后一半,分别 等于其前一半的值。 3.X(k)的后一半的确定 r k rk N N WN W 2 2 2 ( ) = + ) ( ) ( ) ( ) 2 ( 1 1 0 1 ( ) 1 0 1 1 2 2 2 2 2 k x r W x r W X k N X N N N N N r r k r k r + = = = − = + − = 由于 （周期性）,所以: ) ( ) 2 ( 2 2 k X k N X + =