Dvofazna optimizacija daljših binarnih zaporedij z nizkimi avtokorelacijami

magistrsko delo

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

Povzetek

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;magistrske naloge;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2025
Tipologija:	2.09 - Magistrsko delo
Organizacija:	UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
Založnik:	[B. Pšeničnik]
UDK:	004.421.5(043.2)
COBISS:	245852931
Št. ogledov:	0
Št. prenosov:	29
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Dual-Step optimization for long binary sequences with low autocorrelation
Sekundarni povzetek:	The problem of finding low autocorrelation binary sequences presents a significant computational challenge, as it is classified as a hard combinatorial problem. Binary sequences with high merit factors, and thus low autocorrelation properties, have important applications in digital communications, where they enable effective separation of signals from noise, as well as in physics, chemistry, cryptography, and other fields. In this work, we will present a new stochastic dual-step optimization algorithm for long binary sequences with low autocorrelation. The first step consists of a parallel algorithm that exploits skew-symmetry and restriction classes, utilizing graphics processing units to accelerate computations. The second step is a priority queue-based algorithm, which further improves the sequences from the first step by relaxing both constraints and operating over the entire search space of the problem. We will also show that the dual-step optimization finds better binary sequences than those currently known, particularly for longer sequences.
Sekundarne ključne besede:	binary sequences;autocorrelation;self-avoiding walk;merit factor;
Vrsta dela (COBISS):	Magistrsko delo/naloga
Komentar na gradivo:	Univ. v Mariboru, Fak. za elektrotehniko, računalništvo in informatiko, Računalništvo in informacijske tehnologije
Strani:	1 spletni vir (1 datoteka PDF (IX, 35 str.))
ID:	26622631