# Method to generate binary sequences with desired cross-correlation and autocorrelation properties

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?

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.