|
|
A102780
|
|
Ground states of the Bernasconi model; or, greatest merit factor of a binary sequence of length n.
|
|
2
|
|
|
0, 1, 1, 2, 2, 7, 3, 8, 12, 13, 5, 10, 6, 19, 15, 24, 32, 25, 29, 26, 26, 39, 47, 36, 36, 45, 37, 50, 62, 59, 67, 64, 64, 65, 73, 82, 86, 87, 99, 108, 108, 101, 109, 122, 118, 131, 135, 140, 136, 153, 153, 166, 170, 175, 171, 192, 188, 197, 205, 218, 226, 235, 207, 208, 240, 257
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
Peter Borwein, Ron Ferguson, and Joshua Knauer, The merit factor problem, London Mathematical Society Lecture Note Series, 352 (2008): pp. 52ff.
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.]
|
|
EXAMPLE
|
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
|
|
|
|