Here is a list of codes related to block codes that detect or correct an error on at most two coordinates.
| Code | Description |
|---|---|
| Best \((10,40,4)\) code | Binary nonlinear \((10,40,4)\) code that is unique [1]. Under Construction A, this code yields \(P_{10c}\), a non-lattice sphere packing that is the densest known in 10 dimensions [2][3; pg. 140]. |
| Hexacode | The \([6,3,4]_4\) self-dual MDS code that has connections to projective geometry, lattices [3], and conformal field theory [4]. Puncturing the code yields the perfect \([5,3,3]_4\) quaternary Hamming code known as the shortened hexacode or shorter hexacode [5]. Both codes are sometimes refereed to as Golay codes over \(GF(4)\). |
| Julin-Golay code | One of several nonlinear binary \((12,144,4)\) codes based on the Steiner system \(S(5,6,12)\) [6,7][8; Sec. 2.7][9; Sec. 4] or their shortened versions, the nonlinear \((11,72,4)\), \((10,38,4)\), and \((9,20,4)\) Julin-Golay codes. Several of these codes contain more codewords than linear codes of the same length and distance and yield non-lattice sphere-packings that hold records in 9 and 11 dimensions. |
| Melas code | Cyclic \([2^m -1, 2^m - 1 - 2m, 5]\) linear code with generator polynomial is \(g(x) = p(x)p(x)^{\star}\), where \(p(x)\) is a primitive polynomial of degree \(m\) that is the minimal polynomial over \(GF(2)\) of an element \(\alpha\) of order \(2^m -1\) in \(GF(2^m)\), \(m\) is odd and greater that five, and '\(\star\)' denotes reciprocation [10]. |
| Nadler code | A nonlinear \((12,32,5)\) binary code that is the largest double-error-correcting code. |
| Nordstrom-Robinson (NR) code | A nonlinear \((16,256,6)\) binary code that is the smallest Kerdock and the smallest Preparata code. The size of this code is larger than the largest possible linear code with the same length and distance. |
| Pentacode | Nonlinear \((5,40,4)_{\mathbb{Z}_4}\) code over \(\mathbb{Z}_4\) whose codewords are all cyclic permutations and negations of the strings \(01112\), \(03110\), \(21310\), and \(21132\). |
| Petersen cycle code | A \([15,6,5]\) cycle code whose parity-check matrix is the incidence matrix of the Petersen graph. The Petersen graph can be thought of as a dodecahedron with antipodes identified [11; Appx. A.2.1]. |
| Preparata code | A nonlinear binary \((2^{m+1}-1, 2^{m+1}-2m-2, 5)\) code where \(m\) is odd. The size of this code is twice the size of the largest possible linear code with the same length and distance. |
| Single parity-check (SPC) code | An \([n,n-1,2]\) linear binary code whose codewords consist of the message string appended with a parity-check bit or parity bit such that the parity (i.e., sum over all coordinates of each codeword) is zero. If the Hamming weight of a message is odd (even), then the parity bit is one (zero). This code requires only one extra bit of overhead and is therefore inexpensive. Its codewords are all even-weight binary strings. Its automorphism group is \(S_n\). |
| Sloane-Whitehead code | Member of an infinite \((n,\lambda\cdot 2^{n-m-1},3)\) nonlinear code family for any \(n\) satisfying \(2^m \leq n < 3.2^{m-1}\) for some \(m\) and for \(\lambda\in\{20/16,19/16,18/16\}\). Such a code has more codewords than any linear code with the same length and distance. The code is constructed by applying the \((u|u+v)\) construction recursively to the Julin-Golay codes. |
| Small-distance block code | A block code of length \(n\) that either detects or corrects errors on at most two coordinates, i.e., has distance \(d \leq 5\). |
| Small-distance block quantum code | A block quantum code on \(n\) subsystems that either detects or corrects errors on at most two subsystems, i.e., have distance \(\leq 5\). |
| Ternary Golay code | A \([11,6,5]_3\) perfect ternary linear code with connections to various areas of mathematics, e.g., lattices [3] and sporadic simple groups [8]. Adding a parity bit to the code results in the self-dual \([12,6,6]_3\) extended ternary Golay code. Up to equivalence, both codes are unique for their respective parameters [12]. The dual of the ternary Golay code is a \([11,5,6]_3\) projective two-weight subcode. |
| Tetracode | The \([4,2,3]_3\) self-dual MDS code that has connections to lattices [3]. |
| Vasilyev code | Member of an infinite \((2^{m+1}-1,2^{2n-m},3)\) family of perfect nonlinear codes for any \(m \geq 3\). Constructed by applying a modification of the \((u|u+v)\) construction to a perfect \((2^m-1,2^{n-m},3)\) code, not necessarily linear [8; pg. 77]. |
| \([2^r,2^r-r-1,4]\) Extended Hamming code | Member of an infinite family of binary linear codes with parameters \([2^r,2^r-r-1, 4]\) for \(r \geq 2\) that are extensions of the Hamming codes by a parity-check bit. |
| \([2^r-1,2^r-r-1,3]\) Hamming code | Member of an infinite family of perfect linear codes with parameters \([2^r-1,2^r-r-1, 3]\) for \(r \geq 2\). Their \(r \times (2^r-1) \) parity-check matrix \(H\) has all possible non-zero \(r\)-bit strings as its columns. Adding a parity check yields the \([2^r,2^r-r-1, 4]\) extended Hamming code. |
| \([7,3,4]\) simplex code | Second-smallest member of the simplex code family. The columns of its generator matrix are in one-to-one correspondence with the elements of the projective space \(PG(2,2)\), with each column being a chosen representative of the corresponding element. The codewords form a \((8,9)\) simplex spherical code under the antipodal mapping. |
| \([7,4,3]\) Hamming code | Second-smallest member of the Hamming code family. |
| \([8,4,4]\) extended Hamming code | Extension of the \([7,4,3]\) Hamming code by a parity-check bit. The smallest doubly even self-dual code. |
| \(q\)-ary Hamming code | Member of an infinite family of perfect linear \(q\)-ary codes with parameters \([(q^r-1)/(q-1),(q^r-1)/(q-1)-r, 3]_q\) for \(r \geq 2\). |
| \(q\)-ary parity-check code | An \([n,n-1,2]_q\) linear \(q\)-ary code whose codewords consist of the message string appended with a parity-check or zero-sum check digit such that the sum over all coordinates of each codeword is zero. |
References
- [1]
- S. Litsyn and A. Vardy, “The uniqueness of the Best code”, IEEE Transactions on Information Theory 40, 1693 (1994) DOI
- [2]
- J. Leech and N. J. A. Sloane, “Sphere Packings and Error-Correcting Codes”, Canadian Journal of Mathematics 23, 718 (1971) DOI
- [3]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
- [4]
- J. A. Harvey and G. W. Moore, “Moonshine, superconformal symmetry, and quantum error correction”, Journal of High Energy Physics 2020, (2020) arXiv:2003.13700 DOI
- [5]
- G. Hoehn, “Self-dual Codes over the Kleinian Four Group”, (2000) arXiv:math/0005266
- [6]
- J. A. Barrau, On the combinatory problem of Steiner, Proc. Section of Sciences, Koninklijke Akademie van Wetenschappen te Amsterdam 11 (1908), 352–360.
- [7]
- J. Leech, “Some Sphere Packings in Higher Space”, Canadian Journal of Mathematics 16, 657 (1964) DOI
- [8]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [9]
- J. H. Conway and N. J. A. Sloane, “Quaternary constructions for the binary single-error-correcting codes of Julin, Best and others”, Designs, Codes and Cryptography 4, 31 (1994) DOI
- [10]
- A. Alahmadi, H. Alhazmi, T. Helleseth, R. Hijazi, N. Muthana, and P. Solé, “On the lifted Melas code”, Cryptography and Communications 8, 7 (2015) DOI
- [11]
- J. Haah, M. B. Hastings, D. Poulin, and D. Wecker, “Magic state distillation with low space overhead and optimal asymptotic input count”, Quantum 1, 31 (2017) arXiv:1703.07847 DOI
- [12]
- P. Delsarte and J. M. Goethals, “Unrestricted codes with the golay parameters are unique”, Discrete Mathematics 12, 211 (1975) DOI