The butterfly flow graph in Figure 9.10 can be used to compute the DFT of a sequence of...

The butterfly flow graph in Figure 9.10 can be used to compute the DFT of a sequence of length N = 2^ν “in-place,” i.e., using a single array of complex-valued registers. Assume this array of registers A[] is indexed on 0 ≤ l ≤ N − 1. The input sequence is initially stored in in bit-reversed order. The array is then processed by ν stages of butterflies. Each butterfly takes two array elements as inputs, then stores its outputs into those same array locations. The values of 0 and 1 depend on the stage number and the location of the butterfly in the signal flow graph. The stages of the computation are indexed

by m = 1, . . . , ν.

(a) What is as a function of the stage number m?

(b) Many stages contain butterflies with the same “twiddle” factor ?