又由于W+)==一,所以 X(k+N)=X1(+x)+W*X21h+ N N X1(k)-WN2(k),k=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.蝶形运算 車κ(、2(k表示κ的运算是一种特殊的运算碟形运算 X(k)=X1(k)+X2(k)前一半(=0.,…-1 K(k)=X1(k)-WX2(k)后一半(k=号,…,N-1 实现上式运算的流图称作蝶形运算(N2个蝶形) XI(k 1X(k)=X1(k)+WX2(k)(前一半) 1X(+6)=X1(k)-WXk)(后一半)
实现上式运算的流图称作蝶形运算 前一半 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)、X 2(k)表示X(k)的运算是一种特殊的运算-碟形运算
5.计算工作量分析 按奇、偶分组后的计算量: N/2点的DFT运算量:复乘次数: 4 复加次数: (2)两个N/2点的DF运算量:复乘次数:N2 复加次数 (3)N/2个蝶形运算的运算量:复乘次数:N 复加次数 N-N 共运算量:复乘: N N 复加:NN N *但是,N点DFT的复乘为N2;复加NN-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 2 2 N N N 总共运算量 : 按奇、偶分组后的计算量： *但是,N点DFT的复乘为N2 ;复加N(N-1);与 分解后相比可知,计算工作点差不多减少 一半
例如N=8时的DFT,可以分解为两个 N/2=4点的DFT.具体方法如下: (1)n为偶数时,即x(0)x(2)2x(4),x(6) 分别记作:x1(0)=x(0 (2 (2)=x(4 ))) 进行N/2=4点的DFT,得1(k) X()=∑x()=∑(27)水 k=0,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 rk r rk ( 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) (1 xxxx ((( 3) (2) 5) 进行N/2=4点的DFT,得X2(k) X2(k)=∑x2()W4=∑x(2r+1)W4 k=0,1,2,3 X(k)=X,()+WNX,(h) (k+4)=x1(k)-WNX2(),k=0,1,2,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 rk r rk / 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