tailieunhanh - Báo cáo toán học: "Lower Bounds for q-ary Codes with Large Covering Radius"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Lower Bounds for q-ary Codes with Large Covering Radius. | Lower Bounds for q-ary Codes with Large Covering Radius Wolfgang Haas Immanuel Halupczok Jan-Christoph Schlage-Puchta Albert-Ludwigs-Universitat Mathematisches Institut Eckerstr. 1 79104 Freiburg Germany wolfgang_haas@ math@ j csp@ Submitted Jan 12 2009 Accepted Oct 27 2009 Published Nov 7 2009 Mathematics Subject Classification 94B65 Abstract Let Kq n R denote the minimal cardinality of a q-ary code of length n and covering radius R. Recently the authors gave a new proof of a classical lower bound of Rodemich on Kq n n 2 by the use of partition matrices and their transversals. In this paper we show that in contrast to Rodemich s original proof the method generalizes to lower-bound Kq n n k for any k 2. The approach is best-understood in terms of a game where a winning strategy for one of the players implies the non-existence of a code. This proves to be by far the most efficient method presently known to lower-bound Kq n R for large R . small k . One instance the trivial sphere-covering bound K12 7 3 729 the previously best bound K12 7 3 732 and the new bound K12 7 3 878. Keywords covering codes lower bounds partition matrices. The second author was supported by the Fondation Sciences mathematiques de Paris. THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 R133 1 1 Introduction Let q 2 and Zq 0 1 . q 1 . The Hamming distance d x y between x xo . Xn-1 G zq and y yo . yn-1 G zq is defined by d x y i G 0 . . n 1 Xi yi . We say C c zq is a q-ary code of length n and covering radius at most R if Vx G zq 3y G C with d x y R 1 is satisfied. Let Kq n R denote the minimal cardinality of a q-ary code of length n and covering radius R. For a monograph on covering codes see 2 . An updated table of bounds on Kq n R is published online by Keri 5 . An easy lower bound on Kq n R is the sphere-covering bound z _ . qn KqR V R 2 where C Vq n R y G zq d y x Í R w n q I i 0 i R denotes the cardinality of a Hamming-sphere with radius R centered on an .