Lower bounds for \(q\)-ary codes with large covering radius

Wolfgang Haas ; Immanuel Halupczok ; Jan-Christoph Schlage-Puchta

The electronic journal of combinatorics, Tome 16 (2009) no. 1

Résumé

Let $K_q(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 $K_q(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 $K_q(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 $K_q(n,R)$ for large $R$ (i.e. small $k$). One instance: the trivial sphere-covering bound $K_{12}(7,3)\geq 729$, the previously best bound $K_{12}(7,3)\geq 732$ and the new bound $K_{12}(7,3)\geq 878$.

Détail

DOI : 10.37236/222

Classification : 94B65, 94B75
Mots-clés : covering codes, lower bounds, partition matrices