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) code is called even (doubly-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.
Notes
See Ref. [4] for an introduction to triply-even binary linear codes and their construction from doubly-even codes.
Parent
Children
- 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 [5,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 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].
- 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 — Quantum divisible codes are constructed via the CSS construction using a divisible linear binary code.
- Doubled color code — Doubled color codes are constructed using a generalization of the doubling transformation [4] that combine doubly-even codes to make triply-even codes.
References
- [1]
- H. N. Ward, “Divisible codes”, Archiv der Mathematik 36, 485 (1981) DOI
- [2]
- S. Kurz, “Divisible Codes”, (2022) 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]
- R. J. McEliece, “On periodic sequences from GF(q)”, Journal of Combinatorial Theory, Series A 10, 80 (1971) DOI
- [6]
- R. J. McEliece, “Weight congruences for p-ary cyclic codes”, Discrete Mathematics 3, 177 (1972) 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
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