86 Fast Fourier Transform 例 8,计算C1=∑xW,j=0,1,2,3,4,5,6, 技巧:将k,i生 ary numbers */ 般地:取N=2, HW: 每个C用2p次乘法,共用 138#1 2Nlog2N次乘法。 利用Wh2=(-)y,还可以进x2)+(2k 一步化简到N(p-1)/2次乘法。 k0=0k1=0k2=0 A0(k2k1k0) A302j,jo) A,(h, kojo) 2×3次乘 Ani)全部计算需要2×3x8次乘法 法§6 Fast Fourier Transform 例：N = 23 = 8, 计算  ， j = 0, 1, 2, 3, 4, 5, 6, 7   7 k 0 j k C j x kW 技巧：将 k , j 先记为二进制数 /* binary numbers */               2 2 2 ( ) 2 2 2 ( ) 2 1 0 0 0 1 1 2 2 2 1 0 0 0 1 1 2 2 j j j j j j j k k k k k k k j k W ( 2 2 2 ) ( 2 2 2 ) 0 0 1 1 2 2 0 0 1 1 2 2            j j j k k k W ( 2 2 2 ) ( 2 2 2 ) ( ) 0 2 1 0 1 0 2 1 3 1 2 2 0 3 1 4 j2 k2 k k j k k k j k k k W              ( 0 0) ( 0) ( ) 2 0 1 1 0 0 k2 k1 k0 j k j k k j W                         1 0 ( 00) 1 0 ( 0) 1 0 ( ) ( ) ( ) 0 2 0 1 1 1 0 2 0 2 1 0 2 1 0 2 1 0 k j k k j k k k j k k k C j j j x k k k W W W ( ) A0 k2k1k0 ( ) 1 1 0 0 A k k j ( ) 2 0 1 0 A k j j ( ) 3 2 1 0 A j j j 23次乘 法 全部计算需要23 8次乘法 一般地：取 N = 2p， 每个Cj 用 2p 次乘法，共用 2N log2N 次乘法。 利用 ，还可以进 一步化简到 N(p1)/2 次乘法。 0 1 0 ( 1) j 2 j p W    HW: p.138 #1