Dual-Step Optimization for Binary Sequences with High Merit Factors
<|reference_start|>Dual-Step Optimization for Binary Sequences with High Merit Factors: 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.<|reference_end|>
@article{pšeničnik2024dual-step,
    title={Dual-Step Optimization for Binary Sequences with High Merit Factors},
    author={Blav{z} Pv{s}eniv{c}nik, Rene Mlinariv{c}, Janez Brest, Borko
  Bov{s}kovi'c},
    journal={arXiv preprint arXiv:2409.07222},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.07222},
    primaryClass={cs.DS}
}