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

(a) What is the ?fain? along the path that is emphasized in Figure?

(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, show that each input sample contributes the proper amount to the output DFT sample: i.e., verify that?

Transcribed Image Text:

x[0] o x(4] o N. x[2] X12 x(6] o x(3 -1 x[1] X14 N. x[5]c X[5 WN wo x[3] o X(6 WN wk x[7] X(7 -1 Part C N-1 X[2] = x[n]e-i(2m/N)2n n=0