CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Upper bounds for constant-weight codes

Erik Agrell (Institutionen för data- och elektroteknik - Chalmers Lindholmen) ; Alexander Vardy ; Kenneth Zeger
IEEE Transactions on Information Theory (0018-9448 ). Vol. 46 (2000), 7, p. 2373-2395.
[Artikel, refereegranskad vetenskaplig]

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.

Nyckelord: error-control

Denna post skapades 2006-08-29. Senast ändrad 2016-04-28.
CPL Pubid: 14986


Läs direkt!

Lokal fulltext (fritt tillgänglig)

Länk till annan sajt (kan kräva inloggning)

Institutioner (Chalmers)

Institutionen för data- och elektroteknik - Chalmers Lindholmen (1999-2004)


Information Technology

Chalmers infrastruktur