9.2.1 Generalization and Programming the FFT Final flow graph for 8-point decimation in time N=8=23 x[0]o* XO] generalized to N=2m x[40* X1 m=log2N x2]o* 2X[2] m级：每级乘法 NW2个，加法N个x[ X[3] x[10 X[4] We x[5)o9 the figure serves as x[3]o* X[6 proof for WS x[7]00 Complexity: -1 (Nlog2N)/2 complex multiplications and Nlog2N additions 5 mN/2 mN25 9.2.1 Generalization and Programming the FFT ◆Final flow graph for 8-point decimation in time Complexity: (Nlog2N)/2 complex multiplications and Nlog2N additions 2 WN 0 WN 4 WN 6 WN N=2m m=log2N N=8=23 2 WN 6 WN 2 WN 0 WN 2 WN generalized to the figure serves as proof for -1 -1 -1 m级: 每级乘法 N/2个,加法N个 乘法运算量 直接计算乘法量 ) ) mN/2 mN N=210