[Jump to code hierarchy]

Constant-weight code

Alternative names: One-weight code.

Description

A binary code whose codewords all have the same Hamming weight \(w\).

The complement of a constant-weight code is a constant-weight code obtained by interchanging zeroes and ones in the codewords. Constant-weight codes that contain all strings of some fixed Hamming weight are known as \(m\)-in-\(n\) or \({n \choose m}\) codes.

The set of all weight-\(w\) binary strings of length \(n\) forms the Johnson space \(J(n,w)\), a finite two-point homogeneous space \(G/H\) with \(G = S_n\) and \(H = S_w \times S_{n-q}\) [1–5][6; Table 2]. The number of such binary strings is the binomial coefficient \(n \choose w\).

Linear binary codes cannot be constant weight, but can have nonzero codewords with constant weight. All such codes are equidistant, and Bonisoli”s theorem states that any equidistant linear binary code is a direct sum of simplex codes [7] (see also Refs. [8,9]).

Protection

See Ref. [10] for upper bounds on dimension. See book [11] for (Johnson) bounds on size.

Realizations

Radio-network frequency hopping [12].

Notes

Tables of constant-weight codes for \(n \leq 28\) [13] and \(n > 28\) [12].

Cousins

  • Constant-dimension code— Codewords of length \(n\) and weight \(w\) are in one-to-one correspondence with subsets of \(n\) objects with \(w\) elements. The \(q\)-Johnson spaces generalize this notion to subspaces and reduce to Johnson spaces at \(q=1\). In other words, \((q=2)\)-Johnson space is not the same as (binary) Johnson space since the former indexes subspaces, while the latter indexes subsets.
  • Universally optimal \(q\)-ary code— See [4; Table 8.4] for constant-weight universally optimal binary codes.
  • Divisible code— Codes whose codewords have a constant weight of \(m\) are automatically \(m\)-divisible. However, divisible codes are linear by definition while constant-weight codes do not have to be.
  • Linear binary code— Linear binary codes cannot be constant weight, but can have nonzero codewords with constant weight. All such codes are equidistant, and Bonisoli’s theorem states that any equidistant linear binary code is a direct sum of simplex codes [7] (see also Refs. [8,9]).
  • \([2^m-1,m,2^{m-1}]\) simplex code— Linear binary codes cannot be constant weight, but can have nonzero codewords with constant weight. All such codes are equidistant, and Bonisoli’s theorem states that any equidistant linear binary code is a direct sum of simplex codes [7] (see also Refs. [8,9]).
  • Binary balanced spherical code— Binary balanced spherical codes are obtained from constant-weight binary codes.

Member of code lists

Primary Hierarchy

Classical Domain
Binary Kingdom
Binary codeECC
Parents
Binary code
Constant-weight block codeECC
The set of all weight-\(w\) binary strings of length \(n\) forms the Johnson space \(J(n,w)\), a finite two-point homogeneous space \(G/H\) with \(G = S_n\) and \(H = S_w \times S_{n-q}\) [1–5][6; Table 2]. This is a special case of the nonbinary Johnson space for \(q=2\).
Two-point homogeneous-space codeECC
The set of all weight-\(w\) binary strings of length \(n\) forms the Johnson space \(J(n,w)\), a finite two-point homogeneous space \(G/H\) with \(G = S_n\) and \(H = S_w \times S_{n-q}\) [1–5][6; Table 2].
Constant-weight code
Children
Combinatorial design
Weight-two code
One-hot code
One-versus-one (OVO) code

References

[1]
Delsarte, Philippe. “An algebraic approach to the association schemes of coding theory.” Philips Res. Rep. Suppl. 10 (1973): vi+-97.
[2]
P. Delsarte, “Association schemes and t-designs in regular semilattices”, Journal of Combinatorial Theory, Series A 20, 230 (1976) DOI
[3]
Ph. Delsarte, “Hahn Polynomials, Discrete Harmonics, andt-Designs”, SIAM Journal on Applied Mathematics 34, 157 (1978) DOI
[4]
V. I. Levenshtein, “Designs as maximum codes in polynomial metric spaces”, Acta Applicandae Mathematicae 29, 1 (1992) DOI
[5]
C. Bachoc, “Semidefinite programming, harmonic analysis and coding theory”, (2010) arXiv:0909.4767
[6]
C. Bachoc, D. C. Gijswijt, A. Schrijver, and F. Vallentin, “Invariant Semidefinite Programs”, International Series in Operations Research & Management Science 219 (2011) arXiv:1007.2905 DOI
[7]
Bonisoli, Arrigo. “Every equidistant linear code is a sequence of dual Hamming codes.” Ars Combinatoria 18 (1984): 181-186.
[8]
A. E.F. Jr. and H. F. Mattson, “Error-correcting codes: An axiomatic approach”, Information and Control 6, 315 (1963) DOI
[9]
E. Weiss, “Linear Codes of Constant Weight”, SIAM Journal on Applied Mathematics 14, 106 (1966) DOI
[10]
K. Zeger, A. Vardy, and E. Agrell, “Upper bounds for constant-weight codes”, IEEE Transactions on Information Theory 46, 2373 (2000) DOI
[11]
F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
[12]
D. H. Smith, L. A. Hughes, and S. Perkins, “A New Table of Constant Weight Codes of Length Greater than 28”, The Electronic Journal of Combinatorics 13, (2006) DOI
[13]
A. E. Brouwer, J. B. Shearer, N. J. A. Sloane, and W. D. Smith, “A new table of constant weight codes”, IEEE Transactions on Information Theory 36, 1334 (1990) DOI
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: constant_weight

Cite as:
“Constant-weight code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/constant_weight
BibTeX:
@incollection{eczoo_constant_weight, title={Constant-weight code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/constant_weight} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/constant_weight

Cite as:

“Constant-weight code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/constant_weight

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/bits/constant_weight/constant_weight.yml.