Lower bounds on the minimum average distance of binary codes

Let β(n,M)β(n,M) denote the minimum average Hamming distance of a binary code of length nn and cardinality MM. In this paper we consider lower bounds on β(n,M)β(n,M). All the known lower bounds on β(n,M)β(n,M) are useful when MM is at least of size about 2n−1/n2n−1/n. We derive new lower bounds which give good estimations when size of MM is about nn. These bounds are obtained using a linear programming approach. In particular, it is proved that limn→∞β(n,2n)=5/2limn→∞β(n,2n)=5/2. We also give a new recursive inequality for β(n,M)β(n,M).