Lower bounds on covering codes via partition matrices

DOI10.1016/J.JCTA.2008.06.008MaRDI QIDQ1003655zbMATH OpenOpenAlexFDO

Authors Wolfgang Haas, Jan-Christoph Schlage-Puchta, Jörn Quistorff

Publication date 4 March 2009

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcta.2008.06.008

zbMATH Keywords

covering codespartition matricesRodemich boundsurjective codes

Mathematics Subject Classification ID

Combinatorial codes (94B25) Bounds on codes (94B65) Applications of the theory of convex sets and geometry of numbers (covering radius, etc.) to coding theory (94B75)

Review text

The minimum cardinality of a \(q\)-ary code of length \(n\) and covering radius \(R\) is denoted by \(K_q(n,R)\). By utilizing the framework of partition matrices [\textit{W. Benz}, Combinatorics '90, Proc. Conf., Gaeta/Italy 1990, Ann. Discrete Math. 52, 25--36 (1992; Zbl 0768.51012)] the authors obtain general lower bounds on \(K_q(n,n-2)\), improving on the bound by \textit{E. R. Rodemich} [J. Comb. Theory 9, 117--128 (1970; Zbl 0219.05013)] in several cases. The following new bound is also proved: \(K_{q+1}(n+1,R+1) \geq \min\{2(q+1),K_q(n,R)+1\}\). The authors tabulate 36 explicit new lower bounds on \(K_q(n,R)\) for \(5 \leq q \leq 21\), \(5 \leq n \leq 10\), and \(n-3 \leq R \leq n-2\).

Recommendations

• Lower bounds for q-ary codes with large covering radius
• Lower bounds for q-ary covering codes
• Lower bounds for q-ary codes of covering radius one
• On lower bounds for covering codes
• New lower bounds for covering codes

Cites work

• A note on bounds for q-ary covering codes
• Bounds for covering codes over large alphabets
• Coverings by rook domains
• Families of \(k\)-independent sets
• Further results on the covering radius of small codes
• scientific article; zbMATH DE number 140042 (Why is no real title available?)
• scientific article; zbMATH DE number 645821 (Why is no real title available?)
• scientific article; zbMATH DE number 1024657 (Why is no real title available?)
• On the covering radius of small codes

Cited in

(6)

• Lower bounds for q-ary codes with large covering radius
• Invariant sets under linear operator and covering codes over modules
• Hypercube packings and coverings with higher dimensional rooks
• On generalized surjective codes
• The covering problem in Rosenbloom-Tsfasman spaces
• Bounds for short covering codes and reactive tabu search

This page was built for publication: Lower bounds on covering codes via partition matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1003655)