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₀, 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 (z) 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.?

Part 1 x[n] + x[n + N/2]. 0