Upper bounds for constant-weight codes
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 less than or equal to 24 and d less than or equal to 12, 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 less than or equal to 28 and d less than or equal to 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 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 fdr 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 known dependencies among them, are then combined in a coherent 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.
constant-weight codes doubly-constant-weight codes doubly-bounded-weight codes zonal codes delsarte inequalities linear programming error-correcting codes spherical codes