Here is a list of projective codes.
Code | Description |
---|---|
Cycle LDPC code | An LDPC code whose parity-check matrix forms the incidence matrix of a graph, i.e., has weight-two columns. |
Cycle code | A code whose parity-check matrix forms the incidence matrix of a graph. This code's properties are derived from the size two chain complex associated with the graph. |
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. |
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. |
Hexacode | The \([6,3,4]_4\) self-dual MDS code that has connections to projective geometry, lattices [1], and conformal field theory [2]. Puncturing the code yields the perfect \([5,3,3]_4\) quaternary Hamming code known as the shortened hexacode or shorter hexacode [3]. Both codes are sometimes refereed to as Golay codes over \(GF(4)\). |
Hill projective-cap code | Member of a projective code family that contains of \(q\)-ary sharp configurations and that is constructed using projective caps. |
Hirschfeld code | A projective geometry code that is an example of an MDS code that is not an RS code; see [4; Exam. 7.6] for the description. |
Hoffman-Singleton cycle code | A \([50,21,12]\) cycle code whose parity-check matrix is the incidence matrix of the Hoffman-Singleton graph [5]. Its dual is a \([50,29,8]\) code [6; Table II]. |
Hyperoval code | A projective code constructed using hyperovals in projective space. |
Incidence-matrix projective code | Code whose generator matrix is the incidence matrix of points and hyperplanes in a projective space. Has been generalized to incidence matrices of other structures [7,8][9; Sec. 14.4]. Columns of a code's parity-check matrix can similarly correspond to an incidence matrix. |
Margulis LDPC code | Member of a class of LDPC codes deterministically constructed using an explicit class of regular graphs with no short cycles. Related explicit LDPC constructions [10] utilize Ramanujan graphs [11,12]. |
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 [13; pg. 107][14; pg. 192] for further details. |
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 [15; Appx. A.2.1]. |
Projective geometry code | Linear \(q\)-ary \([n,k,d]\) code such that columns of its generator matrix \(G\) does not contain any repeated columns or the zero column. That way, each column corresponds to a distinct point in the projective space \(PG(k-1,q)\) arising from a \(k\)-dimensional vector space over \(GF(q)\). If the columns are linearly independent, then the codewords are collectively called an information set. Columns of a code's parity-check matrix can similarly correspond to points in projective space. This formulation yields connections to projective geometry, which can be applied to determine code properties. |
Projective two-weight code | A projective code whose codewords all have one of two possible nonzero Hamming weights. |
Tetracode | The \([4,2,3]_3\) ternary self-dual MDS code that has connections to lattices [1]. |
\([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. |
\([56,6,36]_3\) Hill-cap code | Projective two-weight ternary code based on the Games graph [17][16; Table 19.1] and Hill's 56-cap [18]. Its automorphism group contains \(PSL_3(4)\) [19]. |
\([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. |
\([78,6,56]_4\) Hill-cap code | Projective two-weight quaternary code based on a cap that corresponds to a strongly regular graph [17; Table 7.1]. |
\(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]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
- [2]
- 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
- [3]
- G. Hoehn, “Self-dual Codes over the Kleinian Four Group”, (2000) arXiv:math/0005266
- [4]
- S. Ball, Finite Geometry and Combinatorial Applications (Cambridge University Press, 2015) DOI
- [5]
- A. J. Hoffman and R. R. Singleton, “On Moore Graphs with Diameters 2 and 3”, IBM Journal of Research and Development 4, 497 (1960) DOI
- [6]
- V. D. Tonchev, “Binary codes derived from the Hoffman-Singleton and Higman-Sims graphs”, IEEE Transactions on Information Theory 43, 1021 (1997) DOI
- [7]
- B. Bagchi and S. P. Inamdar, “Projective Geometric Codes”, Journal of Combinatorial Theory, Series A 99, 128 (2002) DOI
- [8]
- M. Lavrauw, L. Storme, and G. Van de Voorde (2010). Linear codes from projective spaces. In A. Bruen & D. Wehlau (Eds.), Contemporary Mathematics (Vol. 523, pp. 185–202). Providence, RI, USA: American Mathematical Society (AMS).
- [9]
- L. Storme, "Coding Theory and Galois Geometries." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [10]
- J. Rosenthal and P. O. Vontobel, “Constructions of regular and irregular LDPC codes using Ramanujan graphs and ideas from Margulis”, Proceedings. 2001 IEEE International Symposium on Information Theory (IEEE Cat. No.01CH37252) 4 DOI
- [11]
- A. Lubotzky, R. Phillips, and P. Sarnak, “Ramanujan graphs”, Combinatorica 8, 261 (1988) DOI
- [12]
- G. Davidoff, P. Sarnak, and A. Valette, Elementary Number Theory, Group Theory and Ramanujan Graphs (Cambridge University Press, 2001) DOI
- [13]
- R. Calderbank and W. M. Kantor, “The Geometry of Two-Weight Codes”, Bulletin of the London Mathematical Society 18, 97 (1986) DOI
- [14]
- J. Bierbrauer, Introduction to Coding Theory (Chapman and Hall/CRC, 2016) DOI
- [15]
- 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
- [16]
- A. E. Brouwer, "Two-weight Codes." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [17]
- 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
- [18]
- Hill, R. (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.
- [19]
- N. Pace and A. Sonnino, “On linear codes admitting large automorphism groups”, Designs, Codes and Cryptography 83, 115 (2016) DOI