Constructing Covering Codes with Given Automorphisms |
| |
Authors: | Patric R J Osterg William D Weakley |
| |
Institution: | (1) Department of Computer Science and Engineering, Helsinki University of Technology, P. O. Box 5400, 02015 HUT, Finland;(2) Department of Mathematical Sciences, Indiana University-Purdue University Fort Wayne, Fort Wayne, Indiana, 46805 |
| |
Abstract: | Let K(n,r) denote the minimum cardinality of a binary covering code of length n and covering radius r. Constructions of covering codes give upper bounds on K(n,r). It is here shown how computer searches for covering codes can be sped up by requiring that the code has a given (not necessarily full) automorphism group. Tabu search is used to find orbits of words that lead to a covering. In particular, a code D found which proves K(13,1) 704, a new record. A direct construction of D given, and its full automorphism group is shown to be the general linear group GL(3,3). It is proved that D is a perfect dominating set (each word not in D is covered by exactly one word in D) and is a counterexample to the recent Uniformity Conjecture of Weichsel. |
| |
Keywords: | automorphism group covering code dominating set hypercube tabu search |
本文献已被 SpringerLink 等数据库收录! |
|