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. | |
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. | |
Golay code | A \([23, 12, 7]\) perfect binary linear code with connections to various areas of mathematics, e.g., lattices [10] and sporadic simple groups [11]. 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 [12]. Shortening the Golay code yields the \([22,10,8]\), \([22,11,7]\), and \([22,12,6]\) shortened Golay codes [13]. The dual of the Golay code is its \([23,11,8]\) even-weight subcode [14,15]. | |
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,16–18]. | |
Hexacode | The \([6,3,4]_4\) self-dual MDS code that has connections to projective geometry, lattices [10], and conformal field theory [19]. Puncturing the code yields the perfect \([5,3,3]_4\) quaternary Hamming code known as the shortened hexacode or shorter hexacode [20]. 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 [21; 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 [22]. | |
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 [23; pg. 107][24; 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 \(GF(q)\). | |
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,25], 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 [26; Table 1]. | |
Ternary Golay code | A \([11,6,5]_3\) perfect ternary linear code with connections to various areas of mathematics, e.g., lattices [10] and sporadic simple groups [11]. 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 [10]. | |
Universally optimal \(q\)-ary code | A binary or \(q\)-ary code that (weakly) minimizes all completely monotonic potentials on binary space [25]. | |
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 [27,28]. | |
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 [30][29; 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 [10,31,32]. Antipodal pairs of points correspond to the 120 tritangent planes of a canonic sextic curve [5,16–18]. | |
\(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 [10,31,32]. Antipodal pairs of points correspond to the 28 bitangent lines of a general quartic plane curve [5,16–18]. | |
\(A_2\) hexagonal lattice | Two-dimensional lattice that exhibits optimal packing, solving the packing, kissing, covering and quantization problems. Its dual is the honeycomb lattice. The ruby lattice is a fattened honeycomb lattice interpolating between the honeycomb and hexagonal lattices. | |
\(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. | |
\([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 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. | |
\(\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]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
- [11]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [12]
- P. Delsarte and J. M. Goethals, “Unrestricted codes with the golay parameters are unique”, Discrete Mathematics 12, 211 (1975) DOI
- [13]
- 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
- [14]
- W. Feit. Some remarks on weight functions of spaces over GF(2), unpublished (1972)
- [15]
- C. L. Mallows and N. J. A. Sloane, “Weight enumerators of self-orthogonal codes”, Discrete Mathematics 9, 391 (1974) DOI
- [16]
- 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
- [17]
- Arnold, V. I. (1999). Symplectization, complexification and mathematical trinities. The Arnoldfest, 23-37.
- [18]
- Y.-H. He and J. McKay, “Sporadic and Exceptional”, (2015) arXiv:1505.06742
- [19]
- 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
- [20]
- G. Hoehn, “Self-dual Codes over the Kleinian Four Group”, (2000) arXiv:math/0005266
- [21]
- S. Ball, Finite Geometry and Combinatorial Applications (Cambridge University Press, 2015) DOI
- [22]
- H. Cohn, D. de Laat, and N. Leijenhorst, “Optimality of spherical codes via exact semidefinite programming bounds”, (2024) arXiv:2403.16874
- [23]
- R. Calderbank and W. M. Kantor, “The Geometry of Two-Weight Codes”, Bulletin of the London Mathematical Society 18, 97 (1986) DOI
- [24]
- J. Bierbrauer, Introduction to Coding Theory (Chapman and Hall/CRC, 2016) DOI
- [25]
- H. Cohn and Y. Zhao, “Energy-Minimizing Error-Correcting Codes”, IEEE Transactions on Information Theory 60, 7442 (2014) arXiv:1212.1913 DOI
- [26]
- H. Cohn, “Packing, coding, and ground states”, (2016) arXiv:1603.05202
- [27]
- H. Cohn, A. Kumar, and G. Minton, “Optimal simplices and codes in projective spaces”, Geometry & Topology 20, 1289 (2016) arXiv:1308.3188 DOI
- [28]
- A. Glazyrin, “Moments of isotropic measures and optimal projective codes”, (2020) arXiv:1904.11159
- [29]
- P. Boyvalenkov, D. Danev, "Linear programming bounds." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [30]
- 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
- [31]
- E. Bannai and N. J. A. Sloane, “Uniqueness of Certain Spherical Codes”, Canadian Journal of Mathematics 33, 437 (1981) DOI
- [32]
- H. Cohn and A. Kumar, “Uniqueness of the (22,891,1/4) spherical code”, (2007) arXiv:math/0607448