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. Specially, assume that N = KM.

(a) Determine the steps needed to section x(n) and compute r_xx(m) for –(M/2) + 1 ≤ m ≤ (M/2) – 1, by using 4K M-point DFTs and one M-point IDFT

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

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

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

Transcribed Image Text:

N-m-1 > 1*(n)x(n + m), m > 0 T, (m) = (b) X1(n), 2 X3(n) = |-(--*)