The butterfly flow graph in figure can be used to compute the DFT of a sequence of length N = 2^v ?in-place,? i.e., using a single array of complex-valued registers. Assume this array of registers A[?] is indexed on 0 ? I ? N ? 1. The input sequence is initially stored in A[?] in bit-reversed order. The array is then processed by v stages of butterflies. Each butterfly takes two array elements A[?₀] and A[?₁] 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, ,?, v.

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

(b) Many stages contain butterflies with the same ?twiddle? factor W^r_N. ?For these stages, how far apart ate the values of ?₀ for the butterflies with the same W^r_N?

(m - 1)st stage mth stage -1