In implementing a decimation-in-time FFT algorithm, the basic butterfly computation is X m [p] = X m-1
Question:
In implementing a decimation-in-time FFT algorithm, the basic butterfly computation is Xm[p] = Xm-1[p] + /WrN Xm-1[q], Xm[q] = Xm-1[p] – WrN Xm-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 | Xm-1[p] | < ½ and | Xm-1[q] | < ½, then overflow cannot occur in the butterfly computation; i.e., | Re{Xm [p]} | < 1, | Jm{Xm [p]} | < 1, and | Re{Xm[q]} | < 1, |Jm{Xm [q]} | < 1.
(b) In practice, it is easier and most convenient to require | Re{Xm-1[p]} | < ½, | Jm{Xm-1 [p]}| < ½, and | Re{Xm-1 [q]} | < ½, | Jm{Xm-1 [q]}| < ½. Are these conditions sufficient to guarantee that overflow cannot occur in the decimation-in-time butterfly computation? Explain.
Step by Step Answer:
Discrete Time Signal Processing
ISBN: 978-0137549207
2nd Edition
Authors: Alan V. Oppenheim, Rolan W. Schafer