I am looking for a method to generate two binary sequences of length $N$ with the following properties:

  • Very good cross-correlation for all shifts.
  • Good enough autocorrelation for all shifts except zero delay (good enough means $\gg 1$ and $\ll N$).

I can even relax the constraint on the cross-correlation as follows:

  • Very good cross-correlation for $\pm M$ shifts around zero delay, and no matter for the other shifts.
  • Good enough autocorrelation for all shifts except zero delay.

Following publications of Dr Welch and Dr Sarwate, it is possible to obtain a set of $K$ sequences of length $N$ and norm $N$ with the following properties : $$\max(θ_a,θ_c)≥N\sqrt{\frac{K}{NK-1}} \approx \sqrt{N},$$ and $$\theta_c^2 + \frac{N-1}{N(K-1)}\theta_a^2 \geq N,$$ where $\theta_a$ is the maximum autocorrelation and $\theta_c$ is the maximum crosscorrelation.

From that, I understand that it is possible to find two sequences whose cross-correlation is ideal ($\theta_c = 0$) and whose autocorrelation is good enough ($\theta_a \approx \sqrt{N}$). However, I am not aware of a method or an algorithm to generate such sequences. Could you provide some directions or point to a paper that would help?

Besides, by limiting the constraint on the cross-correlation to some shifts only, can we expect to reduce noticeably the maximum autocorrelation? Are there methods to generate such sequences?


1 Answer 1


Flattered though I am that a short note (D.V. Sarwate, "Bounds on crosscorrelation and autocorrelation of sequences", IEEE Trans. Information Theory, vol. IT-25, pp. 720-724, 1979) that I wrote over 40 years ago is still receiving some notice, the OP's question is way too broad for this forum; people (not me!) have written whole books on this subject.

Neither Lloyd Welch nor I ever claimed that there exist sequence sets that meet these bounds exactly or almost exactly. Rather, every set of $K$ sequences of period $N$ must be such that $(1)$ and $(2)$ in the OP's question are satisfied. In particular, the OP's belief

From this, I understand that it is possible to find two sequences whose cross-correlation is ideal ($\theta_c = 0$) and whose autocorrelation is good enough ($\theta_a \approx \sqrt{N}$).

is a false understanding. If two sequences are uncorrelated (that is, $\theta_c = 0$), then $\theta_a$ must be at least $\sqrt N$, but it is not the case that there must exist a pair of uncorrelated sequences with $\theta_a \approx \sqrt N$. My paper cited above gives examples of a set of $N$ sequences (the rows of a length-$N$ DFT matrix) for which $\theta_c = 0$ but $\theta_a = N$ which is much larger than the desired $\sqrt N$. Unfortunately, while smaller subsets do still satisfy $\theta_c = 0$, the maximum off-peak autocorrelation continues to cling to $\theta_a = N$. The paper also described the Frank-Zadoff-Chu sequences for which $\theta_c = \sqrt{N}$ and $\theta_a = 0$. Both sets are optimal with respect to these bounds. The sequences in both sets are complex-valued, not binary.

For sets of $N$ binary sequences of period $N$, a bound due to Sidel'nikov tells us that $\theta_\max$ must be at least as large as $\approx \sqrt{2N-2}$. $\,\,$ Gold sequences of period $N = 2^{2n+1}-1$ essentially meet this bound ($\theta_\max $ equals $\sqrt{2(N+1)}+1)\approx \sqrt{2N-2}$, but for periods $N = 2^{2n}-1$, $\theta_\max$ is $\approx 2\sqrt{N}$ for Gold or Gold-like sequences. If $\theta_\max\approx \sqrt{N}$ is non-negotiable as a criterion for sequence design, then for $N=2^{2n}-1$, the small set of Kasami sequences has $\sqrt{N+1} = 2^n$ sequences with $\theta_\max= \sqrt{N+1}+1 = 2^n+1$. For more details, see D.V. Sarwate and M.B. Pursley, "Cross-correlation properties of pseudorandom and related sequences," Proc. IEEE, vol.68, pp.593-619, May 1980.

With regard to other queries in the OP's question, some work has been done towards the construction of of sequences whose autocorrelation values are small for small nonzero offsets (while larger bounds for large offsets are OK), but typically, small crosscorrelation values for small offsets while allowing larger values for larger offsets has not received much attention. The former problem is of interest because it makes fine-tuning of the synchronization process in spread-spectrum systems easier; the latter might be more of a niche problem for special systems with nearly synchronized times-of-arrival.


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.