(Solution) - Consider the computation of the autocorrelation estimate where -(2025 Original AI-Free Solution)

Paper Details

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 ci[m] can be obtained by computing the N-point circular correlations
where the sequences
and
yi[n] = x[n + iM], 0 ? n ? N ? 1. (P10.38-2)
What is the minimum value of N (in terms of M) suych that ci[m] = ci[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 yi[n] as defined in Eq. (P10.38-2) can be expressed as Yi[k] = Xi[k] + (? 1)kXi+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.