Constant-weight block code

Constant-weight block code[1]

Alternative names: One-weight block code.

Description

A block code whose codewords all have the same number of nonzero coordinates. Code constructions exist for codes over fields [2] or rings [3].

The set of all weight-\(w\) \(q\)-ary strings of length \(n\) forms the nonbinary Johnson space, a finite symmetric space \(G/H\) with \(G = S_{q-1} \wr S_n\) [1][4; Sec. 8.8][5; Table 3]. The number of such strings is \({n \choose w} (q-1)^w\).

Cousins

Constant-excitation (CE) code— Constant-weight codes are classical analogues of qubit constant-excitation codes.
Linear code over \(\mathbb{Z}_q\)— Constant-weight linear codes over \(\mathbb{Z}_q\) have been classified [3].
\(q\)-ary code over \(\mathbb{Z}_q\)— Optimal constant-weight codes over \(\mathbb{Z}_q\) can be constructed [6] from a generalization of combinatorial designs to \(q\)-ary alphabets [7,8].
Combinatorial design— Optimal constant-weight codes over \(\mathbb{Z}_q\) can be constructed [6] from a generalization of combinatorial designs to \(q\)-ary alphabets [7,8].
Linear \(q\)-ary code— Linear \(q\)-ary 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 code is a direct sum of \(q\)-ary simplex codes [9] (see also Refs. [10,11]).
\(q\)-ary simplex code— Linear \(q\)-ary 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 code is a direct sum of \(q\)-ary simplex codes [9] (see also Refs. [10,11]).
Two-weight code— Each codeword of a constant-weight (two-weight) code has one (two) possible Hamming weight(s).

Member of code lists

Primary Hierarchy

Classical Domain

Error-correcting code (ECC)

Block code

Parents

Block code

Symmetric-space codeECC

The set of all weight-\(w\) \(q\)-ary strings of length \(n\) forms the nonbinary Johnson space (a.k.a. \(q\)-ary Johnson space), a finite symmetric space \(G/H\) with \(G = S_{q-1} \wr S_n\) [1][4; Sec. 8.8][5; Table 3]. The number of such strings is \({n \choose w} (q-1)^w\). This reduces to the Johnson space for \(q=2\).

Constant-weight block code

Children

Constant-weight codeCombinatorial design

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}\) [12–16][5; Table 2]. This is a special case of the nonbinary Johnson space for \(q=2\).

Balanced code

References

[1]: H. Tarnanen, M. J. Aaltonen, and J.-M. Goethals, “On the Nonbinary Johnson Scheme”, European Journal of Combinatorics 6, 279 (1985) DOI
[2]: Fang-Wei Fu, A. J. Han Vinck, and Shi-Yi Shen, “On the constructions of constant-weight codes”, IEEE Transactions on Information Theory 44, 328 (1998) DOI
[3]: J. A. Wood, “The structure of linear codes of constant weight”, Transactions of the American Mathematical Society 354, 1007 (2001) DOI
[4]: T. Ceccherini-Silberstein, F. Scarabotti, and F. Tolli, Harmonic Analysis on Finite Groups (Cambridge University Press, 2008) DOI
[5]: 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
[6]: T. Etzion, “Optimal constant weight codes over Zk and generalized designs”, Discrete Mathematics 169, 55 (1997) DOI
[7]: H. Hanani, “On Some Tactical Configurations”, Canadian Journal of Mathematics 15, 702 (1963) DOI
[8]: S.-T. Xia and F.-W. Fu, “Undetected error probability of q-ary constant weight codes”, Designs, Codes and Cryptography 48, 125 (2007) DOI
[9]: Bonisoli, Arrigo. “Every equidistant linear code is a sequence of dual Hamming codes.” Ars Combinatoria 18 (1984): 181-186.
[10]: A. E.F. Jr. and H. F. Mattson, “Error-correcting codes: An axiomatic approach”, Information and Control 6, 315 (1963) DOI
[11]: E. Weiss, “Linear Codes of Constant Weight”, SIAM Journal on Applied Mathematics 14, 106 (1966) DOI
[12]: Delsarte, Philippe. “An algebraic approach to the association schemes of coding theory.” Philips Res. Rep. Suppl. 10 (1973): vi+-97.
[13]: P. Delsarte, “Association schemes and t-designs in regular semilattices”, Journal of Combinatorial Theory, Series A 20, 230 (1976) DOI
[14]: Ph. Delsarte, “Hahn Polynomials, Discrete Harmonics, andt-Designs”, SIAM Journal on Applied Mathematics 34, 157 (1978) DOI
[15]: V. I. Levenshtein, “Designs as maximum codes in polynomial metric spaces”, Acta Applicandae Mathematicae 29, 1 (1992) DOI
[16]: C. Bachoc, “Semidefinite programming, harmonic analysis and coding theory”, (2010) arXiv:0909.4767

Page edit log

Victor V. Albert (2025-10-28) — most recent

Cite as:

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

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/properties/block/q-ary_constant_weight.yml.