Computational Methods for Classification of Codes
Loading...
URL
Journal Title
Journal ISSN
Volume Title
School of Electrical Engineering |
Doctoral thesis (article-based)
| Defence date: 2017-09-29
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
2017
Major/Subject
Mcode
Degree programme
Language
en
Pages
71 + 75
Series
Aalto University publication series DOCTORAL DISSERTATIONS, 159/2017
Abstract
One of the fundamental problems in digital communications and data storage systems is finding good coding methods that allow transmitting or storing information efficiently in situations where errors may occur. Many problems in coding theory can be described in terms of combinatorial objects. These problems can then be solved using theoretical and computational methods. The focus of this thesis is developing algorithms for classification and existence problems involving codes and covering arrays, which are mathematically related to codes and used for example in designing tests for systems such as software. The algorithms make use of common techniques for exhaustive generation and isomorph rejection. The new methods are applied to three problems. First, all maximum distance separable (MDS) codes over alphabets of size at most 8 with minimum distance at least 3 are classified. Three new equivalence classes of perfect one-error-correcting 8-ary MDS codes are found. Second, some small covering arrays of strength 2 are classified to assist studying the structure of such arrays. These results also settle the size of an optimal covering array in some cases. Third, the chromatic number of the square of the 8-cube, a problem that has resisted a solution since the first attempts in early 1990s, is solved using a coding-theoretical approach and the method of prescribing symmetries.Digitaalisessa viestinnässä ja tiedontallennusjärjestelmissä keskeinen ongelma on löytää hyviä koodausmenetelmiä, joilla voidaan siirtää tai tallentaa tietoa tehokkaasti tilanteissa, joissa voi esiintyä virheitä. Monet koodausteorian ongelmat voidaan esittää kombinatoristen objektien avulla, ja näitä ongelmia voidaan ratkoa teoreettisilla ja laskennallisilla menetelmillä. Tässä työssä kehitetään algoritmeja koodien ja peittotaulukoiden luokittelu- ja olemassaolo-ongelmiin. Peittotaulukot muistuttavat matemaattisesti koodeja, ja niitä käytetään esimerkiksi ohjelmistojen testeissä. Algoritmit käyttävät yleisiä tekniikoita kattavaan hakuun ja isomorfisten objektien karsimiseen. Kehitettyjä menetelmiä sovelletaan työssä kolmeen ongelmaan. Ensiksi luokitellaan kaikki MDS-koodit (engl. maximum distance separable), joiden aakkoston koko on enintään 8 ja minimietäisyys vähintään 3. Luokittelussa löydetään kolme uutta ekvivalenssiluokkaa täydellisiä yhden virheen korjaavia MDS-koodeja, joiden aakkoston koko on 8. Toiseksi luokitellaan pieniä peittotaulukoita. Luokittelun tarkoitus on auttaa niiden rakenteen tutkimisessa, ja saadut tulokset myös ratkaisevat optimaalisen peittotaulukon koon joissakin tapauksissa. Kolmantena ratkaistaan 8-ulotteisen hyperkuution neliön kromaattinen luku. 1990-luvun alkupuolelta alkaneista yrityksistä huolimatta tähän ongelmaan ei ole aiemmin löydetty ratkaisua. Tässä työssä ongelma ratkaistaan lähestymällä sitä koodausteorian näkökulmasta ja käyttämällä menetelmää, jossa kiinnitetään haettavan rakenteen symmetrioita.Description
Supervising professor
Östergård, Patric, Prof., Aalto University, Department of Communications and Networking, FinlandKeywords
algorithm, classification, MDS code, covering array, chromatic number, algoritmi, luokittelu, MDS-koodi, peittotaulukko, kromaattinen luku
Other note
Parts
-
[Publication 1]: Janne I. Kokkala, Patric R. J. Östergård. Classification of Graeco-Latin cubes. Journal of Combinatorial Designs, 23, 509–521, 2015.
DOI: 10.1002/jcd.21400 View at publisher
-
[Publication 2]: Janne I. Kokkala, Denis S. Krotov, Patric R. J. Östergård. On the classification of MDS codes. IEEE Transactions on Information Theory, 61, 6485–6492, 2015.
DOI: 10.1109/TIT.2015.2488659 View at publisher
-
[Publication 3]: Janne I. Kokkala, Patric R. J. Östergård. Further results on the classification of MDS codes. Advances in Mathematics of Communications, 10, 489–498, 2016.
DOI: 10.3934/amc.2016020 View at publisher
- [Publication 4]: Janne I. Kokkala, Karen Meagher, Reza Naserasr, Kari J. Nurmela, Patric R. J. Östergård, Brett Stevens. Bounds, structure, and classification of small strength 2 covering arrays. Submitted to Electronic Journal of Combinatorics, 2017
- [Publication 5]: Janne I. Kokkala, Patric R. J. Östergård. The chromatic number of the square of the 8-cube. Accepted for publication in Mathematics of Computation, 2017