Permutation Groups, Error-Correcting Codes and Uncoverings
Robert F. Bailey · 2005
We replace the traditional setting for error-correcting codes (i.e. linear codes) with that of permutation groups, with permutations in list form as the codewords. We introduce a decoding algorithm for these codes, which uses the following notion. A base for a permutation group is a sequence of points whose stabiliser is trivial. An uncovering-by-bases (or UBB) is a set of bases such that any combination of error positions is avoided by at least one base in the set. In the case of sharply k-transitive groups, any k-tuple of points forms a base, so a UBB can be formed from the complements of the blocks of a covering design. (In this case, we use the term uncovering.) A large part of the thesis (chapters 2 to 5) is concerned with constructing UBBs for groups which are base-transitive, i.e. which act transitively on their irredundant bases, which were classified by T. Maund. Various combinatorial, algebraic and number-theoretic techniques are employed in this. Other topics include a case study of the Mathieu group M12, where we investigate ways in which