Binomial moments of the distance distribution: Bounds and applications

We study a combinatorial invariant of codes which counts the number of orde red pairs of codewords in all subcodes of restricted support in a code. Thi s invariant can be expressed as a linear form of the components of the dist ance distribution of the code with binomial numbers as coefficients. For th is reason we call it a binomial moment of the distance distribution. Binomi al moments appear in the proof of the MacWilliams identities and in many ot her problems of combinatorial coding theory. We introduce a linear programm ing problem for bounding these linear forms from below. It turns out that s ome known codes (1-error-correcting perfect codes, Golay codes, Nordstrom-R obinson code, etc.) yield optimal solutions of this problem, i.e., have min imal possible binomial moments of the distance distribution. We derive seve ral general feasible solutions of this problem, which give lower bounds on the binomial moments of codes with given parameters, and derive the corresp onding asymptotic bounds. Applications of these bounds include new lower bounds on the probability of undetected error for binary codes used over the binary-symmetric channel w ith crossover probability p and optimality of many codes for error detectio n. Asymptotic analysis of the bounds enables us to extend the range of code rates in which the upper bound on the undetected error exponent is tight.