On the failing cases of the Johnson bound for error-correcting codes
type: Item
instance of: scholarly article
title: On the failing cases of the Johnson bound for error-correcting codes
zbMATH Open document ID: 1206.94116
author: Wolfgang Haas
published in: The Electronic Journal of Combinatorics
publication date: 2009-04-07T00:00:00Z
full work available at URL: https://eudml.org/doc/117239
full work available at URL: v15i1r55.html
review text: Summary: A central problem in coding theory is to determine \(A_q(n,2e+1)\), the maximal cardinality of a \(q\)-ary code of length \(n\) correcting up to \(e\) errors. When \(e\) is fixed and \(n\) is large, the best upper bound for \(A(n,2e+1)\) (the binary case) is the well-known Johnson bound [\textit{S. M. Johnson}, IRE Trans. Inform. Theory IT-8, 203--207 (1962; Zbl 0102.34602)]. This however simply reduces to the sphere-packing bound if a Steiner system \(S(e+1,2e+1,n)\) exists. Despite the fact that no such system is known whenever \(e\geq 5\), they possibly exist for a set of values for \(n\) with positive density. Therefore in these cases no non-trivial numerical upper bounds for \(A(n,2e+1)\) are known. In this paper the author demonstrates a technique for upper-bounding \(A_q(n,2e+1)\), which closes this gap in coding theory. The author extends his earlier work on the system of linear inequalities satisfied by the number of elements of certain codes lying in \(k\)-dimensional subspaces of the Hamming space. The method suffices to give the first proof, that the difference between the sphere-packing bound and \(A_q(n,2e+1)\) approaches infinity with increasing \(n\) whenever \(q\) and \(e\geq 2\) are fixed. A similar result holds for \(K_q(n,R)\), the minimal cardinality of a \(q\)-ary code of length \(n\) and covering radius \(R\). Moreover the author presents a new bound for \(A(n,3)\) giving for instance \(A(19,3)\leq 26168\).
Mathematics Subject Classification ID: 94B65
Mathematics Subject Classification ID: 94B25
Mathematics Subject Classification ID: 05B07
zbMATH DE Number: 5540960
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5540960