Iskanje po katalogu digitalne knjižnice

Opis: Problem iskanja binarnih zaporedij z nizko avtokorelacijo (angl. low autocorrelation binary sequences problem) predstavlja izjemen računski izziv, saj je klasificiran kot težek kombinatorični problem. Binarna zaporedja z visokimi merit faktorji, in s tem nizkimi avtokorelacijskimi lastnostmi, imajo pomembne aplikacije v digitalnih komunikacijah, kjer omogočajo učinkovito ločevanje signalov od šuma, pa tudi v fiziki, kemiji, kriptografiji, itd. V zaključnem delu bomo predstavili nov stohastični dvofazni algoritem za optimizacijo daljših binarnih zaporedij z nizkimi avtokorelacijami. Prva faza predstavlja paralelni algoritem, ki izkorišča popačeno simetrijo in razrede omejitev ter uporablja grafične procesne enote za pohitritev računanja. Druga faza pa je algoritem s prioritetno vrsto, ki dodatno izboljša zaporedja prve faze s tem, da sprosti omejitvi in deluje nad celotnim iskalnim prostorom problema. Pokazali bomo tudi, da dvofazna optimizacija omogoča iskanje boljših binarnih zaporedij, zlasti za daljše dolžine zaporedij.
Ključne besede: binarna zaporedja, avtokorelacija, samoizogibni sprehod, merit faktor
Objavljeno v DKUM: 13.08.2025; Ogledov: 0; Prenosov: 35
Celotno besedilo (1,43 MB)

Opis: 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: binary sequences, Golay's merit factor, autocorrelation, algorithms
Objavljeno v DKUM: 30.05.2025; Ogledov: 0; Prenosov: 12
Celotno besedilo (968,30 KB)