Computational Methods for Classification of Codes

Janne I. Kokkala

Research output: ThesisDoctoral ThesisCollection of Articles

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.
Translated title of the contributionLaskennallisia mentelmiä koodien luokitteluun
Original languageEnglish
QualificationDoctor's degree
Awarding Institution
  • Aalto University
Supervisors/Advisors
  • Östergård, Patric, Supervising Professor
Publisher
Print ISBNs978-952-60-7581-5
Electronic ISBNs978-952-60-7580-8
Publication statusPublished - 2017
MoE publication typeG5 Doctoral dissertation (article)

Keywords

  • algorithm
  • classification
  • MDS code
  • covering array
  • chromatic number

Fingerprint

Dive into the research topics of 'Computational Methods for Classification of Codes'. Together they form a unique fingerprint.

Cite this