[IEEE Trans. on Information Theory, November 2000, pp. 2373-2395]
Upper Bounds for Constant-Weight Codes
Erik Agrell, Alexander Vardy, and Kenneth Zeger
Abstract
Let A(n,d,w) denote the maximum possible number of codewords in
an (n,d,w) constant-weight binary code. We improve upon the best
known upper bounds on A(n,d,w) in numerous instances for n ≤ 24
and d ≤ 10, which is the parameter range of existing tables. Most
improvements occur for d = 8,10, where we reduce the upper bounds in
more than half of the unresolved cases. We also extend the existing
tables up to n ≤ 28 and d ≤ 14.
To obtain these results, we develop new techniques and introduce new
classes of codes. We derive a number of general bounds on A(n,d,w)
by means of mapping constant-weight codes into Euclidean space. This
approach produces, among other results, a bound on A(n,d,w) that is
tighter than the Johnson bound. A similar improvement over the best
known bounds for doubly-constant-weight codes, studied by Johnson and
Levenshtein, is obtained in the same way. Furthermore, we introduce
the concept of doubly-bounded-weight codes, which may be thought of as
a generalization of the doubly-constant-weight codes. Subsequently, a
class of Euclidean-space codes, called zonal spherical codes, is
introduced, and a bound on the size of such codes is established. This
is used to derive bounds for doubly-bounded-weight codes, which are in
turn used to derive bounds on A(n,d,w). We also develop a universal
method to establish constraints that augment the Delsarte inequalities
for constant-weight codes, used in the linear programming bound.
In addition, we present a detailed survey of known upper bounds for
constant-weight codes, and sharpen these bounds in several cases. All
these bounds, along with all knowndependencies among them, are then
combined in acoherent framework that is amenable to analysis by
computer. This improves the bounds on A(n,d,w) even further for a
large number of instances of n, d, and w.