Consider an N-point sequence x[n] with DFT X[k], k = 0, 1, . . . , N − 1. The following...

Consider an N-point sequence x[n] with DFT X[k], k = 0, 1, . . . , N − 1. The following

algorithm computes the even-indexed DFT values X[k], k = 0, 2, . . . , N − 2, for N even, using only a single N/2-point DFT:

1. Form the sequence y[n] by time aliasing, i.e.,

2. Compute Y [r], r = 0, 1, . . . , (N/2) − 1, the N/2-point DFT of y[n].

3. Then the even-indexed values of X[k] are X[k] = Y [k/2], for k = 0, 2, . . . , N − 2.

(a) Show that the preceding algorithm produces the desired results.

(b) Now suppose that we form a finite-length sequence y[n] from a sequence x[n] by

Determine the relationship between the M-point DFT Y [k] and X(e^jω), the Fourier transform of x[n]. Show that the result of part (a) is a special case of the result of part(b).

(c) Develop an algorithm similar to the one in part (a) to compute the odd-indexed DFT values X[k], k = 1, 3, . . . , N − 1, for N even, using only a single N/2-point DFT.