Two families of low-correlated binary sequences (Q1925010)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Two families of low-correlated binary sequences |
scientific article |
Statements
Two families of low-correlated binary sequences (English)
0 references
11 June 1997
0 references
The correlation of two semi-infinite sequences \(s_1(t)\) and \(s_2(t)\) of period \(n\) is defined as: \[ \theta_{12}(\tau)=\sum(-1)^{s_{12}(t+\tau)+s_{12}(t)}\quad 0\leq\tau\leq n-1. \] If \(\Omega\) is a set of sequences the nonzero periodic correlation is defined as: \[ \theta_{\max}(\Omega)=\max_{s_1,s_2}\max_{0\leq t\leq n-1}|\theta_{12}(\tau)|. \] Previous work on sets of sequences of period \(n\) having maximum periodic correlation \(\theta\) shows that depending on \(\theta\) there are the following two upper bounds on the maximal size of such a set: \[ \begin{aligned} L(n,\theta)\leq(n^2-\theta^2)/(3n-2-\theta^2)\quad &\text{if}\quad\theta^2\leq 3n-8\tag{1}\\ L(n,\theta)\leq 3n^2/10+O(n)\quad &\text{if}\quad\theta^2\leq 3n-10+\sqrt{6n^2-42n+76}.\tag{2}\end{aligned} \] The author gives two constructions of sets having sizes in the range of the given upper bounds. The first one starts with a cyclic code obtained by puncturing an equivalent of the Kerdock code. This code has parameters \([2^{m+1}-2, 2^{2m+2}, 2^m-2^{(m-1)/2}-2]\). From the known weight distribution of the Kerdock code it can be seen that by taking cyclically distinct minimum weight vectors in this code and extending them periodically one obtains a set of sequences having period \(n=2^{m+1}-2\), size \(M=2^m=n/2+1\), and maximal correlation \(\theta=2^{m+1}-2-2d\), where \(d\) is the minimal distance of the code, i.e. \(\theta=2^{(m+1)/2}+2=\sqrt{(n+2)}+2\). This is asymptotically comparable to the first bound. The second construction starts with a cyclic code \(D^*\) obtained by puncturing the Delsarte-Goethals code in the first two coordinates and considering certain vectors of weight \(2^m\pm 2^{(m-1)/2}\), having period \(2^{m+1}-2\). In this way one gets a set of binary sequences of period \(n=2^{m+1}-2\), size \(M=(n+2)^2/4\) and maximal correlation \(\theta=2 \sqrt {(n+2)}+2\), which is asymptotically within the range of the second upper bound (differing only by an amount of approximately \(0.05n^2)\).
0 references
set of sequences
0 references
correlation
0 references
cyclic code
0 references
Kerdock code
0 references
Delsarte-Goethals code
0 references
binary sequences
0 references