又由于W(+)=WW=W,所以 X(k+x)=X1(k+)+WN22(+M X1(k)-WNX2(k)2k=0,1 可见,X(k)的后一半,也完全由X1(k), Ⅹ2(k)的前一半所确定。 N点的DFT可由两个N/2点的DFT来计
可见,X(k)的后一半，也完全由X1(k), X2 (k)的前一半所确定。 *N点的DFT可由两个N/2点的DFT来计 算。 k N k N N k WN W W W N N = = − +2 2 ( ) ) 2 ) ( 2 ) ( 2 ( 1 2 2 N W X k N X k N X k N k + = + + N + + ( ) ( ), 0,1, , 1 1 2 2 = − = − k N N X k W X k k 又由于 ,所以
4.蝶形远算 κ、K21)表示X的运算是一种特殊的运算-碟形运算 X(k)=X1(k)+WX2()前一半(k=0.,…号-1 X(k)=X1(k)-WX()后一半(k=學,,N-1) 实现上式运算的流图称作蝶形运算(N2个蝶形) x1(k) 1X(k)=X1(k)+WX2(k)(前一半) X2(k Wk-1X(2+)=X(k)-W2(k)(后一半)
实现上式运算的流图称作蝶形运算 前一半 4.蝶形运算 后一半 （N/2个蝶形) (前一半) (后一半) 1 1 1 1 -1 ( ) ( ) ( ) ( ) ( ) ( ) 1 2 1 2 X k X k W X k X k X k W X k k N k N = − = + ( , , 1) ( 0,1, , 1) 2 2 = − = − k N k N N ( ) ( ) ( ) 1 2 X k X k W X k k = + N ) ( ) ( ) 2 ( 1 2 k X k W X k N X k + = − N ( ) 1 X k ( ) 2 X k k WN 由X1 (k)、X2 (k)表示X(k)的运算是一种特殊的运算-碟形运算
5.计算工作量分析 按奇、偶分组后的计算量: N/2点的DF运算量:复乘次数:(2) 复加次数:^ (2)两个N/2点的DFT运算量:复乘次数:N 复加次数:N(2- (3)N/2个蝶形运算的运算量:复乘次数 复加次数:2.N=N 总共运算量:复乘:N2+N 复加:NN-1)+N=N *但是,N点DFT的复乘为N2;复加N(N-1);与 分解后相比可知,计算工作点差不多减少一半
(1)N/2点的DFT运算量:复乘次数: 复加次数: (2)两个N/2点的DFT运算量:复乘次数: 复加次数: (3)N/2个蝶形运算的运算量:复乘次数: 复加次数: 5.计算工作量分析 复乘: 复加: 4 ) 2 ( 2 N 2 N = 1) 2 ( 2 − N N 2 2 N 1) 2 ( − N N 2 N N N = 2 2 2 1) 2 ( 2 N N N N − + = 2 2 2 N 2 N N 2 总共运算量 + : 按奇、偶分组后的计算量： *但是,N点DFT的复乘为N 2 ;复加N(N-1);与 分解后相比可知,计算工作点差不多减少一半
例如N=8时的DFT,可以分解为两个 N/2=4点的DFT.具体方法如下 (1)n为偶数时,即x(O)2x(2),x(4),x(6); 分别记作:x1(O)=x(O) x1(1)=x(2), x1(2)=x(42 x1(3)=X(O; 进行N/2=4点的DF7,得X(k) X1(k)=∑x()W=∑x27)W k=0,12,3
例如 N=8 时的DFT,可以分解为两个 N/2=4点的DFT.具体方法如下: (1)n为偶数时,即 分别记作: / 2 4 ( ) 1 进行N = 点的DFT，得X k 0,1,2,3 ( ) ( ) (2 ) 3 0 4 3 0 1 1 4 = = = = = k X k x r W x r W r r k r r k (3) (6); (2) (4), (1) (2), (0) (0), 1 1 1 1 x x x x x x x x = = = = x(0), x(2), x(4), x(6);
2)n为奇数时,分别记作: (O)=x(1) (1)=x(3) (2)=X(5) x2(3)=x(7) 进行N/2=4点的DF7,得X2(k) X2(k)=∑x(O)形4=∑x(2r+1)4 k=0.1.2.3 X(k)=X1()+W2(k) AX(+4)=X(k)-WA2().=01.3
(2) n为奇数时,分别记作: (3) (7); (2) (5), (1) (3), (0) (1), 2 2 2 2 x x x x x x x x = = = = 0,1,2,3 ( ) ( ) (2 1) 3 0 4 3 0 2 2 4 = = = + = = k X k x r W x r W r r k r r k / 2 4 ( ) 2 进行N = 点的DFT，得X k ( 4) ( ) ( ), 0,1,2,3 ( ) ( ) ( ) 1 2 1 2 + = − = = + X k X k W X k k X k X k W X k k N k N