In implementing a decimation-in-time FFT algorithm, the basic butterfly computation is X_m[p] = X_m-1[p] + /W^r_N X_m-1[q], X_m[q] = X_m-1[p] – W^r_N X_m-1[q]. In using fixed-point arithmetic to implement the computations, it is commonly assumed that all numbers are scaled to be less than unity. Therefore, to avoid overflow, it is necessary to ensure that the real numbers that result from the butterfly computations do not exceed unity.

(a) Show that if we require | X_m-1[p] | < ½ and | X_m-1[q] | < ½, then overflow cannot occur in the butterfly computation; i.e., | Re{X_m [p]} | < 1, | Jm{X_m [p]} | < 1, and | Re{X_m[q]} | < 1, |Jm{X_m [q]} | < 1.

(b) In practice, it is easier and most convenient to require | Re{X_m-1[p]} | < ½, | Jm{X_m-1 [p]}| < ½, and | Re{X_m-1 [q]} | < ½, | Jm{X_m-1 [q]}| < ½. Are these conditions sufficient to guarantee that overflow cannot occur in the decimation-in-time butterfly computation? Explain.