Skip to main content

New Evolutionary Search for Long Low Autocorrelation Binary Sequences

You are here

Binary sequences with low aperiodic autocorrelation levels, defined in terms of the peak sidelobe level and/or merit factor, have many important engineering applications, such as radars, sonars, spread spectrum communications, system identification and cryptography. Searching for low autocorrelation binary sequences (LABS) is a notorious combinatorial problem, and has been chosen to form a benchmark test for constraint solvers. Due to its prohibitively high complexity, an exhaustive search solution is impractical, except for relatively short lengths. Many suboptimal algorithms have been introduced to extend the LABS search for lengths of up to a few hundreds. In this paper, we address the challenge of discovering even longer LABS by proposing an evolutionary algorithm with a new combination of several features, borrowed from genetic algorithms, evolutionary strategies and memetic algorithms. The proposed algorithm can efficiently discover long LABS of lengths up to several thousands. Recordbreaking minimum peak sidelobe results of many lengths up to 4096 have been tabulated for benchmarking purpose. In addition, our algorithm design can be easily adapted to tackle various extensions of the LABS problem, say, with a generic sidelobe criterion and/or for possibly nonbinary sequences. 

Contact: 
Ke-Lin Du

Field of Interest

“The field of interest shall be the organization, systems engineering, design, development, integration, and operation of complex systems for space, air, ocean, or ground environments. These systems include but are not limited to navigation, avionics, mobile electric power and electronics, radar, sonar, telemetry, military, law-enforcement, automatic test, simulators, and command and control."

Resources

Technology Navigator
Spectrum

Send Us A Message