In implementing an FFT algorithm, it is sometimes useful to generate the powers of W_N with a recursive difference equation, or oscillator. In this problem we consider a radix-2 decimation-in-time algorithm for N = 2^v. Figure depicts this type of algorithm for N = 8. To generate the coefficients efficiently, the frequency of the oscillator would change from stage to stage. Assume that the arrays are numbered 0 through v = log₂ N, so the array holding the initial input sequence is the zeroth array and the DFT in=s in the vth array. In computing the butterflies in a given stage, all butterflies requiring the same coefficients W^r_N are evaluated before obtaining new coefficients, In indexing through the array, we assume that the date in the array are stored in consecutive complex registers numbered 0 through (N – 1). All the following questions are concerned with the computation of the mth array from the (m – 1)st array, where 1 ≤ m ≤ v. Answers should be expressed in terms of m.

(a) How many butterflies must be computed in the mth stage? How many different coefficients are required in the mth stage? 

(b) Write a difference equation whose impulse response h[n] contains the coefficients W^r_n required by the butterflies in the mth stage.

(c) The difference equation from part (b) should have the form of an oscillator, i.e., h [n] should be periodic for n ≥ 0. What is the period of h[n]? Based on this, write an expression for the frequency of this oscillator as a function of m