Exhaustive search for low-autocorrelation binary sequences

DOI10.1088/0305-4470/29/18/005MaRDI QIDQ4393618zbMATH OpenOpenAlexFDO

Authors

Publication date 4 November 1998

Published in Journal of Physics A: Mathematical and General (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cond-mat/9605050

zbMATH Keywords

Bernasconi modelbinary sequencescommunication engineeringexact ground statesIsing-spinslow autocorrelationssearch algorithm

Mathematics Subject Classification ID

Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Shift register sequences and sequences over finite alphabets in information and communication theory (94A55)

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 $Noinfty$.

Recommendations

• Low autocorrelation binary sequences
• Low autocorrelation binary sequences: exact enumeration and optimization by evolutionary strategies
• Exhaustive search for optimal minimum peak sidelobe binary sequences up to length 80
• scientific article; zbMATH DE number 4114550
• Polyphase Sequences With Low Autocorrelation

Cited in

(14)

• Exploiting relaxation in local search for LABS
• Explicit merit factor formulae for Fekete and Turyn polynomials
• A method of optimisation of the exhaustive computer search for perfect sequences
• Exhaustive search for optimal minimum peak sidelobe binary sequences up to length 80
• Low autocorrelation binary sequences
• scientific article; zbMATH DE number 529725 (Why is no real title available?)
• scientific article; zbMATH DE number 721896 (Why is no real title available?)
• Low autocorrelation binary sequences: exact enumeration and optimization by evolutionary strategies
• On the ground states of the Bernasconi model
• scientific article; zbMATH DE number 4114550 (Why is no real title available?)
• Rudin-Shapiro-like polynomials in $L_{4}$
• Artificial Evolution
• Solving unconstrained binary polynomial programs with limited reach: application to low autocorrelation binary sequences
• Short paper -- The binary linearization complexity of pseudo-Boolean functions

This page was built for publication: Exhaustive search for low-autocorrelation binary sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4393618)