Figure P9.6 shows the graph representation of a decimation-in-time FFT algorithm for N =...

Figure P9.6 shows the graph representation of a decimation-in-time FFT algorithm for N = 8. The heavy line shows a path from sample x[7] to DFT sample X[2].

(a) What is the “gain” along the path that is emphasized in Figure P9.6?

(b) How many other paths in the flow graph begin at x[7] and end at X[2]? Is this true in general? That is, how many paths are there between each input sample and each output sample?

(c) Now consider the DFT sample X[2]. By tracing paths in the flow graph of Figure P9.6, show that each input sample contributes the proper amount to the output DFT sample; i.e., verify that