Stephan Mertens - Publications Home | Research | Publications | Teaching | Smorgasbord

Exhaustive search for low autocorrelation binary sequences

Stephan Mertens

---

Abstract

Binary sequences with low autocorrelations are important in communication engineering and in statistical mechanics as groundstates of the Bernasconi-model. Computer searches are the main tool to construct such sequences. Due to the exponential size $O(2^N)$ of the configuration space, exhaustive searches are limited to short sequences. We discuss an exhaustive search algorithm with run time characteristic $O(1.85^N)$ and apply it to compile a table of exact groundstates of the Bernasconi-model up to $N=48$. The data suggests $F> 9$ for the optimal merit factor in the limit $N\to\infty$.

---

BiBTeX Entry

@article{,
   author    = {Stephan Mertens},
   title     = {Exhaustive search for low-autocorrelation binary sequences},
   journal   = {J.~Phys.~A},
   year      = {1996},
   volume    = {29},
   pages     = {L473-L481}
}

---

Download:
mertens-96a.pdf