
Accession Number : AD0681448
Title : ON UPPER BOUNDS FOR UNRESTRICTED ERROR CORRECTING CODES,
Corporate Author : RAND CORP SANTA MONICA CALIF
Personal Author(s) : Johnson,S. M.
Report Date : DEC 1968
Pagination or Media Count : 46
Abstract : The report improves the sphere packing method of establishing upper bounds to the capability of transmissionerrorcorrecting 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 grouptheoretic 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 errordetecting 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 noncode point. The new bounds are improvements over previously published results in almost all of the many cases considered. (Author)
Descriptors : (*CODING, ERRORS), INFORMATION THEORY, BINARY ARITHMETIC, COMBINATORIAL ANALYSIS, INEQUALITIES, TABLES(DATA)
Subject Categories : Cybernetics
Distribution Statement : APPROVED FOR PUBLIC RELEASE