On Upper Bounds for Unrestricted Error Correcting Codes

摘要

The report improves the sphere packing method of establishing upper bounds to the capability of transmission-error-correcting codes. Geometric and algebraic information theory methods are used in the analysis, which applies to codes unrestricted in the sense that they need not have any group-theoretic structure. The problem is to find the maximum number of binary code words of length n such that every pair of words differs from each other in at least d positions; for d = 2e + 1, the code would correct e errors. Previously published bounding methods are shown to be special cases of a unified approach to this problem. The bounds obtained are based on consideration of the distribution of code points in the neighborhood of a fixed point; previously used inequalities are sharpened by the use of the corresponding error-detecting form, summing over only odd or only even values of the code word weights, and also by bounding the average number rather than the maximum number of code points that are closest to a particular non-code point. The new bounds are improvements over previously published results in almost all of the many cases considered. (Author)