DFT算法存在的问题 改进办法: 1.旋转因子WW的对称性和周期性 (1)对称性:W+N2)=-W (2)周期性:W+Nn=W=W(+N (3)可约性:W=Wm=WWm 例:求当N=4时,X(2)的值 X(2)=∑x(m)W2n=xOW4+x(1)42+x(2)W4+x(3)W [x(O)+x(2W4+[x(1)+x(3)J2(周期性) [x(O)+x(2)[x(1)+x(3)}W4(对称性) 通过合并,使乘法次数由4次减少到1次,运算量减少。DFT算法存在的问题 ➢改进办法： 1. 旋转因子 WN m 的对称性和周期性 例：求当N＝4时，X(2)的值 （1) 对称性： （2) 周期性： k N k N WN = −W ( + / 2) n N k N kn N k N n WN W W ( + ) ( + ) = = {[ (0) (2)] [ (1) (3)]} ( ) [ (0) (2)] [ (1) (3)] ( ) (2) ( ) (0) (1) (2) (3) 0 4 2 4 0 4 6 4 4 4 2 4 0 4 3 0 2 4 ＝ － 对称性 周期性 x x x x W x x W x x W X x n W x W x W x W x W n n + + = + + + =  = + + + = 通过合并，使乘法次数由4次减少到1次，运算量减少。 kn m N m mkn mN kn WN W W / （3)可约性: = = / • • • • 0 WN 2 N WN k WN k −WN k N 2 0