Best Pair of Binary Sequences

This page reports on the best pair of binary sequences for the auto and cross correlation point of views.
Philippe Langevin, Last modification February 28th 2014.


Let n be a positive integer, f end g two binary sequences of length n i.e. two mapping from the cyclic group Z/nZ into {-1,+1}. The cross correlation between f and g at t is defined by

fxg (t) = sum_{ y - x = t } f(x) g(y)
in other words, the scalar product between the vector f and the t-shift of g. One defines the correlation values :
R(f) = max { f x f (t) | 0 <> t in Z/LZ } and I(f,g) = max { f x g (t) | t in Z/LZ }


To a given sequence f we associate a polynomial of degree less than n in a natural way

f(T) = sum_{k} f(k) T^k

We have two products :
f(T) f( 1/T ) = sum_{k} A_k(f) T^k and f(T) f( 1/T ) = sum_{k} C_k(f) T^k modulo (T^n - 1)

The coefficients C_k(f) are nothing but the autocorrelation values of f, the A_k(f) are called aperiodic correlation values. A sequence with A_k(f) smaller than one in absolute (for k>0) is called a Barker sequence. Such sequences could be useful for radar applications but one conjectures the non existence of Barker sequences of length greater than 13. A sequence with C_k(f) equals to zero for all k>0 is called perfect, one conjectures the non existence of such combinatorial object for n>4. It is easy to see that
C_k(f) = n modulo 4

a reason why one says a binary sequence has optimal correlation when
sup_{k>0} | fxf( k)| = 4, 3, 2, 1 according to the congruence of n modulo 4 is : 0, 1, 2, 3.


Provides datas about the best pair of binary sequences i.e. pair (f,g) of optimal sequences minimizing the correlation parameters :

theta( n ) := min sup { f x g (t) | t in ZnZ}
where both f and g are optimal sequences.


One can see the correlation values of a sequence do not depend on shift and change of sign. For the small values of n ( less than 40 ), one can use a naive approach to compute the distribution of optimal sequences, here are the codes we used :

[src/countps.c] [src/genopt.c] [src/bpbs.c] [cpu.txt]
The running time for n=41 was about 14 hours, using 18 cores of the above architecture below, the same when offloading on xeon phi.
[langevin@mejean COUNTPS]$ cat job.585.out
[Offload] [MIC 0] [File]            countps.c
[Offload] [MIC 0] [Line]            99
[Offload] [MIC 0] [Tag]             Tag 0
[Offload] [HOST]  [Tag 0] [CPU Time]        51451.540086(seconds)
[Offload] [MIC 0] [Tag 0] [CPU->MIC Data]   28 (bytes)
[Offload] [MIC 0] [Tag 0] [MIC Time]        51210.619694(seconds)
[Offload] [MIC 0] [Tag 0] [MIC->CPU Data]   28 (bytes)

L=41 (1) alpha=3 opt=4842
[langevin@mejean COUNTPS]$ cat job.586.out

L=41 (1) alpha=3 opt=4842
[langevin@mejean COUNTPS]$ cat job.586.err


The distribution of optimal sequences up to shift, up to change of sign with length less or equal to 43. The best pairs of optimal sequences are in the opt-file and bp-file. The correlation picture :


[1] The Cross-Correlation of Binary Sequences With Optimal Autocorrelation, Cunsheng Ding and Xiaohu Tang, ieee transactions on information theory, vol. 56, no. 4, april 2010.