Computational Methods for Classification of Codes

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.