2
$\begingroup$

I have heard somewhere that sequences with perfect autocorrelations and crosscorrelations do not exist. I have been searching for an insight into this claim, but have not been successful.

Can anyone can give a think about this and share his view? I have tried seeing previous questions but no luck there as well.

$\endgroup$
3
  • 1
    $\begingroup$ what do you mean by "perfect" with regard to autocorrelation? there are repeating sequences of $x[n]=\pm1$, called Maximum Length Sequences (MLS) or Linear Feedback Shift Register (LFSR) sequences or PN sequences or Galios fields (GF(2)) that have a "perfect" kronecker delta function (with a little bit of a constant added) as the autocorrelation. $\endgroup$ Commented Sep 25, 2017 at 23:33
  • $\begingroup$ Hi Robert, what I meant to ask was relating to Welch bound and has been appropriately answered by D. Sarwate below. $\endgroup$
    – Sal
    Commented Sep 27, 2017 at 0:11
  • 3
    $\begingroup$ you should give the answer a check mark, then. $\endgroup$ Commented Sep 27, 2017 at 2:42

1 Answer 1

7
$\begingroup$

Let $\theta_a$ and $\theta_c$ respectively denote the maximum magnitudes of the off-peak or out-of-phase periodic autocorrelation functions and the periodic crosscorrelation functions of a set of $K$ sequences of length $N$ and energy $\sum_{n=0}^{N-1}|x[n]]|^2 = N$. In a seminal paper published in 1974, Welch proved that $$\max\big(\theta_a, \theta_c\big)\geq N\sqrt{\frac{K}{NK-1}} \approx \sqrt{N}$$ and so $\theta_a$ and $\theta_c$ both cannot have value $0$; at least one of them must be as large as $\sqrt{N}$. This shows that it is not possible to have uncorrelated sequences with perfect autocorrelation, just as the OP heard somewhere.

In a follow-up paper in 1979, I showed that $$\left(\frac{\theta_c^2}{N}\right)+\frac{N-1}{N(K-1)}\left(\frac{\theta_a^2}{N}\right) \geq 1$$ which allows one to study the autocorrelation and crosscorrelation maxima separately, and gives additional insights into the problem.

  • If $\theta_a = 0$ (all $K$ sequences have ideal autocorrelation functions), then $\theta_c \geq \sqrt{N}$. An example of such a set is the Frank-Zadoff-Chu sequences which have perfect autocorrelation functions and maximum crosscorrelation $\sqrt{N}$.

  • If $\theta_c = 0$ (the $K$ sequences are uncorrelated, i.e., orthogonal for all cyclic shifts), then $\theta_a \gtrapprox K$. In particular, a set of $N$ uncorrelated sequences of length $N$ has $\theta_a = N$. An example of such a set of sequences is the rows of a $N\times N$ DFT matrix. It is, of course, trivially true that a set of $K>N$ sequences of length $N$ cannot be orthogonal to each other, let alone be uncorrelated.

Similar results (but not the examples) hold for the aperiodic (or linear) correlation functions. For details, see my paper cited above.

$\endgroup$
3
  • 2
    $\begingroup$ Very nice summary, especially the examples you gave in the additional insights. I learned something new today; I wasn't aware of those specific relationships between the autocorrelation and cross-correlation properties. $\endgroup$
    – Jason R
    Commented Sep 26, 2017 at 16:54
  • $\begingroup$ @Dilip Sarwate. I had a look through your paper earlier as I am working on creating a "close-to-perfect" aperiodic sequences. However, the explanation you have given here has helped me understand your findings (then) and the question I asked (now). Appreciate your response. $\endgroup$
    – Sal
    Commented Sep 27, 2017 at 0:16
  • $\begingroup$ @Sal For aperiodic autocorrelations, look at the impulse-equivalent sequences of Huffman mentioned in my paper cited above. $\endgroup$ Commented Sep 27, 2017 at 3:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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