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$
  • 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$ – robert bristow-johnson Sep 25 '17 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 Sep 27 '17 at 0:11
  • 3
    $\begingroup$ you should give the answer a check mark, then. $\endgroup$ – robert bristow-johnson Sep 27 '17 at 2:42
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$
  • 1
    $\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 Sep 26 '17 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 Sep 27 '17 at 0:16
  • $\begingroup$ @Sal For aperiodic autocorrelations, look at the impulse-equivalent sequences of Huffman mentioned in my paper cited above. $\endgroup$ – Dilip Sarwate Sep 27 '17 at 3:20

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.