Suppose that a program is available that computes the DFT of a complex sequence. If we w...

Suppose that a program is available that computes the DFT of a complex sequence. If we wish to compute the DFT of a real sequence, we may simply specify the imaginary part to be zero and use the program directly. However, the symmetry of the DFT of a real sequence can be used to reduce the amount of computation.

(a) Let x[n] be a real-valued sequence of length N, and let X[k] be its DFT with real and imaginary parts denoted X_R[k] and X_I[k], respectively; i.e.,

X[k] = X_R[k] + jX_I[k].

Show that if x[n] is real, then X_R[k] = X_R[N − k] and X_I[k] = −X_I[N − k] for k = 1, . . . , N − 1.

(b) Now consider two real-valued sequences x1[n] and x₂[n] with DFTs X₁[k] and X₂[k], respectively. Let g[n] be the complex sequence g[n] = x1[n] + jx₂[n], with corresponding DFT G[k] = G_R[k]+jG_I [k]. Also, let G_OR[k],G_ER[k],G_OI[k] and G_EI[k] denote, respectively, the odd part of the real part, the even part of the real part, the odd part of the imaginary part, and the even part of the imaginary part ofG[k]. Specifically, for 1 ≤ k ≤ N − 1,

(c) Assume that N = 2^ν and that a radix-2 FFT program is available to compute the DFT. Determine the number of real multiplications and the number of real additions required to compute both X₁[k] and X₂[k] by (i) using the program twice (with the

imaginary part of the input set to zero) to compute the two complex N-point DFTs X₁[k] and X₂[k] separately and (ii) using the scheme suggested in part (b), which requires only one N-point DFT to be computed.

(d) Assume that we have only one real N-point sequence x[n], where N is a power of 2. Let x₁[n] and x₂[n] be the two real N/2-point sequences x₁[n] = x[2n] and x₂[n] = x[2n + 1], where n = 0, 1, . . . , (N/2) − 1. Determine X[k] in terms of the

(N/2)-point DFTs X₁[k] and X₂[k].

(e) Using the results of parts (b), (c), and (d), describe a procedure for computing the DFT of the real N-point sequence x[n] utilizing only one N/2-point FFT computation. Determine the numbers of real multiplications and real additions required by this procedure, and compare these numbers with the numbers required if the X[k] is computed using one N-point FFT computation with the imaginary part set to zero.