In Section 9.3.2, it was asserted that the transpose of the flow graph of an FFT algorit...

In Section 9.3.2, it was asserted that the transpose of the flow graph of an FFT algorithm is also the flow graph of an FFT algorithm. The purpose of this problem is to develop that result for radix-2 FFT algorithms.

(a) The basic butterfly for the decimation-in-frequency radix-2 FFT algorithm is depicted in Figure P9.31-1. This flow graph represents the equations

Starting with these equations, show that X_m−1[p] and X_m−1[q] can be computed from X_m[p] and X_m[q], respectively, using the butterfly shown in Figure P9.31-2.

b) In the decimation-in-frequency algorithm of Figure 9.22, X_ν[r], r = 0, 1, . . . , N − 1 is the DFT X[k] arranged in bit-reversed order, and X₀[r] = x[r], r = 0, 1, . . . , N − 1; i.e., the zeroth array is the input sequence arranged in normal order. If each butterfly in Figure 9.22 is replaced by the appropriate butterfly of the form of Figure P9.31, the result would be a flow graph for computing the sequence x[n] (in normal order) from the DFT X[k] (in bit-reversed order). Draw the resulting flow graph for N = 8.

(c) The flow graph obtained in part (b) represents an inverse DFT algorithm, i.e., an algorithm for computing

Modify the flow graph obtained in part (b) so that it computes the DFT

rather than the inverse DFT.

(d) Observe that the result in part (c) is the transpose of the decimation-in-frequency algorithm of Figure 9.22 and that it is identical to the decimation-in-time algorithm depicted in Figure 9.11. Does it follow that, to each decimation-in-time algorithm (e.g., Figures 9.15–9.17), there corresponds a decimation-in-frequency algorithm that is the transpose of the decimation-in-time algorithm and vice versa? Explain.