(+k 又由于WN2 WW=-W6,所以 N N X(k+-)=X1(k+-)+WN2X2(k+ 2 X()-WNX2(k)k=01…-1 可见,X(k)的后一半,也完全由x1k), X2(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,蝶形运算 冉X/、K2/k表示的运算是一种特殊的运算-碟形运算 X()=X1()+WX2(k)葡一半(k=0,,号-D X(k)=X1(k)-WX2(k)后一半k=豐,…,N-1) 实现上式运算的流图称作蝶形运算(N/2个蝶形 X1(k) 11X(k)=X1()+WxX2(k)(前一半) W-1x(+8)=x()-形x)(后一半)
实现上式运算的流图称作蝶形运算 前一半 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点的DT运算量:复乘次数:(2)2=4 复加次数:(-1) (2)两个N/2点的D运算量:复乘次数:N2 复加次数:N(2=D) (3)N/2个蝶形运算的运算量:复乘次数 复加次数: N-N 总共运算量:复乘:N2+N=N2 复加:2-1)+N=x2 *但是,N点DFT的复乘为N;复加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)x(2),x(4),x(6); 分别记作:x1(O)=x(O x1(1)=x(2) x1(2)=X(4) x1(3)=x(6) 进行N2=4点的DF,得X1(k) X(k)=∑x()W=∑x(2)W r=0 k=0,1,2,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为奇数时,分别记作: (0)=x(1) (1)=x(3)2 x2(2)=x(5) x2(3)=x(7) 进行N2=4点的DFT,得X2(k) X2(k)=∑x2(4=∑x(2r+1)W4 k=0.1.2.3 X(k)=X(h)+WrX,(k) A7(+4)=x1()-Wx2(6,=0.23
(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