Naslov An algorithm for construction of extremal and near-extremal \(\mathbb{Z}_4\)-codes Naslov (hrvatski) Algoritam konstrukcije ekstremalnih i skoro ekstremalnih \(\mathbb{Z}_4\)-kodova Autor Matteo Mravić Mentor Sanja Rukavina (mentor)Član povjerenstva Dean Crnković (predsjednik povjerenstva)Član povjerenstva Vedran Krčadinac (član povjerenstva)Član povjerenstva Sanja Rukavina (član povjerenstva)Član povjerenstva Vedrana Mikulić Crnković (član povjerenstva)Ustanova koja je dodijelila Sveučilište u Zagrebu Datum i država obrane 2022-07-01, Hrvatska Znanstveno / umjetničko PRIRODNE ZNANOSTI Univerzalna decimalna klasifikacijaUDC ) 51 - Matematika Sažetak Self-dual \(\mathbb{Z}_4\)-codes are, depending on their Euclidean weight distribution, divided on Type I and Type II codes. For self-dual \(\mathbb{Z}_4\)-codes, a theoretical upper bound on the minimum Euclidean weight of a code is known. Codes that meet that upper bound are called extremal \(\mathbb{Z}_4\)-codes. It is known that Type I extremal \(\mathbb{Z}_4\)-codes do not exist for lengths 24 and 48. For these lengths, self-dual \(\mathbb{Z}_4\)-codes that have the best possible minimum weight are called near-extremal \(\mathbb{Z}_4\)-codes. The main subject of this thesis are extremal and near-extremal \(\mathbb{Z}_4\)-codes. It is known that Type II \(\mathbb{Z}_4\)-codes exist only for lengths divisible by 8. Since we wanted to construct \(\mathbb{Z}_4\)-codes of Type I and Type II, our work is restricted to such lengths. The known method of construction of a self-dual \(\mathbb{Z}_4\)-code has a doubly-even binary code of dimension \(k\) as a starting point. It consists of choosing one matrix \(B\) among the \(2^{\frac{k(k+1)}{2}}\) binary \(k \times k\) matrices that are suitable for the construction of a self-dual \(\mathbb{Z}_4\)-code. The usual approach to the construction of extremal or near-extremal \(\mathbb{Z}_4\)-codes consists of the construction of self-dual \(\mathbb{Z}_4\)-codes and checking their minimum Euclidean weight. The calculation of the minimum Euclidean weight is necessary to determine extremality or near-extremality of \(\mathbb{Z}_4\)-codes, but it is also time consuming. Calculation of minimum Euclidean weight of the code gets slower as the length of the examined code gets bigger. This fact, together with the size of the search space, makes this method inefficient. In this thesis, we modified the known method in such way that more than one \(\mathbb{Z}_4\)-code can be checked for extremality or near-extremality, from one calculation of the minimum Euclidean weight. This increases the efficiency of the existing method. Also, we developed a method to construct a series of Hadamard designs on \(4n - 1\) points from one skew-symmetric Hadamard matrix of order \(n\). This was motivated by the known fact that incidence matrix of a Hadamard 3- design spans a doubly-even binary code. We used developed algorithms to construct new extremal \(\mathbb{Z}_4\)-codes of length 32 and 40. Also, we used the residue codes of the known extremal \(\mathbb{Z}_4\)-codes of length 40 to construct new extremal \(\mathbb{Z}_4\)-codes of the same length. Regarding length 48, by our modified method, we obtained already known extremal \(\mathbb{Z}_4\)-code, and at least two nonequivalent near-extremal \(\mathbb{Z}_4\)-codes. This near-extremal \(\mathbb{Z}_4\)-codes are of no great importance since they have the same residue code as the already known extremal \(\mathbb{Z}_4\)-code of that length. We applied described methods on codes of lengths 56, 64 and 72, but no extremal or near-extremal \(\mathbb{Z}_4\)-codes were constructed. From obtained codes of length 32 and 40, we constructed strongly regular graphs. All of the obtained graphs were already known. Also, we constructed 1-designs on 32 points from obtained extremal \(\mathbb{Z}_4\)-codes of length 32. Some of the constructed designs are resolvable.
Sažetak (hrvatski) Samodualni \(\mathbb{Z}_4\)-kodovi, u ovisnosti o njihovoj distribuciji euklidskih težina, podijeljeni su na kodove tipa I i tipa II. Za samodualne \(\mathbb{Z}_4\)-kodove, teorijske gornje granice minimalnih euklidskih težina su poznate. Kodovi koji dostižu te teorijske granice nazivaju se ekstremalnim \(\mathbb{Z}_4\)-kodovima. Poznato je da ne postoje ekstremalni \(\mathbb{Z}_4\)-kodovi tipa I i duljina 24 i 48. Za te duljine, kodovi tipa I koji postižu maksimalnu moguću minimalnu euklidsku težinu nazivaju se skoro ekstremalnim \(\mathbb{Z}_4\)-kodovima. Predmet istraživanja ove doktorske disertacije su ekstremalni i skoro ekstremalni \(\mathbb{Z}_4\)-kodovi. Poznato je da \(\mathbb{Z}_4\)-kodovi tipa II imaju duljine djeljive s 8. S obzirom da smo htjeli konstruirati \(\mathbb{Z}_4\)-kodove oba tipa, ograničili smo ovaj rad na duljine kodova djeljive s 8. Poznata metoda konstrukcije samodualnog \(\mathbb{Z}_4\)-koda polazi od binarnog dvostruko parnog koda dimenzije \(k\), a sastoji se od odabira jedne od \(2^{\frac{k(k+1)}{2}}\) binarnih \(k \times k\)matrica \(B\) koje su pogodne za konstrukciju samodualnog \(\mathbb{Z}_4\)-koda. Dosadašnji pristup konstrukciji ekstremalnih i skoro ekstremalnih \(\mathbb{Z}_4\)-kodova sastojao se od slučajnog pretraživanja prostora tih matrica i izračuna minimalne euklidske težine dobivenog samodualnog \(\mathbb{Z}_4\)-koda. Izračun minimalne euklidske težine samodualnog \(\mathbb{Z}_4\)-koda nužan je za utvrđivanje ekstremalnosti koda, ali postaje vremenski zahtjevan s porastom duljine koda. Zbog toga, i velikog prostora pretraživanja, ovakav pristup nije efikasan. U ovoj disertaciji modificirali smo opisanu metodu tako da se iz jednog izračuna minimalne euklidske težine \(\mathbb{Z}_4\)-koda uspješno ispituje ekstremalnost i skoro ekstremalnost većeg broja kodova. Time smo povećali učinkovitost postojeće metode. Također, razvili smo metodu konstrukcije serije Hadamardovih dizajna na \(4n-1\) točaka iz koso-simetrične Hadamardove matrice dimenzije \(n\). Motivacija za ovu konstrukciju je poznata činjenica da Hadamardovi 3-dizajni razapinju dvostruko parne binarne kodove, koji su polazna točka konstrukcije samodualnih \(\mathbb{Z}_4\)-kodova. Pomoću te konstrukcije i modificirane metode konstrukcije ekstremalnih i skoro ekstremalnih \(\mathbb{Z}_4\)-kodova, konstruirali smo nove ekstremalne \(\mathbb{Z}_4\)-kodove duljine 32 i 40. Modificiranu metodu primijenili smo i na rezidualne kodove poznatih ekstremalnih \(\mathbb{Z}_4\)-kodova duljine 40 te smo, također, konstruirali nove ekstremalne \(\mathbb{Z}_4\)-kodove. Iz binarnih kodova duljine 48 konstruirali smo jedan, već poznati, ekstremalan \(\mathbb{Z}_4\)-kod te barem dva neekvivalentna skoro ekstremalna \(\mathbb{Z}_4\)-koda. Dobiveni skoro ekstremalni kodovi nisu od velikog značaja jer imaju isti rezidualan kod kao i poznat ekstremalan \(\mathbb{Z}_4\)-kod iste duljine. Konstrukciju smo proveli i za duljine 56, 64 i 72, međutim nismo pronašli ekstremalane niti skoro ekstremalne \(\mathbb{Z}_4\)-kodove. Iz dobivenih binarnih kodova duljina 32 i 40 konstruirali smo već poznate jako regularne grafove. Također, iz ekstremalnih \(\mathbb{Z}_4\)-kodova duljine 32 konstruirali smo 1-dizajne sa 32 točke.
Ključne riječi
Extremal \(\mathbb{Z}_4\)-code
near-extremal \(\mathbb{Z}_4\)-code
\(\mathbb{Z}_4\)-code
binary linear code
self-dual code
doubly-even code
Hadamard matrix
Hadamard design
algorithm
Euclidean weight
Ključne riječi (hrvatski)
ekstremalni \(\mathbb{Z}_4\)-kodovi
skoro ekstremalni \(\mathbb{Z}_4\)-kodovi
\(\mathbb{Z}_4\)-kodovi
binarni linearni kod
samodualni kod
dvostruko parni kod
Hadamardova matrica
Hadamardov dizajn
algoritam
euklidska težina
Jezik engleski URN:NBN urn:nbn:hr:217:242656 Studijski program Naziv: Matematika Vrsta resursa Tekst Opseg xiv, 129 str. Način izrade datoteke Izvorno digitalna Prava pristupa Otvoreni pristup Uvjeti korištenja Datum i vrijeme pohrane 2022-10-11 14:02:56
