算法 解令W=eN,则k为整数时,W=W。假设 j=jq+j,方=0 l,j=0,1,…q-1, n=nP+n,n1=0,1,…,q-1,n=0,1,…,P-1。 X()=2xex以=∑x(mWm ∑xp+n)W W∑x(nP+n形 nJop 固定,计算xnp+mW需要q-1次乘法(n=0不需要做乘 法,对于相同的,∑x(mP+n1M是相同的,无需重复计算,所 有此类和式共需q(q-1)次乘法。对m求和需要(p-1)N次乘法,所以, 总共需要q(q-1)+(p-1)N=O(p+q)N)次乘法。 4.对N=23,具体写出以2为底的FFT的计算流程。 解记W=e8=e4,则W4=-1,W8=1。可得计算公式 X()=∑x(mWm,j=0,1…7 =[x(0)+(-1)x(4)+W[x(1)+(-1)x(5) +2/{[x(2)+(-1)yx(6)+W[x(3)+(-1)yx(7)]}。 计算流程 第一步: x1()=x(1)+x(+4) x1(+4)=W[x()-x(+4)]i=0,1,2,3算法。 解 令 2 e i W N π − = ，则k 为整数时，W kN +n = W n 。假设 1 0 1 0 j j = +q j , 0 j = ,1," " , p −1, j = 0,1, , q −1, 1 0 1 0 n n = + p n , n = 0,1," " , q −1, n = 0,1, , p −1。 X j x n i n j N n N ( ) = ( ) e − = − ∑ 2 0 1 π 1 0 ( ) N jn n x n W − = = ∑ 1 0 0 1 1 1 ( ) 1 0 0 0 ( ) p q j n p n n n x n p n W − − + = = = + ∑ ∑ 0 1 0 1 1 1 1 0 0 0 ( ) p q jn n j p n n W x n p n W − − = = = + ∑ ∑ 0 。 固定 j ，计算 1 0 需要 1 1 1 0 0 ( ) q n j p n x n p n W − = ∑ + q −1次乘法（ 1 n = 0不需要做乘 法），对于相同的 ， 是相同的，无需重复计算，所 有此类和式共需 次乘法。对 求和需要 0 j 1 0 1 1 1 0 0 ( ) q n j p n x n p n W − = ∑ + q q( −1) 0 n ( p −1)N 次乘法，所以， 总共需要q q( 1− +) ( p −1)N = O(( p + q)N) 次乘法。 4． 对 N = 23，具体写出以 2 为底的 FFT 的计算流程。 解 记 2 8 4 e e i i W π π − − = = ，则 4 8 W = −1,W =1。可得计算公式 7 0 ( ) ( ) , 0,1, ,7. jn n X j x n W j = = = ∑ " [ (0) ( 1) (4)] [ (1) ( 1) (5)] j j j = + x x − +W x + − x 2 {[ (2) ( 1) (6)] [ (3) ( 1) (7)]} j j j j + + W x − x +W x + − x 。 . 计算流程 第一步： 1 1 ( ) ( ) ( 4), ( 4) [ ( ) ( 4)], 0,1, 2,3 i x i x i x i x i W x i x i i = + + + = − + = 4