A new upper bound for error-correcting codes

Abstract

By refining Hamming's geometric sphere-packing model a new upper bound for nonsystematic binary error-correcting codes is found. Only combinatorial arguments are used. Whereas Hamming's upper bound estimate for <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">e</tex> -error-correcting codes involved a count of all points <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">\leq e</tex> Hamming distance from the set of code points, the model is extended here to include consideration of points which are <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;e</tex> distance away from the code set. The percentage improvement from Hamming's bounds is sometimes quite sizable for cases of two or more errors to be corrected. The new bound improves on Wax's bounds in all but four of the cases he lists.