Dual-Step Optimization for Binary Sequences with High Merit Factors

Abstract

The problem of finding aperiodic low auto-correlation binary sequences (LABS) presents a significant computational challenge, particularly as the sequence length increases. Such sequences have important applications in communication engineering, physics, chemistry, and cryptography. This paper introduces a novel dual-step algorithm for long binary sequences with high merit factors. The first step employs a parallel algorithm utilizing skew-symmetry and restriction classes to generate sequence candidates with merit factors above a predefined threshold. The second step uses a priority queue algorithm to refine these candidates further, searching the entire search space unrestrictedly. By combining GPU-based parallel computing and dual-step optimization, our approach has successfully identified new best-known binary sequences for all lengths ranging from 450 to 527, with the exception of length 518, where the previous best-known value was matched with a different sequence. This hybrid method significantly outperforms traditional exhaustive and stochastic search methods, offering an efficient solution for finding long sequences with good merit factors.

arXiv comment14 pages, 6 figures, 2 tables

References in corpus (6)

• 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
• On the Generation of Long Binary Sequences with Record-Breaking PSL Values
• Computational Searching of Long Skew-symmetric Binary Sequences with High Merit Factors
• Parallel Self-Avoiding Walks for a Low-Autocorrelation Binary Sequences Problem