Here is a list of universally optimal codes over various alphabets.
| Code | Description |
|---|---|
| 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 of the 600-cell can be given in terms of icosians, which are quaternion coordinates of the 120 elements of the binary icosahedral group \(2I \cong 2.A_5\) (a.k.a. the icosian group) [4][3; Ch. 8, pg. 207]. |
| 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)\) [5; Exam. 9.4.5]. There exist multiple distinct spherical codes using this construction for \(q>3\) [6,7]. |
| 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. |
| Denniston code | Projective code that is part of a family of \([2^{a+i}+2^i-2^a,3,2^{a+i}-2^a]_{2^a}\) codes for \(i < a\) constructed using Denniston arcs [8; Sec. 19.7.3]. |
| 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 [9; Def. 15.3.19]. |
| Griesmer code | A type of \(q\)-ary code whose parameters satisfy the Griesmer bound with equality. |
| Hessian polyhedron code | Spherical \((6,27,3/2)\) code whose codewords are the vertices of the Hessian complex polyhedron and the \(2_{21}\) 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 [5; Ch. 9]. The (antipodal pairs of) points of the (double) Hessian polyhedron correspond to the 27 lines on a smooth cubic surface in \(\mathbb{C}P^3\) [6,10–13]. |
| Hirschfeld code | A \([q+1,4,q-2]_q\) projective geometry code for non-prime \(q\) that is an example of an MDS code that is not an RS code; see [14; Exam. 7.6] for the generator matrix. |
| 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). |
| Maximum distance separable (MDS) code | A \(q\)-ary linear code whose parameters satisfy the Singleton bound with equality. |
| McLaughlin spherical code | The \((22,275,1/6)\) or \((23,552,1/5)\) code associated with the McLaughlin graph and the Leech lattice. See Ref. [15] for explicit constructions of and relations between both codes. |
| 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 \(\mathbb{F}_q\). |
| Ovoid code | Member of a \([q^2+1,4,q^2-q]_q\) projective two-weight code family obtained from ovoids in \(\mathrm{PG}(3,q)\). If the columns of a generator matrix are the \(q^2+1\) points of an ovoid, then every hyperplane meets the ovoid in either \(1\) or \(q+1\) points, yielding the two nonzero weights \(q^2\) and \(q^2-q\). See [16; pg. 107][17; 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}}\}\). |
| Reed-Solomon (RS) code | An \([n,k,n-k+1]_q\) linear code based on polynomials over \(\mathbb{F}_q\). |
| Repetition code | \([n,1,n]\) binary linear code encoding one bit of information into an \(n\)-bit string. Majority decoding requires \(n\) to be odd in order to avoid ties. 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 nonlinear \(q\)-ary code family that is related to affine resolvable block designs and that is universally optimal. |
| Sharp configuration | A code \(W\) in a compact connected two-point homogeneous space with \(m=l(W)\) distinct distances such that either \(r(W) \geq 2m-1\), or \(r(W)=2m-2>0\) and \(W\) is diametrical [18]. |
| 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. The union of a simplex and its antipodal simplex forms the vertices of a bi-simplex, which has \(2(n+1)\) vertices. |
| 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 configurations are either obtained from the Leech or \(E_8\) lattice, certain regular polytopes, or are CGS isotropic subspace spherical codes [19; Table 1] (see also [18; Table 9.1]). |
| Universally optimal \(q\)-ary code | A \(q\)-ary code that (weakly) minimizes all completely monotonic potentials on Hamming space [20]. Equivalently, its binomial moments are minimal among all codes with the same size and block length [20; Lemma 4]. |
| Universally optimal code | A code that minimizes, among all codes of the same cardinality, a large family of potential functions. |
| 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 [22][21; Sec. 12.4] for further discussion. In particular, all spherical sharp configurations and the 600-cell are universally optimal [6; Thm. 1.2]. |
| Witting polytope code | Spherical \((8,240,1)\) code whose codewords are the vertices of the Witting complex polytope, the \(4_{21}\) polytope, and the minimal lattice-shell code of the \(E_8\) lattice. The code is optimal and unique up to equivalence [3,23,24]. Antipodal pairs of points of the \(4_{21}\) polytope code correspond to the 120 tritangent planes of a canonical sextic curve in \(\mathbb{C}P^3\) [6,11–13]. |
| \(3_{21}\) polytope code | Spherical \((7,56,1/3)\) code whose codewords are the vertices of the \(3_{21}\) polytope (a.k.a. the Hess polytope). The vertices form the kissing configuration of the Witting polytope code. The 1-skeleton of this polytope is the Gosset graph [25]. The code is optimal and unique up to equivalence [3,23,24]. |
| \(ED_m\) code | Member of a family of nonlinear \( (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 | Even unimodular 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. |
| \([10,5,6]_9\) 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. |
| \([11,6,5]_3\) 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 [26]. Adding a parity bit to the code results in the self-dual \([12,6,6]_3\) extended ternary Golay code, whose weight enumerator is the Gleason polynomial \(g_5\) [27; Rem. 4.2.6]. Up to equivalence, both codes are unique for their respective parameters [28]. The dual of the ternary Golay code is a \([11,5,6]_3\) projective two-weight subcode [8; Exam. 19.3.2]. |
| \([23, 12, 7]\) Golay code | A \([23, 12, 7]\) perfect binary linear code with connections to various areas of mathematics, e.g., lattices [3] and sporadic simple groups [26]. Up to equivalence, it is unique for its parameters [28]. The dual of the Golay code is its \([23,11,8]\) even-weight subcode [29,30]. |
| \([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. Equivalently, puncturing any coordinate yields the \([23,12,7]\) Golay code. Up to equivalence, it is unique for its parameters [28], and it is the unique \([24,12,8]\) extremal Type II code [27; Rems. 4.3.10 and 4.3.11]. |
| \([2^m-1,m,2^{m-1}]\) simplex code | A member of the equidistant code family dual to the \([2^m-1,2^m-m-1,3]\) Hamming family. |
| \([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. |
| \([4,2,3]_3\) Tetracode | The \([4,2,3]_3\) ternary self-dual MDS code that has connections to lattices [3]. Its weight enumerator is the Gleason polynomial \(g_4\) [27; Rem. 4.2.6]. |
| \([4,2,3]_4\) RS\(_4\) code | A Type II Euclidean self-dual extended RS code that is the smallest quaternary extended QR code [26; pg. 296][31; Sec. 2.4.2]. |
| \([56,6,36]_3\) Hill-cap code | Projective two-weight ternary code based on the Games graph [32][8; Table 19.1] and Hill’s 56-cap [33]. Its automorphism group contains \(PSL(3,4)\) [34]. |
| \([6,3,4]_4\) Hexacode | The \([6,3,4]_4\) Hermitian self-dual MDS code that has connections to projective geometry, lattices [3], and conformal field theory [35]. Its weight enumerator is the Gleason polynomial \(g_7\) [27; Rem. 4.2.6]. |
| \([7,3,4]\) simplex code | Second-smallest nontrivial 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. As a simplex code, it is equidistant: every nonzero codeword has Hamming weight \(4\). |
| \([7,4,3]\) Hamming code | Second-smallest member of the Hamming code family. |
| \([78,6,56]_4\) Hill-cap code | Projective two-weight quaternary code based on a cap that corresponds to a strongly regular graph [32; Table 7.1]. |
| \([n,n-1,2]\) 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, and its parity-check matrix is a row vector of all ones. Its automorphism group is \(S_n\). |
| \([n,n-1,2]_q\) \(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. |
| \(\Lambda_{24}\) Leech lattice | Even unimodular lattice in 24 dimensions that exhibits optimal packing. Its automorphism group is the Conway group 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\) [36; (3.1)]. These are precisely the nontrivial perfect linear codes over \(\mathbb{F}_q\) [36; Thm. 3.3.1]. |
| \(q\)-ary repetition code | An \([n,1,n]_q\) code consisting of codewords \((j,j,\cdots,j)\) for \(j \in \mathbb{F}_q\). |
| \(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\) equidistant 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. All nonzero simplex codewords have a constant weight of \(q^{m-1}\) [37,38]. |
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]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
- [4]
- L. Rastanawi and G. Rote, “Towards a Geometric Understanding of the 4-Dimensional Point Groups”, (2022) arXiv:2205.04965
- [5]
- T. Ericson and V. Zinoviev, eds., Codes on Euclidean Spheres (Elsevier, 2001)
- [6]
- 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
- [7]
- H. Cohn, D. de Laat, and N. Leijenhorst, “Optimality of spherical codes via exact semidefinite programming bounds”, (2024) arXiv:2403.16874
- [8]
- A. E. Brouwer, “Two-weight Codes.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [9]
- A. Couvreur, H. Randriambololona, “Algebraic Geometry Codes and Some Applications.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [10]
- H. S. M. Coxeter, “The Polytope 2 21 Whose Twenty-Seven Vertices Correspond to the Lines to the General Cubic Surface”, American Journal of Mathematics 62, 457 (1940) DOI
- [11]
- 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
- [12]
- V. I. Arnold (1999). “Symplectization, complexification and mathematical trinities”. The Arnoldfest, 23-37
- [13]
- Y.-H. He and J. McKay, “Sporadic and Exceptional”, (2015) arXiv:1505.06742
- [14]
- S. Ball, Finite Geometry and Combinatorial Applications (Cambridge University Press, 2015) DOI
- [15]
- P. Boyvalenkov, P. Dragnev, D. Hardin, E. Saff, and M. Stoyanova, “Universal minima of discrete potentials for sharp spherical codes”, (2023) arXiv:2211.00092
- [16]
- R. Calderbank and W. M. Kantor, “The Geometry of Two-Weight Codes”, Bulletin of the London Mathematical Society 18, 97 (1986) DOI
- [17]
- J. Bierbrauer, Introduction to Coding Theory (Chapman and Hall/CRC, 2016) DOI
- [18]
- V. I. Levenshtein, “Designs as maximum codes in polynomial metric spaces”, Acta Applicandae Mathematicae 29, 1 (1992) DOI
- [19]
- H. Cohn, “Packing, coding, and ground states”, (2016) arXiv:1603.05202
- [20]
- H. Cohn and Y. Zhao, “Energy-Minimizing Error-Correcting Codes”, IEEE Transactions on Information Theory 60, 7442 (2014) arXiv:1212.1913 DOI
- [21]
- P. Boyvalenkov, D. Danev, “Linear programming bounds.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [22]
- 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
- [23]
- E. Bannai and N. J. A. Sloane, “Uniqueness of Certain Spherical Codes”, Canadian Journal of Mathematics 33, 437 (1981) DOI
- [24]
- H. Cohn and A. Kumar, “Uniqueness of the (22,891,1/4) spherical code”, (2007) arXiv:math/0607448
- [25]
- H. S. M. Coxeter, Regular Polytopes (Courier Corporation, 1973)
- [26]
- F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes (Elsevier, 1977)
- [27]
- S. Bouyuklieva, “Self-dual codes.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [28]
- P. Delsarte and J. M. Goethals, “Unrestricted codes with the golay parameters are unique”, Discrete Mathematics 12, 211 (1975) DOI
- [29]
- W. Feit. Some remarks on weight functions of spaces over GF(2), unpublished (1972)
- [30]
- C. L. Mallows and N. J. A. Sloane, “Weight enumerators of self-orthogonal codes”, Discrete Mathematics 9, 391 (1974) DOI
- [31]
- Self-Dual Codes and Invariant Theory (Springer-Verlag, 2006) DOI
- [32]
- R. A. Games, “The packing problem for projective geometries over GF(3) with dimension greater than five”, Journal of Combinatorial Theory, Series A 35, 126 (1983) DOI
- [33]
- R. Hill (1973). “On the largest size of cap in s53”. Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti, 54(3), 378-384
- [34]
- N. Pace and A. Sonnino, “On linear codes admitting large automorphism groups”, Designs, Codes and Cryptography 83, 115 (2016) DOI
- [35]
- 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
- [36]
- P. R. J. Östergård, “Construction and Classification of Codes.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [37]
- A. E.F. Jr. and H. F. Mattson, “Error-correcting codes: An axiomatic approach”, Information and Control 6, 315 (1963) DOI
- [38]
- E. Weiss, “Linear Codes of Constant Weight”, SIAM Journal on Applied Mathematics 14, 106 (1966) DOI