Upper bounds for constant-weight codes
Upper bounds for constant-weight codes
复制标题
DOI：
10.1109/18.887851
复制
发表时间：
2000-11
期刊：
影响因子：
--
通讯作者：
E. Agrell;A. Vardy;K. Zeger
中科院分区：
文献类型：
--
作者：
E. Agrell;A. Vardy;K. Zeger
设A（n,d,w）表示一个（n,d,w）等权二进制码中码字的最大可能数目。在n/spl les/24和d/spl les/12的许多情况下，我们改进了已知的A（n,d,w）的上界，这是现有表的参数范围。大多数改进发生在d= 8,10时，其中我们减少了一半以上未解决情况的上界。我们还将现有的表扩展到n/spl les/28和d/spl les/14。为了获得这些结果，我们开发了新的技术并引入了新的代码类。通过将等权码映射到欧几里得空间，导出了a （n,d,w）上的若干一般界。这种方法产生了一个比Johnson界更紧的a （n,d,w）界。Johnson和Levenshtein用同样的方法对双等权码的已知界进行了类似的改进。进一步，我们引入了双有界权码的概念，它可以被认为是双等权码的推广。随后，引入了一类称为区域码的欧几里得空间码，并建立了这类码的大小界。这用于推导双有界权码的边界，而双有界权码又用于推导A（n,d,w）的边界。我们还开发了一种通用的方法来建立约束，增加了线性规划界中使用的等权码的Delsarte不等式。此外，我们还详细调查了已知的等权码的上界，并在一些情况下锐化了这些上界。所有这些边界，以及它们之间所有已知的依赖关系，然后被组合在一个连贯的框架中，该框架可用于计算机分析。这进一步提高了A（n,d,w）对于大量n，d和w实例的边界。
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/spl les/24 and d/spl les/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/spl les/28 and d/spl les/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 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 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.