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?

  • $\begingroup$ so, what – in terms of Fourier Transforms – is the $[\,]$ in your last line? $\endgroup$ Jan 15 '19 at 10:27
  • $\begingroup$ oh and hint: this is the linear correlation that you're using together with the DFT. You'll find it much easier to find results if you start with a cyclic correlation instead! $\endgroup$ Jan 15 '19 at 10:29
  • $\begingroup$ Oh come on, @MarcusMüller, there is no way to get to the linear autocorrelation from the length-$N$ cyclic autocorrelation and you know it. Why mislead the OP? $\endgroup$ Jan 15 '19 at 16:19
  • 1
    $\begingroup$ @DilipSarwate I was hoping he'd reformulate to cyclic correlation, so that we can write something on cyclic convolution, and then close the circle by referring to fast convolution, which far as I can see would be able to implement a fast linear autocorrelation (of finite length) as well? (albeit the benefit would be questionable) $\endgroup$ Jan 15 '19 at 16:21
  • 2
    $\begingroup$ @MarcusMüller Fast or slow is irrelevant; as my answer points out, one cannot get to the linear autocorrelation of a sequence of length $N$ from a length-$N$ DFT and so the OP's question "How can I get the $y(l)$ from the $X(k)$?" is unanswerable except by "You can't". One has to use zero-padding and begin from a length-$M$ DFT $\hat{X}(k)$ (where $M \geq 2N-1$), calculate the $M$ $\hat{X}(k)[\hat{X}(k)]^*$ values, take the length-$M$ iDFT and then interpret the iDFT ($M$ coefficients) to relate them to the $2N-1$ desired linear autocorrelation coefficients of the desired sequence. $\endgroup$ Jan 15 '19 at 16:59

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.

  • $\begingroup$ Thanks for your time and a clear answer. Would you mind giving a expression for $y(l)$ if it were a cyclic correlation, that is, by zero padding as you explained? I would like to see an expression in terms of the X(K) only. Thanks a lot for your help. $\endgroup$
    – Oliver
    Jan 15 '19 at 22:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.