Search: onr:"swepub:oai:research.chalmers.se:b1ed3274-cd55-4846-a470-7f63aabbf37c" >
Upper bounds for co...
Upper bounds for constant-weight codes
-
- Agrell, Erik, 1965 (author)
- Chalmers tekniska högskola,Chalmers University of Technology
-
Vardy, Alexander (author)
-
Zeger, Kenneth (author)
-
(creator_code:org_t)
- Institute of Electrical and Electronics Engineers (IEEE), 2000
- 2000
- English.
-
In: IEEE Transactions on Information Theory. - : Institute of Electrical and Electronics Engineers (IEEE). - 0018-9448 .- 1557-9654. ; 46:7, s. 2373-2395
- Related links:
-
http://publications.... (primary) (free)
-
show more...
-
http://publications....
-
https://research.cha...
-
https://doi.org/10.1...
-
show less...
Abstract
Subject headings
Close
- 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⩽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⩽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 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.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences (hsv//eng)
Keyword
- error-control
Publication and Content Type
- art (subject category)
- ref (subject category)
Find in a library
To the university's database