Here is a list of codes related to universally optimal codes.
Code | Description | Relation |
---|---|---|
24-cell code | Spherical \((4,24,1)\) code whose codewords are the vertices of the 24-cell. Codewords form the minimal lattice-shell code of the \(D_4\) lattice. | |
600-cell code | Spherical \((4,120,(3-\sqrt{5})/2)\) code whose codewords are the vertices of the 600-cell. See [1; Table 1][2; Table 3] for realizations of the 120 codewords. A realization in terms of quaternion coordinates yields the 120 elements of the binary icosahedral group \(2I\) [3]. | |
Binary PSK (BPSK) code | Encodes one bit of information into a constellation of antipodal points \(\pm\alpha\) for complex \(\alpha\). These points are typically associated with two phases of an electromagnetic signal. | |
Biorthogonal spherical code | Spherical \((n,2n,2)\) code whose codewords are all permutations of the \(n\)-dimensional vectors \((0,0,\cdots,0,\pm1)\), up to normalization. The code makes up the vertices of an \(n\)-orthoplex (a.k.a. hyperoctahedron or cross polytope). | |
Cameron-Goethals-Seidel (CGS) isotropic subspace code | Member of a \((q(q^2-q+1),(q+1)(q^3+1),2-2/q^2)\) family of spherical codes for any prime-power \(q\). Constructed from generalized quadrangles, which in this case correspond to sets of totally isotropic points and lines in the projective space \(PG_{5}(q)\) [4; Exam. 9.4.5]. There exist multiple distinct spherical codes using this construction for \(q>3\) [5]. | |
Conference code | A member of the family of \((n,2n+2,(n-1)/2)\) nonlinear binary codes for \(n=1\) modulo 4 that are constructed from conference matrices. | |
Constant-weight code | A block code over a field or a ring whose codewords all have the same Hamming weight \(w\). The complement of a binary constant-weight code is a constant-weight code obtained by interchanging zeroes and ones in the codewords. The set of all binary codewords of length \(n\) forms the Johnson space \(J(n,w)\) [6–9]. | |
Denniston code | Projective code that is part of a family of \([2^{a+i}+2^i-2^a,3,2^{a+i}-2^a]_{GF(2^a)}\) codes for \(i < a\) constructed using Denniston arcs. | |
Extended GRS code | A GRS code with an additional parity-check coordinate with corresponding evaluation point of zero. In other words, an \([n+1,k,n-k+2]_q\) GRS code whose polynomials are evaluated at the points \((\alpha_1,\cdots,\alpha_n,0)\). The case when \(n=q-1\), multipliers \(v_i=1\), and \(\alpha_i\) are \(i-1\)st powers of a primitive \(n\)th root of unity is an extended narrow-sense RS code. | |
Five-qubit perfect code | Five-qubit cyclic stabilizer code that is the smallest qubit stabilizer code to correct a single-qubit error. | |
Generalized RS (GRS) code | An \([n,k,n-k+1]_q\) linear code that is a modification of the RS code where codeword polynomials are multiplied by additional prefactors. | |
Glynn code | The unique trace-Hermitian self-dual \([10,5,6]_9\) code, constructed using a 10-arc in \(PG(4,9)\) that is not a rational curve. | |
Griesmer code | A type of \(q\)-ary code whose parameters satisfy the Griesmer bound with equality. | |
Hadamard code | An \([2^m,m,2^{m-1}]\) balanced binary code. The \([2^m,m+1,2^{m-1}]\) augmented Hadamard code is the first-order RM code (a.k.a. RM\((1,m)\)), while the \([2^m-1,m,2^{m-1}]\) shortened Hadamard code is the simplex code (a.k.a. RM\(^*(1,m)\)). | |
Hessian polyhedron code | Spherical \((6,27,3/2)\) code whose codewords are the vertices of the Hessian complex polyhedron and the \(2_{21}\) real polytope. Two copies of the code yield the \((6,54,1)\) double Hessian polyhedron (a.k.a. diplo-Schläfli) code. The code can be obtained from the Schläfli graph [4; Ch. 9]. The (antipodal pairs of) points of the (double) Hessian polyhedron correspond to the 27 lines on a smooth cubic surface in the complex projective plane [5,10–12]. | |
Hexacode | The \([6,3,4]_4\) self-dual MDS code that has connections to projective geometry, lattices [13], and conformal field theory [14]. Puncturing the code yields the perfect \([5,3,3]_4\) quaternary Hamming code known as the shortened hexacode or shorter hexacode [15]. Both codes are sometimes refereed to as Golay codes over \(GF(4)\). | |
Hirschfeld code | A projective geometry code that is an example of an MDS code that is not an RS code; see [16; Exam. 7.6] for the description. | |
Icosahedron code | Spherical \((3,12,2-2/\sqrt{5})\) code whose codewords are the vertices of the icosahedron (alternatively, the centers of the faces of a dodecahedron, the icosahedron's dual polytope). | |
Kerdock code | Binary nonlinear \((2^m, 2^{2m}, 2^{m-1} - 2^{(m-2)/2})\) for even \(m\) consisting of the first-order Reed-Muller code RM\((1,m)\) with maximum-rank cosets of RM\((1,m)\) in RM\((2,m)\). | |
Kerdock spherical code | Family of \((n=2^{2r},n^2,2-2/\sqrt{n})\) spherical codes for \(r \geq 2\), obtained from Kerdock codes via the antipodal mapping [4; pg. 157]. These codes are optimal for their parameters for \(2\leq r\leq 5\), they are unique for \(r\in\{2,3\}\), and they form spherical 3-designs because their codewords are unions of \(2^{2r-1}+1\) cross polytopes [17]. | |
Maximum distance separable (MDS) code | A type of \(q\)-ary code whose parameters satisfy the Singleton bound with equality. | |
Narrow-sense RS code | An \([q-1,k,n-k+1]_q\) RS code whose points \(\alpha_i\) are all \((i-1)\)st powers of a primitive element \(\alpha\) of \(GF(q)\). | |
Ovoid code | Member of a \([q^2+1,4,q^2-q]_q\) projective code family that is universally optimal and that is constructed using ovoids in projective space. See [18; pg. 107][19; pg. 192] for further details. | |
Phase-shift keying (PSK) code | A \(q\)-ary phase-shift keying (\(q\)-PSK) encodes one \(q\)-ary digit of information into a constellation of \(q\) points distributed equidistantly on a circle in \(\mathbb{C}\) or, equivalently, \(\mathbb{R}^2\). | |
Polygon code | Spherical \((1,q,4\sin^2 \frac{\pi}{q})\) code for any \(q\geq1\) whose codewords are the vertices of a \(q\)-gon. Special cases include the line segment (\(q=2\)), triangle (\(q=3\)), square (\(q=4\)), pentagon (\(q=5\)), and hexagon (\(q=6\)). | |
Quadrature PSK (QPSK) code | A quaternary encoding into a constellation of four points distributed equidistantly on a circle. For the case of \(\pi/4\)-QPSK, the constellation is \(\{e^{\pm i\frac{\pi}{4}},e^{\pm i\frac{3\pi}{4}}\}\). | |
Quantum convolutional code | One-dimensional translationally invariant qubit stabilizer code whose whose stabilizer group can be partitioned into constant-size subsets of constant support and of constant overlap between neighboring sets. Initially formulated as a quantum analogue of convolutional codes, which were designed to protect a continuous and never-ending stream of information. Precise formulations sometimes begin with a finite-dimensional lattice, with the intent to take the thermodynamic limit; logical dimension can be infinite as well. | |
Quantum irregular convolutional code (QIRCC) | Quantum convolutional code whose stabilizer group consists of different constant-size subsets. | |
Quantum turbo code | A quantum version of the turbo code, obtained from an interleaved serial quantum concatenation [20; Def. 30] of quantum convolutional codes. | |
Reed-Solomon (RS) code | An \([n,k,n-k+1]_q\) linear code based on polynomials over \(GF(q)\). | |
Repetition code | \([n,1,n]\) binary linear code encoding one bit of information into an \(n\)-bit string. The length \(n\) needs to be an odd number, since the receiver will pick the majority to recover the information. The idea is to increase the code distance by repeating the logical information several times. It is a \((n,1)\)-Hamming code. Its automorphism group is \(S_n\). | |
Roth-Lempel code | Member of a \(q\)-ary linear code family that includes many examples of MDS codes that are not GRS codes. | |
Semakov-Zinoviev-Zaitsev (SZZ) equidistant code | Member of a family that is related to affine resolvable block designs and that is universally optimal. | |
Sharp configuration | A code \(C\) that attains a universal bound expressed in terms of the minimal distance, the number of distances between codewords, and the strength of the design formed by the codewords. For codes on a compact connected two-point homogeneous space, \(C\) is a design of strength \(M\) and admits \(m\) different distances between its points such that \(M \geq 2m - 1 - \delta\), where \(\delta\) is one if there are two antipodal points in \(C\) and zero otherwise [5]. | All sharp configurations are universally optimal [5,21], but not all universally optimal codes are sharp configurations. |
Simplex spherical code | Spherical \((n,n+1,2+2/n)\) code whose codewords are all permutations of the \(n+1\)-dimensional vector \((1,1,\cdots,1,-n)\), up to normalization, forming an \(n\)-simplex. Codewords are all equidistant and their components add up to zero. Simplex spherical codewords in 2 (3, 4) dimensions form the vertices of a triangle (tetrahedron, 5-cell) In general, the code makes up the vertices of an \(n\)-simplex. See [4; Sec. 7.7] for a parameterization. | |
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\). | |
Spherical sharp configuration | A spherical code that is a spherical design of strength \(2m-1\) for some \(m\) and that has \(m\) distances between distinct points. All known spherical sharp configrations are either obtained from the Leech or \(E_8\) lattice, certain regular polytopes, or are CGS isotropic subspace spherical codes [22; Table 1]. | |
Ternary Golay code | A \([11,6,5]_3\) perfect ternary linear code with connections to various areas of mathematics, e.g., lattices [13] and sporadic simple groups [23]. 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 [24]. The dual of the ternary Golay code is a \([11,5,6]_3\) projective two-weight subcode. | |
Tetracode | The \([4,2,3]_3\) ternary self-dual MDS code that has connections to lattices [13]. | |
Universally optimal \(q\)-ary code | A binary or \(q\)-ary code that (weakly) minimizes all completely monotonic potentials on Hamming space [21]. | |
Universally optimal code | A code that produces a minimum over all codes of its cardinality for a large family of potential functions. Such codes exist for the conventional \(q\)-ary and real spaces (see children below), but can also be formulated for more exotic spaces such as Lie groups, projective spaces, and real Grassmanians [25,26]. | |
Universally optimal sphere packing | A periodic sphere packing that (weakly) minimizes all completely monotonic potentials of square Euclidean distance among all periodic packings of the same density. | |
Universally optimal spherical code | A spherical code that (weakly) minimizes all completely monotonic potentials on the sphere for its cardinality. See [28][27; Sec. 12.4] for further discussion. | |
Witting polytope code | Spherical \((8,240,1)\) code whose codewords are the vertices of the Witting complex polytope, the \(4_{21}\) real polytope, and the minimal lattice-shell code of the \(E_8\) lattice. The code is optimal and unique up to equivalence [13,29,30]. Antipodal pairs of points correspond to the 120 tritangent planes of a canonic sextic curve [5,10–12]. | |
\((5,1,2)\)-convolutional code | Family of quantum convolutional codes that are 1D lattice generalizations of the five-qubit perfect code, with the former''s lattice-translation symmetry being the extension of the latter''s cyclic permutation symmetry. | |
\(3_{21}\) polytope code | Spherical \((7,56,1/3)\) code whose codewords are the vertices of the \(3_{21}\) real polytope (a.k.a. the Hess polytope). The vertices form the kissing configuration of the Witting polytope code. The code is optimal and unique up to equivalence [13,29,30]. Antipodal pairs of points correspond to the 28 bitangent lines of a general quartic plane curve [5,10–12]. | |
\(A_2\) triangular lattice | Two-dimensional lattice that corresponds to the triangular tiling and that exhibits optimal packing, solving the packing, kissing, covering and quantization problems. As a tiling, its dual (whose points lie at the centers of each triangle) is the honeycomb tiling. | |
\(ED_m\) code | Member of the family of \( (c\frac{qt-1}{(t-1,q-1)},qt,ct\frac{q-1}{(t-1,q-1)}) \) \(q\)-ary codes, where \(c,t\geq 1\) and \((a,b)\) is the greatest common divisor of \(a\) and \(b\). Such codes are universally optimal and are related to resolvable block designs. | |
\(E_8\) Gosset lattice | Unimodular even BW lattice in dimension \(8\), consisting of the Cayley integral octonions rescaled by \(\sqrt{2}\). The lattice corresponds to the \([8,4,4]\) Hamming code via Construction A. | |
\([23, 12, 7]\) Golay code | A \([23, 12, 7]\) perfect binary linear code with connections to various areas of mathematics, e.g., lattices [13] and sporadic simple groups [23]. Up to equivalence, it is unique for its parameters [24]. Shortening the Golay code yields the \([22,10,8]\), \([22,11,7]\), and \([22,12,6]\) shortened Golay codes [31]. The dual of the Golay code is its \([23,11,8]\) even-weight subcode [32,33]. | |
\([24, 12, 8]\) Extended Golay code | A self-dual \([24, 12, 8]\) code that is obtained from the Golay code by adding a parity check. Up to equivalence, it is unique for its parameters [24]. | |
\([2^m-1,m,2^{m-1}]\) simplex code | A member of the code family that is dual to the \([2^m,2^m-m-1,3]\) Hamming family. The columns of its generator matrix are in one-to-one correspondence with the elements of the projective space \(PG(m-1,2)\), with each column being a chosen representative of the corresponding element. The codewords form a \((2^m,2^m+1)\) simplex spherical code under the antipodal mapping. | |
\([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 nonzero \(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. | |
\(\Lambda_{24}\) Leech lattice | Even unimodular lattice in 24 dimensions that exhibits optimal packing. Its automorphism group is the Conway group \(.0\) a.k.a. Co\(_0\). | |
\(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. | |
\(q\)-ary repetition code | An \([n,1,n]_q\) code encoding consisting of codewords \((j,j,\cdots,j)\) for \(j \in GF(q)\). The length \(n\) needs to be an odd number, since the receiver will pick the majority to recover the information. | |
\(q\)-ary sharp configuration | A \(q\)-ary code that admits \(m\) different distances between distinct codewords and forms a design of strength \(2m-1\) or greater. | |
\(q\)-ary simplex code | An \([n,m,q^{m-1}]_q\) projective code with \(n=\frac{q^m-1}{q-1}\), denoted as \(S(q,m)\). The columns of the generator matrix are in one-to-one correspondence with the elements of the projective space \(PG(m-1,q)\), with each column being a chosen representative of the corresponding element. |
References
- [1]
- M. Waegell and P. K. Aravind, “Critical noncolorings of the 600-cell proving the Bell–Kochen–Specker theorem”, Journal of Physics A: Mathematical and Theoretical 43, 105304 (2010) arXiv:0911.2289 DOI
- [2]
- S. Mamone, G. Pileio, and M. H. Levitt, “Orientational Sampling Schemes Based on Four Dimensional Polytopes”, Symmetry 2, 1423 (2010) DOI
- [3]
- L. Rastanawi and G. Rote, “Towards a Geometric Understanding of the 4-Dimensional Point Groups”, (2022) arXiv:2205.04965
- [4]
- T. Ericson, and V. Zinoviev, eds. Codes on Euclidean spheres. Elsevier, 2001.
- [5]
- H. Cohn and A. Kumar, “Universally optimal distribution of points on spheres”, Journal of the American Mathematical Society 20, 99 (2006) arXiv:math/0607446 DOI
- [6]
- Delsarte, Philippe. "An algebraic approach to the association schemes of coding theory." Philips Res. Rep. Suppl. 10 (1973): vi+-97.
- [7]
- P. Delsarte, “Association schemes and t-designs in regular semilattices”, Journal of Combinatorial Theory, Series A 20, 230 (1976) DOI
- [8]
- Ph. Delsarte, “Hahn Polynomials, Discrete Harmonics, andt-Designs”, SIAM Journal on Applied Mathematics 34, 157 (1978) DOI
- [9]
- V. I. Levenshtein, “Designs as maximum codes in polynomial metric spaces”, Acta Applicandae Mathematicae 29, 1 (1992) DOI
- [10]
- P. du Val, “On the Directrices of a Set of Points in a Plane”, Proceedings of the London Mathematical Society s2-35, 23 (1933) DOI
- [11]
- Arnold, V. I. (1999). Symplectization, complexification and mathematical trinities. The Arnoldfest, 23-37.
- [12]
- Y.-H. He and J. McKay, “Sporadic and Exceptional”, (2015) arXiv:1505.06742
- [13]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
- [14]
- 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
- [15]
- G. Hoehn, “Self-dual Codes over the Kleinian Four Group”, (2000) arXiv:math/0005266
- [16]
- S. Ball, Finite Geometry and Combinatorial Applications (Cambridge University Press, 2015) DOI
- [17]
- H. Cohn, D. de Laat, and N. Leijenhorst, “Optimality of spherical codes via exact semidefinite programming bounds”, (2024) arXiv:2403.16874
- [18]
- R. Calderbank and W. M. Kantor, “The Geometry of Two-Weight Codes”, Bulletin of the London Mathematical Society 18, 97 (1986) DOI
- [19]
- J. Bierbrauer, Introduction to Coding Theory (Chapman and Hall/CRC, 2016) DOI
- [20]
- D. Poulin, J.-P. Tillich, and H. Ollivier, “Quantum serial turbo-codes”, (2009) arXiv:0712.2888
- [21]
- H. Cohn and Y. Zhao, “Energy-Minimizing Error-Correcting Codes”, IEEE Transactions on Information Theory 60, 7442 (2014) arXiv:1212.1913 DOI
- [22]
- H. Cohn, “Packing, coding, and ground states”, (2016) arXiv:1603.05202
- [23]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [24]
- P. Delsarte and J. M. Goethals, “Unrestricted codes with the golay parameters are unique”, Discrete Mathematics 12, 211 (1975) DOI
- [25]
- H. Cohn, A. Kumar, and G. Minton, “Optimal simplices and codes in projective spaces”, Geometry & Topology 20, 1289 (2016) arXiv:1308.3188 DOI
- [26]
- A. Glazyrin, “Moments of isotropic measures and optimal projective codes”, (2020) arXiv:1904.11159
- [27]
- P. Boyvalenkov, D. Danev, "Linear programming bounds." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [28]
- J. S. Brauchart and P. J. Grabner, “Distributing many points on spheres: Minimal energy and designs”, Journal of Complexity 31, 293 (2015) arXiv:1407.8282 DOI
- [29]
- E. Bannai and N. J. A. Sloane, “Uniqueness of Certain Spherical Codes”, Canadian Journal of Mathematics 33, 437 (1981) DOI
- [30]
- H. Cohn and A. Kumar, “Uniqueness of the (22,891,1/4) spherical code”, (2007) arXiv:math/0607448
- [31]
- 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
- [32]
- W. Feit. Some remarks on weight functions of spaces over GF(2), unpublished (1972)
- [33]
- C. L. Mallows and N. J. A. Sloane, “Weight enumerators of self-orthogonal codes”, Discrete Mathematics 9, 391 (1974) DOI