Here is a list of codes related to perfect codes.
Code | Description |
---|---|
Combinatorial design | A constant-weight binary code that is mapped into a combinatorial \(t\)-design. |
Editing code | A code designed to protect against insertions, where a new symbol is added somewhere within the string, and deletions, where a symbol at an unknown location is erased. |
Golay code | A \([23, 12, 7]\) perfect binary linear code with connections to various areas of mathematics, e.g., lattices [1] and sporadic simple groups [2]. Adding a parity bit to the code results in the self-dual \([24, 12, 8]\) extended Golay code. Up to equivalence, both codes are unique for their respective parameters [3]. Shortening the Golay code yields the \([22,10,8]\), \([22,11,7]\), and \([22,12,6]\) shortened Golay codes [4]. The dual of the Golay code is its \([23,11,8]\) even-weight subcode [5,6]. |
Hexacode | The \([6,3,4]_4\) self-dual MDS code that has connections to projective geometry, lattices [1], and conformal field theory [7]. Puncturing the code yields the perfect \([5,3,3]_4\) quaternary Hamming code known as the shortened hexacode or shorter hexacode [8]. Both codes are sometimes refereed to as Golay codes over \(GF(4)\). |
Perfect binary code | An \((n,K,2t+1)\) binary code is perfect if parameters \(n\), \(K\), and \(t\) are such that the binary Hamming (a.k.a. sphere-packing) bound \begin{align} \sum_{j=0}^{t} {n \choose j} \leq 2^{n}/K \tag*{(1)}\end{align} becomes an equality. For example, for a code with one logical bit (\(K=2\)) and \(t=1\), the bound becomes \(n+1 \leq 2^{n-1}\). Perfect codes are those for which balls of Hamming radius \(t\) exactly fill the space of all \(n\) binary strings. |
Perfect code | A type of \(q\)-ary code whose parameters satisfy the Hamming bound with equality. |
Perfect quantum code | A type of block quantum code whose parameters satisfy the quantum Hamming bound with equality. |
Ternary Golay code | A \([11,6,5]_3\) perfect ternary linear code with connections to various areas of mathematics, e.g., lattices [1] and sporadic simple groups [2]. 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 [3]. 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 [1]. |
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 [2; pg. 77]. |
\([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,4,3]\) Hamming code | Second-smallest member of the Hamming code family. |
\(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\). |
References
- [1]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
- [2]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [3]
- P. Delsarte and J. M. Goethals, “Unrestricted codes with the golay parameters are unique”, Discrete Mathematics 12, 211 (1975) DOI
- [4]
- J. H. Conway and N. J. A. Sloane, “Orbit and coset analysis of the Golay and related codes”, IEEE Transactions on Information Theory 36, 1038 (1990) DOI
- [5]
- W. Feit. Some remarks on weight functions of spaces over GF(2), unpublished (1972)
- [6]
- C. L. Mallows and N. J. A. Sloane, “Weight enumerators of self-orthogonal codes”, Discrete Mathematics 9, 391 (1974) DOI
- [7]
- 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
- [8]
- G. Hoehn, “Self-dual Codes over the Kleinian Four Group”, (2000) arXiv:math/0005266