In implementing an FFT algorithm, it is sometimes useful to generate the powers of WN wi...

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^ν . 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 ν = log₂ N, so the array holding the initial input sequence is the zeroth array and the DFT is in the v^th 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 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 m^th 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 m^th stage? How many different coefficients are required in the m^th stage?

(b) Write a difference equation whose impulse response h[n] contains the coefficientsW^r_N required by the butterflies in the m^th 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.