On the minimum average distance of binary codes: linear programming approach Original Research Article

Ahlswede and Katona posed the following average distance problem: For every n and 1⩽M⩽2n, determine the minimum average Hamming distance β(n,M) of binary codes with length n and size M. In this paper, improved lower bounds for β(n,M) are found with the help of linear programming. As a corollary, β(n,2n−2±1),β(n,2n−1+2n−2±1),β(n,2n−2),β(n,2n−1+2n−2),β(n,2n−1±2) and β(n,2n−2) are determined. Furthermore, an upper bound for β(n,M) is obtained by constructing a binary code with length n and size M. This upper bound is tight for some cases, but not in general.