Sections 9.2 and 9.3 focus on the fast Fourier transform for sequences where N is a powe...

Sections 9.2 and 9.3 focus on the fast Fourier transform for sequences where N is a power of 2. However, it is also possible to find efficient algorithms to compute the DFT when the length N has more than one prime factor, i.e., cannot be expressed as N = mν for some integer m. In this problem, you will examine the case where N = 6. The techniques described extend easily to other composite numbers. Burrus and Parks (1985) discuss such algorithms in more detail.

(a) The key to decomposing the FFT for N = 6 is to use the concept of an index map, proposed by Cooley and Tukey (1965) in their original paper on the FFT. Specifically, for the case of N = 6, we will represent the indices n and k as

Verify that using each possible value of n1 and n2 produces each value of n = 0, . . . , 5 once and only once. Demonstrate that the same holds for k with each choice of k₁ and k₂.

(b) Substitute Eqs. (P9.60-1) and (P9.60-2) into the definition of the DFT to get a new expression for the DFT in terms of n₁, n₂, k₁, and k₂. The resulting equation should have a double summation over n₁ and n₂ instead of a single summation over n.

(c) Examine the W₆ terms in your equation carefully. You can rewrite some of these as equivalent expressions in W₂ and W₃.

(d) Based on part (c), group the terms in your DFT such that the n₂ summation is outside and the n₁ summation is inside. You should be able to write this expression so that it can be interpreted as three DFTs with N = 2, followed by some “twiddle” factors (powers of W₆), followed by two N = 3 DFTs.

(e) Draw the signal flow graph implementing your expression from part (d). How many complex multiplications does this require? How does this compare with the number of complex multiplications required by a direct implementation of the DFT equation for N = 6?

(f) Find an alternative indexing similar to Eqs. (P9.60-1) and (P9.60-2) that results in a signal flow graph that is two N = 3 DFTs followed by three N = 2 DFTs.