Consider the computation of the autocorrelation estimate

where x[n] is a real sequence. Since ?_xx[?m] = ?_xx[m], it is necessary onlu to evaluate Eq. (p10.38-1) for 0 ? m ? M ? 1 to obrain ?_xx[m] for ?(M ? 1) ? m ? M ? 1, as is required to estimate the power density spectrum using Eq. (10.88).

(a) When Q >> M, it may not be feasible to compute ?_xx[m] using a single FFT somputation. In such cases, it is convenient to exxpress ?_xx[m] as a sum of correlation estimates based on shorter sequences . Show that if Q = KM,

Where

For 0 ? m ? M ? 1.

(b) Show that the correlations c_i[m] can be obtained by computing the N-point circular correlations?

where the sequences

and

y_i[n] = x[n + iM],? ? ? ??0 ? n ? N ? 1.? ? ? ? ? ? ? ? ? ? ? ? ??(P10.38-2)

What is the minimum value of N (in terms of M) suych that c_i[m] = c_i[m] for 0 ? m ? M ? 1?

(c) State a procedure for computing ?_xx[m] for 0 ? m ? M ? 1 that involves the computation of 2K N-point DFTs of real sequences and one N-point inverse DFT. How many complex multiplications are required to compute ?_xx[m] for 0 ? m ? M ? 1 if a radix-2 FFT is used?

(d) What modifications to the procedure developed in part (c) would be necessary to compute the cross-correlation estimate?

where x [n] and y[n] are real sequences known for 0 ? n ? Q ? 1?

(e) Rader (1970) showed that, for computing the autocorrelation estimate ?_xx[m] for 0 ? m ? M ? 1, significant savings of computation can be achieved if N = 2M. Show that the N-point DFT of a segment y_i[n] as defined in Eq. (P10.38-2) can be expressed as?

Y_i[k] = X_i[k] + (? 1)^kX_i+1[k], ? ? ? ? ? ? ?k = 0, 1, ? , N ? 1.

State a procedure for computing ?_xx[m] for 0 ? m ? M ? 1 that involves the computation of K N-point DFTs and one N-point inverse DFT. Determine the total number of complex multiplications in this case of a radix-2 FFT is used.

Transcribed Image Text:

h;[n} 0 1 2 3 4 5 6 7 (a) h]n] 0 1 2 3 4 5 6 7 (b)