Divisible code

Divisible code[1]

Description

A linear \(q\)-ary block code is \(\Delta\)-divisible if the Hamming weight of each of its codewords is divisible by divisor \(\Delta\). A \(2\)-divisible (\(4\)-divisible, \(8\)-divisible) code is called even (doubly even, triply even) [2,3]. A code is called singly even if all codewords are even and at least one has weight equal to 2 modulo 4. More generally, a code is \(m\)-even if it is \(2^{m}\)-divisible.

Notes

See Ref. [4] for an introduction to triply even binary linear codes and their construction from doubly even codes.Doubly even self-dual codes have been classified up to \(n\leq 40\) [5].There are ten maximal triply even codes of length 48 up to equivalence [6].

Cousins

Binary quadratic-residue (QR) code— Extended binary quadratic residue codes of length \(8m\) are self-dual doubly even codes [3; pg. 82].
\([8,4,4]\) extended Hamming code— The \([8,4,4]\) extended Hamming code code is the smallest double-even self-dual code.
Constant-weight 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.
Self-dual linear code— Binary self-dual codes are singly even, and binary self-orthogonal codes that are not doubly even are singly even [7; Def. 4.1.6]. The minimum distance of doubly even binary self-dual codes asymptotically satisfies \(d\leq0.1664n+o(n)\) [8]. Doubly even self-dual codes have been classified up to \(n\leq 40\) [5].
Ternary Golay code— Extended ternary Golay code is 3-divisible ([9], pg. 296).
Griesmer code— If a \(p\)-ary Griesmer code with \(p\) prime is such that a power of \(p\) divides the distance, then the code is divisible by that power [10].
Two-weight code— Two-weight codes are \(m\)-divisible, where \(m\) is the greatest common factor of their two possible weights.
Quantum divisible code— The \(X\)-type stabilizers of a level-\(\nu\) quantum divisible code form a \(\nu\)-even linear binary code.
\([[49,1,5]]\) triorthogonal code— The \([[49,1,5]]\) triorthogonal code stabilizer generator matrix can be obtained from a triply even linear binary code [11; Appx. B].

Member of code lists

Primary Hierarchy

Classical Domain

Galois-field Kingdom

\(q\)-ary codeECC

Additive \(q\)-ary codeECC

Linear \(q\)-ary codeECC

Parents

Linear \(q\)-ary code

Divisible code

Children

\([48,24,12]\) self-dual code

The \([48,24,12]\) self-dual code is the only self-dual doubly even code at its parameters [12].

Single parity-check (SPC) code

Binary SPCs are two-divisible.

Reed-Muller (RM) code

An RM\((r,m)\) code is \(2^{\left\lceil m/r\right\rceil-1}\)-divisible, according to McEliece's theorem [13,14].

References

[1]: H. N. Ward, “Divisible codes”, Archiv der Mathematik 36, 485 (1981) DOI
[2]: S. Kurz, “Divisible Codes”, (2023) arXiv:2112.11763
[3]: J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
[4]: K. Betsumiya and A. Munemasa, “On triply even binary codes”, Journal of the London Mathematical Society 86, 1 (2012) arXiv:1012.4134 DOI
[5]: K. Betsumiya, M. Harada, and A. Munemasa, “A complete classification of doubly even self-dual codes of length 40”, (2012) arXiv:1104.3727
[6]: K. Betsumiya and A. Munemasa, “On triply even binary codes”, Journal of the London Mathematical Society 86, 1 (2012) DOI
[7]: S. Bouyuklieva, "Self-dual codes." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[8]: I. Krasikov and S. Litsyn, “Linear programming bounds for doubly-even self-dual codes”, IEEE Transactions on Information Theory 43, 1238 (1997) DOI
[9]: J. Bierbrauer, Introduction to Coding Theory (Chapman and Hall/CRC, 2016) DOI
[10]: H. N. Ward, “Divisibility of Codes Meeting the Griesmer Bound”, Journal of Combinatorial Theory, Series A 83, 79 (1998) DOI
[11]: S. Bravyi and J. Haah, “Magic-state distillation with low overhead”, Physical Review A 86, (2012) arXiv:1209.2426 DOI
[12]: S. K. Houghten, C. W. H. Lam, L. H. Thiel, and J. A. Parker, “The extended quadratic residue code is the only (48,24,12) self-dual doubly-even code”, IEEE Transactions on Information Theory 49, 53 (2003) DOI
[13]: R. J. McEliece, “On periodic sequences from GF(q)”, Journal of Combinatorial Theory, Series A 10, 80 (1971) DOI
[14]: R. J. McEliece, “Weight congruences for p-ary cyclic codes”, Discrete Mathematics 3, 177 (1972) DOI

Page edit log

Victor V. Albert (2022-07-14) — most recent

Cite as:

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

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/q-ary_digits/weight/divisible.yml.