Exhaustive search for low autocorrelation binary sequences

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

6 pages, LaTeX2e, several packages, 3 figures (eps), extended version contains data for N=47 and 48

References in corpus (3)

• Replica Field Theory for Deterministic Models: Binary Sequences with Low Autocorrelation
• Self Induced Quenched Disorder: A Model for the Glass Transition
• Aging without disorder on long time scales

Cited by in corpus (13)

• Optimization Methods for Designing Sequences with Low Autocorrelation Sidelobes
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• Low Autocorrelation Binary Sequences
• Low-Autocorrelation Binary Sequences: On Improved Merit Factors and Runtime Predictions to Achieve Them
• Landscape statistics of the low autocorrelated binary string problem
• On the ground states of the Bernasconi model
• Low Autocorrelation Binary Sequences: Number Theory-based Analysis for Minimum Energy Level, Barker codes
• Intra-Pulse Polyphase Coding System for Second Trip Suppression in a Weather Radar
• A Non-Disordered Glassy Model with a Tunable Interaction Range
• Low autocorrelated multi-phase sequences
• Metastable States in High Order Short-Range Spin Glasses
• Generation of unpredictable time series by a Neural Network
• Autocorrelations of Binary Sequences and Run Structure