Computational Methods for Classification of Codes

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.