Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649631 | Discrete Mathematics | 2009 | 13 Pages |
Abstract
We replace the usual setting for error-correcting codes (i.e. vector spaces over finite fields) with that of permutation groups. We give an algorithm which uses a combinatorial structure which we call an uncovering-by-bases, related to covering designs, and construct some examples of these. We also analyse the complexity of the algorithm.We then formulate a conjecture about uncoverings-by-bases, for which we give some supporting evidence and prove for some special cases. In particular, we consider the case of the symmetric group in its action on 2-subsets, where we make use of the theory of graph decompositions. Finally, we discuss the implications this conjecture has for the complexity of the decoding algorithm.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Robert F. Bailey,