Consider the computation of the autocorrelation estimate where x[n] is a real s...

Consider the computation of the autocorrelation estimate

where x[n] is a real sequence. Since it is necessary only to evaluate Eq. (P10.44-1) for 0 ≤ m ≤ M − 1 to obtain for −(M − 1) ≤ m ≤ M − 1, as is required to estimate the power density spectrum using Eq. (10.102).

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

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

What is the minimum value of N (in terms of M) such that for 0 ≤ m ≤ M − 1?

(c) State a procedure for computing 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 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 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.44-2) can be expressed as

State a procedure for computing 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 if a radix-2 FFT is used.