ERK'2022, Portorož, 355-358 355
Neperiodiˇ cna binarna zaporedja z dobrimi avtokorelacijskimi
lastnostmi: nizke vrednosti stranskih reˇ znjev
Janez Brest, Borko Boˇ skovi´ c
Laboratorij za raˇ cunalniˇ ske arhitekture in jezike,
Inˇ stitut za raˇ cunalniˇ stvo,
Fakulteta za elektrotehniko, raˇ cunalniˇ stvo in informatiko,
Univerza v Mariboru,
Koroˇ ska cesta 46, 2000 Maribor, Slovenija
E-poˇ sta: janez.brest@um.si, borko.boskovic@um.si
Aperiodic Binary Sequences with Good
Autocorrelation Properties: Low Peak
Side-lobe Levels Values
In this short review paper, aperiodic binary sequences
with good autocorrelation properties are presented. The
Peak Side-Lobe Level (PSL) value of a binary sequence
should be as small as possible. Algorithms for tackling
this optimization problem have difficulties when search-
ing for long binary sequences with low PSL values due
to the huge search space. Our main focus is an analysis
of the best-known results in the literature for aperiodic
binary sequences of selected lengths.
1 Uvod
Binarna zaporedja z dobrimi avtokorelacijskimi last-
nostmi so zelo uporabna v praksi. Sreˇ camo jih v fiziki,
kemiji, digitalnih komunikacijah, procesiranju signalov
in kriptografiji. Iskanje binarnih zaporedij glede na de-
finirane kriterije je znan in precej dobro preuˇ cen prob-
lem. V literaturi znani metriki sta najviˇ sji nivo stranskega
reˇ znja (Peak Sidelobe Level, PSL) [17] in MF (Merit fac-
tor) [16].
V sploˇ snem loˇ cimo dve vrsti avtokorelacij in sicer:
• periodiˇ cne in
• aperiodiˇ cne ali neperiodiˇ cne.
V tem ˇ clanku se bomo omejili le na aperiodiˇ cni prob-
lem binarnih zaporedij in na metriko najviˇ sjega stran-
skega reˇ znja. Bralec, ki ˇ zeli izvedeti veˇ c o drugi metriki
(merit factor) in nedavnih rezultatih, je napoten na litera-
turo: [4, 6, 10].
Pri danem binarnem zaporedjuS:
S = (s
0
,s
1
,...,s
L− 1
), (1)
kjerL oznaˇ cuje dolˇ zino binarnega zaporedja, imajo ele-
mentis
i
,i ∈{ 0,L − 1} vrednost +1 ali− 1.
Aperiodiˇ cna avtokorelacijska funkcija binarnega za-
poredjaS pri zamikuk je definirana kot:
C
k
(S) =
L− k− 1
X
i=0
s
i
s
i+k
, zak =− (L− 1),..., − 1, 0, 1,...,L − 1. (2)
Metrika, s katero opiˇ semo kvaliteto binarnega zaporedja,
je najviˇ sji nivo stranskega reˇ znja, PSL, in je defini-
rana [18]:
PSL(S) =
L− 1
max
k=1
|C
k
(S)|. (3)
Cilj je poiskati binarna zaporedja, ki imajo minimalno
vrednost PSL. C
0
imenujemo glavni reˇ zenj, ostali
(C
k
,k = 1, 2,...,L − 1) pa predstavljajo stranske reˇ znje.
Stranski reˇ znji so simetriˇ cni, kar lahko vidimo tudi v
enaˇ cbi (2), in se pojavijo na obeh straneh ob glavnem
reˇ znju.
Nadaljevanje ˇ clanka je sledeˇ ce. V 2. poglavju pri-
kaˇ zemo izraˇ cun vrednosti na primeru kratkega aperi-
odiˇ cnega binarnega zaporedja. V 3. poglavju opravimo
pregled najnovejˇ se literature na podroˇ cju iskanja aperi-
odiˇ cnih binarnih zaporedij z nizkimi avtokorelacijskimi
lastnostmi in podamo pregled najboljˇ sih znanih binarnih
zaporedij z nizkimi vrednostmiPSL glede na dolˇ zino za-
poredij. V 4. poglavju opravimo analizo rasti najboljˇ sih
vrednosti PSL za zaporedja izbranih dolˇ zin do velikosti
pribliˇ zno 2000. Sledi zakljuˇ cno poglavje, kjer izposta-
vimo smernice za nadaljnje raziskave.
2 Zgled
Prikaˇ zimo izraˇ cun avtokorelacijskih funkcij na binarnem
zaporedju s sedmimi elementi (L = 7):
S = (s
0
,s
1
,s
2
,s
3
,s
4
,s
5
,s
6
). S pomoˇ cjo enaˇ cbe (2) izraˇ cunamo avtokorelacijske funk-
cijeC
k
:
C
1
=s
0
s
1
+s
1
s
2
+s
2
s
3
+s
3
s
4
+s
4
s
5
+s
5
s
6
, C
2
=s
0
s
2
+s
1
s
3
+s
2
s
4
+s
3
s
5
+s
4
s
6
, C
3
=s
0
s
3
+s
1
s
4
+s
2
s
5
+s
3
s
6
, C
4
=s
0
s
4
+s
1
s
5
+s
2
s
6
, C
5
=s
0
s
5
+s
1
s
6
, C
6
=s
0
s
6
. ˇ
ClenC
0
smo izpustili, saj ni vkljuˇ cen v enaˇ cbo (3). Ome-
nimo, da ima vsakC
k
natankoL− k elementov. Za nekaj
356
primerov zaporedij zaL = 7 izraˇ cunajmo vrednostiPSL:
S = (1, 1, 1, 1, 1, 1, 1), PSL = 6;
S = (− 1,− 1,− 1, 1, 1, 1, 1), PSL = 4;
S = (1,− 1, 1, 1, 1, 1, 1), PSL = 3;
S = (1, 1, 1,− 1,− 1, 1,− 1), PSL = 1;
Za zadnja dva primera zaporedij so avtokorelacij-
ske funkcije prikazane na sliki 1. Zaporedje, kjer je
PSL =1 , je tudi optimalno za dolˇ zino 7 in je znano
kot Barkerjevo zaporedje. Omenimo ˇ se, da je najdaljˇ se
binarno Barkerjevo zaporedje (zaporedja s PSL =1 )
znano zaL = 13.
Pri majhnih vrednostih L (kratka binarna zaporedja)
lahko optimalno (minimalno) vrednost PSL izraˇ cunamo
z eksaktnim algoritmom, s katerim izraˇ cunamo vrednost
PSL za vse moˇ zne razvrstitve− 1 in 1 v danem binarnem
zaporedju. Vseh moˇ znosti je 2
L
, zato problem iskanja
binarnih zaporedij z nizkimi avtokorelacijami spada med
probleme z eksponentno ˇ casovno zahtevnostjo.
3 Pregled literature in znanih najboljˇ sih
vrednostiPSL
Ker je problem iskanja dolgih binarnih zaporedij ekspo-
nentne narave, se raziskovalci in znanstveniki lotevajo
naslednjih moˇ znosti pri reˇ sevanju problema iskanja za-
poredij z dobrimi avtokorelacijskimi lastnostmi:
• konstrukcijske metode in
• hevristiˇ cni algoritmi.
Konstrukcijske metode [7] omogoˇ cajo, da z dokaj prepro-
stimi postopki naˇ crtujemo binarna zaporedja, lahko tudi
zelo dolga, to je za poljubno dolˇ zino (nekatere konstruk-
cijske metode imajo omejitve, npr. moˇ zno jih je uporabiti
le za dolˇ zineL = 2
n
,n ∈ N), a imajo tako dobljena bi-
narna zaporedja vrednostiPSL, ki so precej oddaljena od
optimalnih vrednosti. Konstrukcijske metode poznamo
ˇ ze od leta 1950 [7].
Hevristiˇ cni algoritmi prav tako ne zagotavljajo, da bi
vedno naˇ sli binarna zaporedna z najmanjˇ simi moˇ znimi
(optimalnimi) vrednostmi – lahko pa uspejo najti solidne
reˇ sitve. Tudi s hevristiˇ cnimi algoritmi se lahko lotimo
iskanja zaporedij, ki so nekoliko daljˇ sa. Hevristiˇ cne al-
goritme lahko dalje razdelimo v dve skupini. Prvi med
postopkom iskanja uporabljajo le eno reˇ sitev (npr. simu-
lirano ohlajanje) in jo postopoma poskuˇ sajo izboljˇ sevati,
drugi pa so populacijski algoritmi, ki med preiskovanjem
uporabljajo veˇ c reˇ sitev, ki jim reˇ cemo populacija. Pri-
meri populacijskih algoritmov so: evolucijski algoritmi,
algoritmi za optimizacijo z roji delcev itd. Pri iskanju bi-
narnih zaporedij so uˇ cinkoviti tudi hevristiˇ cni algoritmi,
ki uporabljajo le eno reˇ sitev in vkljuˇ cujejo mehanizem
ponovnih zagonov (restartov) [5]. Uporabo hevristiˇ cnih
algoritmov za iskanje binarnim zaporedij z nizkimi vred-
nostmi stranskih reˇ znjev najdemo v [6, 12].
Barkerjeva zaporedja so sploˇ sno znana zaporedja, ki
imajo odliˇ cne aperiodiˇ cne avtokorelacijske lastnosti, ven-
dar je velikost najdaljˇ sega poznanega Barkerjevega zapo-
-6 -4 -2 0 2 4 6
0 1 2 3 4 5 6 7
k
C
k
PSL = 3
PSL = 1
Slika 1: Primera avtokorelacijskih funkcij s PSL =3 in
PSL =1 za binarni zaporedji dolˇ zineL = 7.
redja enaka 13, kar pa je ponavadi premalo za uporabo v
praktiˇ cnih aplikacijah.
K.U. Schmidt [24] je predlagal konstrukcijsko me-
todo za aperiodiˇ cna binarna zaporedja z vrednostmiPSL,
ki niso viˇ sja od
p
L ln(2L) in njihove vrednostiPSL bi
naj rastle z redom
p
L ln(lnL), vendar slednje ni doka-
zano.
Obstaja precej konstrukcijskih metod, a nobena od
njih ne zagotavlja, da bi generirana binarna zaporedja
imela najniˇ zjo moˇ zno vrednostPSL [12].
Precej raˇ cunskega napora je bilo vloˇ zenega v iska-
nje binarnih zaporedij z nizkimi vrednostmi PSL [19,
22, 24]. Dandanes so najboljˇ se znane vrednostiPSL (ki
bi naj bile tudi optimalne) za binarna zaporedja dolˇ zine
86≤ L≤ 105 objavljene v [22].
Za daljˇ sa zaporedja so poznane le najboljˇ se znane
vrednosti (ang. best-known results) in pregled literature
naredimo glede na dolˇ zino zaporedij:
• rezultate za zaporedja 106≤ L≤ 300 najdemo v
[6, 12, 13],
• za izbrane dolˇ zine na intervalu 301<L⪅ 4000 v
prispevkih [6, 7, 8, 9, 13, 15, 21, 23, 25],
• za nekatere dolˇ zineL od 4000 do 8191 v prispev-
kih [2, 3] in
• za najdaljˇ se (tudi do dolˇ zine 10
6
) lahko najdemo v
literaturi: [6, 7, 11, 20].
V zadnjem ˇ casu je bilo objavljenih precej ˇ clankov o
binarnih zaporedjih in zanimivo je, da v teh ˇ clankih
lahko zasledimo precejˇ snje izboljˇ sanje eksperimental-
nih rezultatov, ki niso le odraz poveˇ cane zmogljivosti
raˇ cunalniˇ skih sistemov.
4 Rast najboljˇ sih znanih vrednostiPSL
Pri binarnih zaporedjih raziskovalce in znanstvenike za-
nima (asimptotiˇ cna) odvisnost vrednostiPSL od njihove
dolˇ zine. Kot zanimivost povejmo, da matematiˇ cni dokazi
potekajo v smeri preuˇ cevanja ne le izbranih razredov za-
poredij, ampak vseh binarnih zaporedij. V literaturi za-
sledimo, da je rast vrednosti PSL skoraj vseh binarnih
357
l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l 0 10 20 30 40
L
PSL
0 200 400 600 800 1000 1200 1400 1600 1800 2000
l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l Najboljša znana vrednost PSL
−1.5592 + 0.7452 · L,   R
2
= 0.9970
L
Slika 2: Rast vrednostiPSL glede na dolˇ zino binarnih zaporedij (L) zaL =m
2
, 4≤ m≤ 44,m ∈ N.
zaporedij dolˇ zineL:
Θ(
√ L lnL). (4)
Matematiˇ cni dokaz najdemo v [1], v [14, 18] pa naj-
demo eksperimentalni dokaz, ki temelji na raˇ cunalniˇ skih
poskusih. Izraz skoraj vseh uporabljamo, saj obstajajo
razredi binarnih zaporedij, ki odstopajo od enaˇ cbe (4),
npr. binarna zaporedja, kjer imajo vsi elementi vrednost
+1.
Prav tako zanimivo vpraˇ sanje se glasi: kako je z ra-
stjo najboljˇ sih znanih vrednostiPSL v odvisnosti od nji-
hove dolˇ zine? Preden nadaljujemo, opozorimo na dve za-
devi: v enaˇ cbi (4) nastopajo skoraj vsa binarna zaporedja
(v tem primeru govorimo o rasti povpreˇ cnih vrednosti)
in da so optimalne vrednosti PSL znane za L ≤ 105.
V nadaljevanju bomo na slednje vpraˇ sanje odgovorili za
izbrane dolˇ zine binarnih zaporedij do velikosti pribliˇ zno
2000. Za omenjene dolˇ zine so se v zadnjem ˇ casu v litera-
turi pojavili algoritmi, ki dokaj uspeˇ sno reˇ sujejo problem
iskanja binarnih zaporedij z dobrimi avtokorelacijskimi
lastnostmi.
Slika 2 prikazuje aproksimacijo trenutno znanih naj-
boljˇ sih vrednostiPSL aperiodiˇ cnih binarnih zaporedij, ki
imajo dolˇ zino:
L =m
2
, m ∈{ 4, 5,··· , 44} (5)
in jo primerja z rastjo
√ L. Torej izbrane vrednostiL so
16, 25, 36, ..., 1936 in za njih velja, da je m
2
< 2000.
Dobljene vrednostiPSL najdemo v literaturi: [13] ter [6]
(dodali smo ˇ se nekaj izraˇ cunanih vrednosti naˇ sih zadnjih
raziskav). Opazimo lahko, da je
√ L (na sliki 2 oznaˇ ceno
z modro barvo) precej viˇ sje, kot je aproksimacija naj-
boljˇ sih znanih vrednostiPSL (na sliki oznaˇ ceno z rdeˇ co
barvo). Omenjena aproksimacija sledi krivulji, ki jo pri-
kazuje enaˇ cba (6):
0. 7452
√ L− 1. 5592 (6)
Sama aproksimacija s kvadratnim polinomom se lepo
ujema, saj je statistiˇ cna vrednost R
2
= 0. 997. Iz do-
bljenega pa ˇ zal ne moremo sklepati, kako je z rastjo naj-
boljˇ sih binarnih zaporedij pri zelo velikih dolˇ zinah, npr.
L> 10
6
, saj pri teh dolˇ zinah postanejo tudi najboljˇ si he-
vristiˇ cni algoritmi ˇ casovno preveˇ c zahtevni in seveda tudi
premalo zmogljivi.
Matematiˇ cni dokaz ali pa vsaj raˇ cunalniˇ ski eksperi-
menti tako ostajajo odprti pri ugotavljanju rasti vrednosti
PSL aperiodiˇ cnih binarnih zaporedij.
−2000 −1000 0 1000 2000
−40 −20 0 20 40
k
C
k
Slika 3: Primer avtokorelacijskih funkcij s PSL =31 za bi-
narno zaporedje dolˇ zineL = 1936.
Na sliki 3 vidimo primer avtokorelacijskih funkcij za
binarno zaporedje dolˇ zine L = 1936 (44
2
= 1936).
358
Glavni reˇ zenj C
0
je na sliki odrezan. Stranski reˇ znji so
simetriˇ cni glede na glavni reˇ zenj.
5 Zakljuˇ cek
V preglednem ˇ clanku smo predstavili aperiodiˇ cna bi-
narna zaporedja z nizkimi avtokorelacijskimi vrednostmi,
kjer smo se omejili na nizke vrednosti stranskih reˇ znjev
oziroma vrednostPSL.
Opravili smo pregled nedavnih prispevkov, kjer smo
se fokusirali na iskanje neperiodiˇ cnih binarnih zapore-
dij z nizkimi vrednostmi PSL in trenutno znanimi naj-
boljˇ simi rezultati za izbrane dolˇ zine do velikosti pribliˇ zno
2000. Na omenjenem intervalu smo opravili aproksima-
cijo najboljˇ sih vrednosti. Dobljena aproksimacija sledi
krivulji 0. 7452
√ L− 1. 5592, ki je niˇ zja (to je boljˇ sa) kot
√ L.
Hevristiˇ cni algoritmi, ki jih zasledimo v literaturi,
imajo teˇ zave pri reˇ sevanju iskanja aperiodiˇ cnih binar-
nih zaporedij z nizkimi vrednostmi PSL zaradi veliko-
sti iskalnega prostora, ki se glede na dolˇ zino zaporedja
poveˇ cuje eksponentno.
Nadaljnje raziskave na tem podroˇ cju lahko potekajo
v smeri opravljanja eksperimentov za viˇ sje dolˇ zine binar-
nih zaporedij z uporabo zmogljive raˇ cunalniˇ ske strojne
opreme, katere zmogljivost se poveˇ cuje iz dneva v dan.
Zahvala
J. Brest in B. Boˇ skovi´ c priznavata financiranje prispevka
s strani Javne agencije za raziskovalno dejavnost Re-
publike Slovenije, raziskovalni program P2-0041 –
Raˇ cunalniˇ ski sistemi, metodologije in inteligentne sto-
ritve.
Literatura
[1] Noga Alon, Simon Litsyn, and Alexander Shpunt. Typical
peak sidelobe level of binary sequences. IEEE transacti-
ons on information theory, 56(1):545–554, 2009.
[2] Arindam Bose. Waveform Synthesis for Active Sensing
with Emerging Applications. PhD thesis, University of
Illinois at Chicago, 2021.
[3] Arindam Bose and Mojtaba Soltanalian. Constructing bi-
nary sequences with good correlation properties: An effi-
cient analytical-computational interplay. IEEE Trans. Si-
gnal Process., 66(11):2998–3007, 2018.
[4] Borko Boˇ skovi´ c and Janez Brest. Two-phase Optimiza-
tion of Binary Sequences with Low Peak Sidelobe Level
Value. arXiv preprint arXiv:2107.09801, 2021.
[5] Borko Boˇ skovi´ c, Franc Brglez, and Janez Brest. Low-
Autocorrelation Binary Sequences: On Improved Merit
Factors and Runtime Predictions to Achieve Them. Appl.
Soft Comput., 56:262–285, 2017.
[6] Janez Brest and Borko Boˇ skovi´ c. Low Autocorrelation
Binary Sequences: Best-Known Peak Sidelobe Level Va-
lues. IEEE Access, 9:67713–67723, 2021.
[7] Yutao Chen and Ronghao Lin. Computationally Efficient
Long Binary Sequence Designs with Low Autocorrelation
Sidelobes. IEEE Trans. Aerosp. Electron. Syst., 2021.
[8] Gregory E Coxson, Connie R Hill, and Jon C Russo. Adi-
abatic quantum computing for finding low-peak-sidelobe
codes. In 2014 IEEE High Performance Extreme Compu-
ting Conference (HPEC), pages 1–6. IEEE, 2014.
[9] Gregory E Coxson, Jon C Russo, and Angeline Luther.
Long Low-PSL Binary Codes by Multi-Thread Evolutio-
nary Search. In 2020 IEEE International Radar Confe-
rence (RADAR), pages 256–261. IEEE, 2020.
[10] Miroslav Dimitrov. New classes of binary sequences with
high merit factor. arXiv preprint arXiv.2206.12070, 2022.
[11] Miroslav Dimitrov. On the Aperiodic Autocorrelations of
Rotated Binary Sequences. IEEE Commun. Lett., Dec,
2020.
[12] Miroslav Dimitrov, Tsonka Baicheva, and Nikolay Ni-
kolov. Hybrid Constructions of Binary Sequences With
Low Autocorrelation Sidelobes. IEEE Access, 9:112400–
112410, 2021.
[13] Miroslav Dimitrov, Tsonka Baitcheva, and Nikolay Niko-
lov. On the Generation of Long Binary Sequences With
Record-Breaking PSL Values. IEEE Signal Process. Lett.,
27:1904–1908, 2020.
[14] Denis Dmitriev and Jonathan Jedwab. Bounds on the gro-
wth rate of the peak sidelobe level of binary sequences.
Advances in Mathematics of Communications, 1(4):461,
2007.
[15] Anna Dzvonkovskaya and Hermann Rohling. Long binary
phase codes with good autocorrelation properties. In 2008
International Radar Symposium, pages 1–4. IEEE, 2008.
[16] M Golay. The merit factor of Legendre sequences
(corresp.). IEEE Transactions on Information Theory,
29(6):934–936, 1983.
[17] Jonathan Jedwab et al. A survey of the merit factor prob-
lem for binary sequences. In SETA, pages 30–55. Sprin-
ger, 2004.
[18] Jonathan Jedwab and Kayo Yoshida. The peak sidelobe
level of families of binary sequences. IEEE transactions
on information theory, 52(5):2247–2254, 2006.
[19] Anatolii N Leukhin and Egor N Potekhin. Optimal peak
sidelobe level sequences up to length 74. In 2013 Euro-
pean Radar Conference, pages 495–498. IEEE, 2013.
[20] Ronghao Lin, Mojtaba Soltanalian, Bo Tang, and Jian
Li. Efficient Design of Binary Sequences With Low Au-
tocorrelation Sidelobes. IEEE Trans. Signal Process.,
67(24):6397–6410, 2019.
[21] Wai Ho Mow, Ke-Lin Du, and Wei Hsiang Wu. New
evolutionary search for long low autocorrelation bi-
nary sequences. IEEE Trans. Aerosp. Electron. Syst.,
51(1):290–303, 2015.
[22] Carroll J Nunn and Gregory E Coxson. Best-known auto-
correlation peak sidelobe levels for binary codes of length
71 to 105. IEEE Trans. Aerosp. Electron. Syst., 44(1),
2008.
[23] K Veerabhadra Rao and V Umapathi Reddy. Biphase
sequence generation with low sidelobe autocorrelation
function. IEEE Trans. Aerosp. Electron. Syst., AES-
22(2):128–133, 1986.
[24] Kai-Uwe Schmidt. Binary sequences with small peak si-
delobe level. IEEE Trans. Inf. Theory, 58(4):2512–2515,
2012.
[25] Mingxing Zhang, Zhengchun Zhou, Meng Yang, Zilong
Liu, and Yang Yang. A hybrid algorithm for the search
of long binary sequences with low aperiodic autocorrela-
tions. Soft Computing, 25(20):12725–12744, 2021.