Dual-step optimization for binary sequences with high merit factors

Blaž Pšeničnik (Author), Rene Mlinarič (Author), Janez Brest (Author), Borko Bošković (Author)

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 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 best-known binary sequences for all lengths ranging from 450 to 527, with the exception of length 518, where the previous best-known merit factor 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.

Keywords

binarna zaporedja;Golayev faktor zaslug;avtokorelacija;algoritmi;binary sequences;Golay's merit factor;autocorrelation;algorithms;

Data

Language:	English
Year of publishing:	2025
Typology:	1.01 - Original Scientific Article
Organization:	UM FERI - Faculty of Electrical Engineering and Computer Science
Publisher:	Elsevier Inc.
UDC:	004
COBISS:	236425219
ISSN:	1095-4333
Views:	0
Downloads:	0
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary keywords:	binarna zaporedja;Golayev faktor zaslug;avtokorelacija;algoritmi;
Type (COBISS):	Article
Pages:	9 str.
Issue:	ǂVol. ǂ165, [article no.] 105316
Chronology:	Oct. 2025
DOI:	10.1016/j.dsp.2025.105316
ID:	26471627