9.2 decimation-in-time FFT Algorithms DIT flow graph for 8-point decimation in time x0] XO] N=8=23 we generalized to x[4] X[1] w N=2m x[2] X[2] w m=1og2N x[6]o- W W x 1 X[4] m级：每级乘法 和加法个数为N WOWWB2-WN x[3] 6X[6 Complexity: x S-x17I Nlog2N complex multiplications and Nlog2N additions Nm Nm D?22 9.2 decimation-in-time FFT Algorithms ◆DIT flow graph for 8-point decimation in time ◆Complexity: Nlog2N complex multiplications and Nlog2N additions 2 WN 0 WN 4 WN 6 WN N=2m m=log2N N=8=23 3 WN 7 WN generalized to m级: 每级乘法 和加法个数为N 3 /2 N =W WN N 2 /2 N W WN N = 0 WN 0 4 / 2= N N W W NWN Nm Nm