Let us consider the use of the DFT (computed via the FFT algorithm) to compute the autoc...

Let us consider the use of the DFT (computed via the FFT algorithm) to compute the autocorrelation of the complex-valued sequence x(n), that is,

Suppose the size M of the FFT is much smaller than that of the data length N. Specifically, assume that N = KM. (a) Determine the steps needed to section x(n) and compute r_xx (m) for -(M/2) + 1 ≤ m ≤ (MI2)- 1, by using 4K M-point DFTs and one M -point MET.

(b) Now consider the following three sequences x₁(n) , x₂,(n) , and x₃(n), each of duration M . Let the sequences x1 (n) and x₂ (n) have arbitrary values in the range 0 ≤ n ≤ (M/2) - 1, but be zero for (M/2) ≤ n ≤ M - 1. The sequence x₃ (n) is defined as

Determine a simple relationship among the Al -point DFTs X₁ (k), X₂(k), and X₃ (k)

(c) By using the result in part (13), show how the computation of the DFTs in part (a) can be reduced in number from 4K to 2K.