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

Ahlswede and Katona posed the following average distance problem: For every n and 1 less than or equal to M less than or equal to 2(n), determine the minimum average Hamming distance beta (n,M) of binary codes with length n a nd size M. In this paper. improved lower bounds for B(n,M) are found with t he help of linear programming. As a corollary, beta (n, 2(n-2) +/- 1), beta (n, 2(n-1) + 2(n-2) +/-1), beta (n, 2(n-2)), beta (n, 2(n-1) + 2(n-2)), be ta (n, 2(n-1) +/- 2) and beta (n, 2(n) - 2) are determined. Furthermore, an upper bound for beta (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. (C) 2001 Elsevier Science B.V. All rights reserved.