Dvofazna optimizacija daljših binarnih zaporedij z nizkimi avtokorelacijami

magistrsko delo

Blaž Pšeničnik (Author), Borko Bošković (Mentor), Janez Brest (Co-mentor)

Abstract

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.

Keywords

binarna zaporedja;avtokorelacija;samoizogibni sprehod;merit faktor;magistrske naloge;

Data

Language:	Slovenian
Year of publishing:	2025
Typology:	2.09 - Master's Thesis
Organization:	UM FERI - Faculty of Electrical Engineering and Computer Science
Publisher:	[B. Pšeničnik]
UDC:	004.421.5(043.2)
COBISS:	245852931
Views:	0
Downloads:	29
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Dual-Step optimization for long binary sequences with low autocorrelation
Secondary abstract:	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.
Secondary keywords:	binary sequences;autocorrelation;self-avoiding walk;merit factor;
Type (COBISS):	Master's thesis/paper
Thesis comment:	Univ. v Mariboru, Fak. za elektrotehniko, računalništvo in informatiko, Računalništvo in informacijske tehnologije
Pages:	1 spletni vir (1 datoteka PDF (IX, 35 str.))
ID:	26622631