In implementing an FFT algorithm, it is sometimes useful to generate the powers of WN with a recursive difference equation, or oscillator. In this problem we consider a radix-2 decimation-in-time algorithm for N = 2ν . Figure 9.11 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 ν = log2 N, so the array holding the initial input sequence is the zeroth array and the DFT is in the vth array. In computing the butterflies in a given stage, all butterflies requiring the same coefficients Wr N are evaluated before obtaining new coefficients. In indexing through the array, we assume that the data 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 ≤ ν. Answers should be expressed in terms of m.
(a) How many butterflies must be computed in the mth stage? How many different coef- ficients are required in the mth stage?
(b) Write a difference equation whose impulse response h[n] contains the coefficients Wr 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.