OFFSET
1,4
COMMENTS
Binary sequences of +1 and -1 with low autocorrelations have many applications in communication engineering. Their construction has a long tradition and has turned out to be a very hard mathematical problem. This problem is also called the low autocorrelation binary sequences (LABS) problem.
Bernasconi introduced an Ising spin model that allows one to formulate the construction problem in the framework of statistical mechanics.
Consider a sequence of binary variables or Ising spins of length N: S=(s_1, s_2, ..., s_N) s_i in {-1, +1} and their autocorrelations C_g = sum_{i=1..n-g} s_i s_{i + g}.
Bernasconi defined a Hamiltonian H(S) by H(S) = Sum_{g = 1..N-1} (C_g)^2. The ground states (that minimize H(S)) of this model are the low autocorrelation binary sequences we are looking for.
REFERENCES
Tom Hoholdt, "The merit factor problem for binary sequences." Lecture notes in computer science, Vol. 3857 (2006): 51.
Jonathan Jedwab, "A survey of the merit factor problem for binary sequences." In Sequences and Their Applications-SETA 2004, pp. 30-55. Springer Berlin Heidelberg, 2005.
LINKS
Heiko Bauke, The Bernasconi Model.
J. Bernasconi, Low autocorrelation binary sequences: statistical mechanics and configuration space analysis, J. Physique, 48:559, 1987.
Peter Borwein, Kwok-Kwong Stephen Choi, and Jonathan Jedwab, Binary sequences with merit factor greater than 6.34, Information Theory, IEEE Transactions on 50.12 (2004): 3234-3249.
Peter Borwein, Ron Ferguson, and Joshua Knauer, The merit factor problem, London Mathematical Society Lecture Note Series, 352 (2008): pp. 52ff.
Steven Finch, Golay-Littlewood Problem, Mar 05 2014. [Cached copy, with permission of the author]
M. J. E. Golay, The merit factor of long low autocorrelation binary sequences, IEEE Trans. Inform. Theory, IT-28, 1982, 543-549.
Joshua Knauer, Merit Factor Records. Gives best results known at that time for n <= 304 [Broken link]
Joshua Knauer, Merit Factor Records [Cached copy, showing results for n <= 136. Scanned copy of printout of original.]
Stephan Mertens, Exhaustive search for low-autocorrelation binary sequences, J. Phys. A, 29:L473-L481, 1996.
Stephen Mertens, Ground states of the Bernasconi model with open boundary conditions. [Table of records for n <= 60]
Tom Packebusch and Stephan Mertens, Low autocorrelation binary sequences, J. Phys. A: Math. Theor. 49 (2016) 165001. Gives sequence for n <= 66.
EXAMPLE
From Steven Finch, Mar 03 2014: (Start)
The merit factor for the 13-term Barker sequence {1, -1, 1, -1, 1, 1, -1, -1, 1, 1, 1, 1, 1} is 13^2/(2*a(13)) = 169/12 = 14.083...
The merit factor for the 11-term Barker sequence {1, -1, 1, 1, -1, 1, 1, 1, -1, -1, -1} is 11^2/(2*a(11)) = 121/10 = 12.1. (End)
CROSSREFS
KEYWORD
nonn
AUTHOR
Heiko Bauke (heiko.bauke(AT)physik.uni-magdeburg.de), Feb 11 2005
EXTENSIONS
a(61)-a(66) from Packebusch and Mertens (2016) added by Stephan Mertens, Jan 08 2024
STATUS
approved