Dual-step optimization for binary sequences with high merit factors

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

Povzetek

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.

Ključne besede

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

Podatki

Jezik:	Angleški jezik
Leto izida:	2025
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
Založnik:	Elsevier Inc.
UDK:	004
COBISS:	236425219
ISSN:	1095-4333
Št. ogledov:	0
Št. prenosov:	0
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Slovenski jezik
Sekundarne ključne besede:	binarna zaporedja;Golayev faktor zaslug;avtokorelacija;algoritmi;
Vrsta dela (COBISS):	Članek v reviji
Strani:	9 str.
Zvezek:	ǂVol. ǂ165, [article no.] 105316
Čas izdaje:	Oct. 2025
DOI:	10.1016/j.dsp.2025.105316
ID:	26471627