In deriving formulas tor the noise-to-signal ratio for the fixed-point radix-2 decimation-in-time FFT algorithm, we assumed that each output node was connected to (N ? 1) butterfly computations, each of which contributed an amount ?²_B = 1/3. 2^?2B to the output noise variance However, when W^r_N = ? 1 or ? j, the multiplications can in fact be done without error. Thus, if the results derived in Section 9.7 are modified to account for this fact, we obtain a less pessimistic estimate of quantization noise effects.

(a) For the decimation-in-time algorithm discussed in Section 9.7, determine, for each stage, the number of butterflies that involve multiplication by either ? 1 or ? j.

(b) Use the result of part (a) to find improved estimates of the output noise variance, Eq. (9.55), and noise-to-signal ratio, Eq. (9.65), for odd values of k. Discuss how these estimates are different for even values of k. Do not attempt to find a closed form expression of these quantities for even values of k.

(c) Repeat part (a) and (b) for the case where the output of each stage is attenuated by a factor of ?; i.e., derive modified expressions corresponding to Eq. (9.68) for the output noise variance and Eq. (9.69) for the output noise-to-signal ratio, assuming that multiplications by ? 1 and ? j do not introduce error.

(9.55) E||F[k]*} = (N 1)o, E|| F [k]l*} E{|X[k]|3} = 3N0; = N2 28 (9.65) E{\F[k]l} = 40 = - 2-28, E || F[k]l*} E{|X[k]?} 4.2-2B, (9.68) (9.69) 12 No = 4N - 2-2B.