利用上述特性,可以将有些项合并,并 将DFT分解为短序列,从而降低运算次数,提 高运算速度.1965年,库利( cooley)和图基 ( Tukey)首先提出FFT算法对于N点DFT,仅需 (N/2)1og2N次复数乘法运算例如N=1024-210时, 需要(1024/2)log2210=512*10=5120次。 5120/1048576=4.88%,速度提高20倍
利用上述特性,可以将有些项合并,并 将DFT分解为短序列,从而降低运算次数,提 高运算速度.1965年,库利(cooley)和图基 (Tukey)首先提出FFT算法.对于N点DFT,仅需 (N/2)log2N 次复数乘法运算.例如N=1024=2 10 时， 需要(1024/2)log2 2 10 =512*10=5120次。 5120/1048576=4.88% ,速度提高20倍
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)
X(k)=∑x(n)W+∑x(n)W n=0(为偶数)n=0(n为奇数) ∑x(2)W2+∑x(2r+1)W21 r=0 ∑x1()(W3)+W∑x2()WR2) 0 r=0 由子 e 所以,上式可表示为 X()=∑()W+∑2()=x1(k)+Nx2(k)
由于: 所以,上式可表示为: 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 rk N k N r rk N r r k N r rk N N n N n nk N nk 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 rk N r rk N N N N
X1(k)=∑x()W=∑x(2)W 其中 X2()∑x2()W=∑x2r+m 0 r=0 2.两点结论 (1)X1(k),X2(k)均为N/2点的DFT。 (2)X(k)=X1(k)+WX2(k)只能确定出 X()的k=0,…,y-1个; 即前一半的结果
其中, 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 rk r rk r rk r rk X k x r W x r W X k x r W x r W 0,1, , 1 2 N
3.x()的后一半的确定 由于W, r(k+) =W(周期性),所以: X1(+k) ∑ x()W1(+) ∑x(W=X() r=0 同理,X N+k)=x2(k) 这就是说,H(k),2(从)的后一半,分别 等于其前一半的值
同理, 这就是说,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 rk r 由于 （周期性）,所以: ) ( ) 2 ( 2 2 k X k N X