Haas, Wolfgang

On the failing cases of the Johnson bound for error-correcting codes

Electron. J. Comb. 15(1), Research Paper R55, 13 p. (2008)


Summary: A central problem in coding theory is to determine $Aq(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 from 1962. 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.

Mathematics Subject Classification

94B25, 94B65