Constant-weight code

From Wikipedia, the free encyclopedia

 It has been suggested that M of n codes be merged into this article or section. (Discuss)

In coding theory, a constant-weight code is an error detection and correction code where all codewords share the same Hamming weight. The theory is closely connected to that of designs (such as t-designs and Steiner systems) and has several applications, including frequency hopping in GSM networks.[1] Most of the work on this very vital field of discrete mathematics is concerned with binary constant-weight codes.

[edit] A(n,d,w)

The central problem regarding constant-weight codes is the following: what is the maximum number of codewords in a binary constant-weight code with length n, Hamming distance d, and weight w? This number is called A(n,d,w).

Apart from some trivial observations, it is generally impossible to compute these numbers in a straightforward way. Upper bounds are given by several important theorems such as the first and second Johnson bounds,[2] and better upper bounds can sometimes be found in other ways. Lower bounds are most often found by exhibiting specific codes, either with use of a variety of methods from discrete mathematics, or through heavy computer searching. A large table of such record-breaking codes was published in 1990,[3] and an extension to longer codes (but only for those values of d and w which are relevant for the GSM application) was published in 2006.[1]

[edit] References

  1. ^ a b D. H. Smith, L. A. Hughes and S. Perkins (2006). "A New Table of Constant Weight Codes of Length Greater than 28". The Electronic Journal of Combinatorics 13.
  2. ^ See pp. 526–527 of F. J. MacWilliams and N. J. A. Sloane (1979). The Theory of Error-Correcting Codes. Amsterdam: North-Holland.
  3. ^ A. E. Brouwer, James B. Shearer, N. J. A. Sloane and Warren D. Smith (1990). "A New Table of Constant Weight Codes". IEEE Transactions of Information Theory 36.

[edit] External links