Autocorrelation sequence in terms of Fourier transform of the underlying signal

Question

Let $x(n)$ be a sequence of length $N$, which is zero outside the interval $(0,N-1)$. Let $X(k), k=0,1,\cdots,N-1$ be the FFT coefficients of $x(n)$, that is, $X(k)=\sum_{n=0}^{N-1}x(n) \exp\left( -\frac{j2\pi k n}{N}\right)$. How to relate the autocorrelation sequence $y(l)=\sum_{n=0}^{N-1-l}x(n)x^{*}(n+l)$ in terms of $X(k)$?

My try:

\begin{equation} \begin{split} y(l)& =\sum_{n=0}^{N-1-l}x(n)x^{*}(n+l)\\ & =\sum_{n=0}^{N-1-l}x(n) \left[ \sum_{k=0}^{N-1}X^*(k) \exp\left( -\frac{j2\pi (k+l) n}{N}\right) \right]\\ & = \sum_{k=0}^{N-1}X^*(k) \left[\sum_{n=0}^{N-1-l}x(n) \exp\left( -\frac{j2\pi (k+l) n}{N}\right) \right]\\ \end{split} \end{equation}

How to proceed from here?

Answer 1

There is, unfortunately, no simple way of getting to where you want to from what you have. As Marcus Muller's comment says, the convolutions and correlations that are associated with the DFT (FFT if you like) are cyclic or periodic whereas the autocorrelation that you seek is the linear or aperiodic autocorrelation, and it is difficult to derive the latter from the former. Note for example that cyclic shifts e.g. $(x_k, x_{k+1},\ldots, x_{N-1},x_0, x_1, \ldots x_{k-1})$ instead of $(x_0, x_1, \ldots, x_{N-1})$ have the same periodic autocorrelation but quite different aperiodic autocorrelations. The classic example of this is a PN sequence (maximal-length sequence) of length 7 which has the classic "inverted thumbtack" periodic autocorrelation but quite different aperiodic autocorrelation function depending on which cyclic shift we are using (a.k.a. what is the initial loading of the linear feedback shift register (LFSR) that is generating the PN sequence. In particular, one of the cyclic shifts of the PN sequence is a Barker sequence whose aperiodic autocorrelation function has maximum magnitude $1$ only $\big($that is, all the autocorrelation values are in $\{-1, 0, 1\}\big)$ while other cyclic shifts have larger autocorrelation magnitudes.

So, what to do? The standard trick is to zero-pad the sequence. If you want to find the aperiodic autocorrelation function of $(x_0, x_1, \ldots, x_{N-1})$, begin with the sequence $$\hat{\mathbf x} = (x_0, x_1, \ldots, x_{N-1}, \underbrace{0, 0, \ldots, 0}_{\text{at least} ~N-1~0\text{s}})$$ of length $M \geq 2N-1$, compute its length-$M$ DFT etc. There are plenty of answers here explaining the zero padding technique and so I won't bother explaining further.