Description
Linear \(q\)-ary \([n,k,d]\) code such that columns of its generator matrix \(G\) do 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 \(\mathbb{F}_q\). A choice of \(k\) linearly independent columns determines 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.
Recall that a linear code encodes a message \(h\) into a codeword \(c = hG\). The \(i\)th coordinate of a codeword is given by the dot product \(h \cdot G_{i}\), with \(G_{i}\) being the \(i\)th column of the generator matrix. The zero-coordinate condition \(h \cdot x = 0\) defines a hyperplane of points \(x\) with normal vector \(h\). Therefore, the Hamming weight of the corresponding codeword is the number of points \(G_i\) not contained in that hyperplane.
In general, linear codes can admit repeated columns or columns proportional to each other. In that case, the columns correspond to a multiset of not-necessarily-distinct nonzero points of projective space [1,2]. Multisets can also be used to construct parity-check matrices of linear codes.
Protection
Distance \(d\) is \(n\) minus the maximum number of points that are contained in a hyperplane. For \(n \geq 3\), a code is projective if and only if the distance of its dual code is at least three.
The weight enumerator of the code comes from the Tutte polynomial associated with the projective code [3].
Notes
See corresponding definition in MinT.Cousins
- Cyclic linear \(q\)-ary code— Every projective linear code is a punctured code of a special cyclic code [4; Thm. 2.3.6].
- Evaluation code— Codewords of an evaluation code of multivariate polynomials up to degree one evaluated at points in projective space yield a projective code.
- Extended GRS code— Columns of parity-check matrices of doubly extended narrow-sense RS codes consist of points of a normal rational curve [5; Def. 14.2.6].
- Narrow-sense RS code— Columns of parity-check matrices of doubly extended narrow-sense RS codes consist of points of a normal rational curve [5; Def. 14.2.6].
- Griesmer code— Arcs corresponding to Griesmer codes are called Griesmer arcs [1; pg. 248]. There is a one-to-one correspondence between Griesmer codes and minihypers [6,7]; see [8][5; Sec. 14.2.4] for more details.
- Anticode— There is a relation between anticodes and minihypers [9; pg. 295].
- Constant-dimension code— The projective plane \(PG(k-1,q)\) is a special case of the finite-field Grassmannian [10].
- Subspace code— Subspace codes are sets of subspaces of a projective space \(PG(n-1,q)\).
- Projective RM (PRM) code— Nonzero codewords of minimum weight of a \(r\)th-order \(q\)-ary projective RM code correspond to algebraic hypersurfaces of degree \(r\) having the largest number of points in the projective space \(PG(n,q)\) [5; Thm. 14.3.3].
- Maximum distance separable (MDS) code— A linear code is MDS (almost MDS) if and only if columns of its parity-check matrix form an \(n\)-arc (\(n\)-track) in projective space [8,11–13]. The dual of a MDS code is an MDS code, so MDS codes are projective. All \([9,3]\) MDS codes have been tabulated [14] in terms of 9-arcs in the projective plane.
- \([11,6,5]_3\) Ternary Golay code— The extended ternary Golay code admits a projective geometric construction [9; pg. 296].
- \(q\)-ary duadic code— The weight-five codewords of the \([21,5,6]_4\) quaternary duadic code support a projective plane of order 4 [15; Table 6.3].
- Two-weight code— Projective two-weight codes correspond to projective 2-character sets and certain strongly regular graphs, and arbitrary projective codes are in 1-1 correspondence with arbitrary two-weight codes [17–19][16; Sec. 19.3.3][16; Sec. 19.9.1].
- Octacode— Columns of the heptacode’s (octacode’s) generator matrix represent the seven (eight) points of a hyperoval (8-arc) in the projective Hjelmslev plane \(PHG(2,\mathbb{Z}_4)\) (\(PHG(3,\mathbb{Z}_4)\)) [21][20; Exam. 5].
- Cameron-Goethals-Seidel (CGS) isotropic subspace code— CGS isotropic subspace codes are constructed from incidence matrices of \(PG(5,q)\) [22; Exam. 9.4.5].
- \([[n,n-2k,4]]\) Quantum cap code— A quantum cap code is a distance-four pure Hermitian qubit code constructed by identifying its underlying Hermitian self-orthogonal \([n,k]_4\) code with a particular projective cap in \(PG(k-1,4)\).
- \([[2^r, 2^r-r-2, 3]]\) Gottesman code— Gottesman codes are related to partial spreads in projective geometry [23].
- \([[9,3,3]]\) Quadric code— The \([[9,3,3]]\) quadric code can be constructed from the elliptic quadric in \(PG(5, 2)\) [23].
- Hermitian qubit code— There is an equivalence between pure \([[n,n-2k]]\) Hermitian qubit codes and certain sets of points in projective space \(PG(k-1,4)\) [23; Thm. 2.8].
- Purity-testing stabilizer code— Purity-testing stabilizer codes are constructed from normal rational curves.
- Finite-geometry (FG) qubit QLDPC code— PG-QLDPC codes are constructed from linear binary codes whose parity-check or generator matrices are incidence matrices of structures in finite geometries.
- Qubit stabilizer code— \([[n,k,d]]\) qubit stabilizer codes with no weight-one stabilizers are equivalent to particular “quantum” sets of lines in projective space \(PG(n-k-1,2)\) [25,26][24; Thm. 3.7]. This equivalence is stated in the case of pure qubit stabilizer codes with distance two or greater in [23; Thm. 2.6].
- Galois-qudit USt code— Galois-qudit USt codes can be obtained from lines in projective space [26,27].
Primary Hierarchy
Parents
Columns of the generator matrix of a projective linear \([n,k]_q\) code correspond to distinct nonzero points in projective space. In general, linear codes admit repeating columns or columns proportional to each other. In that case, the columns correspond to a multiset of non-distinct nonzero points, and multisets are in one-to-one correspondence to arcs in projective space [1; Thm. 1.1].
Projective geometry code
Children
Incidence matrices of graphs have no repeated columns since that would correspond to multi-edges. Therefore, cycle codes can be interpreted as projective codes.
Incidence matrices of graphs have no repeated columns since that would correspond to multi-edges. Therefore, Laplacian codes can be interpreted as projective codes.
The Glynn code is constructed using a 10-arc in \(PG(4,9)\) that is not a rational curve.
Projective two-weight codes are projective codes by definition [16; Sec. 19.2] (see also [17–19]).
References
- [1]
- I. N. Landjev, “The Geometric Approach to Linear Codes”, Developments in Mathematics 247 (2001) DOI
- [2]
- I. N. Landjev, “Linear codes over finite fields and finite projective geometries”, Discrete Mathematics 213, 211 (2000) DOI
- [3]
- C. Greene, “Weight Enumeration and the Geometry of Linear Codes”, Studies in Applied Mathematics 55, 119 (1976) DOI
- [4]
- C. Ding, “Cyclic Codes over Finite Fields.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [5]
- L. Storme, “Coding Theory and Galois Geometries.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [6]
- N. Hamada and M. Deza, “A characterization of νμ + 1 + ε, νμ; t, q-min.hypers and its applications to error-correcting codes and factorial designs”, Journal of Statistical Planning and Inference 22, 323 (1989) DOI
- [7]
- N. Hamada, Characterization of minihypers in a finite projective geometry and its applications to error-correcting codes, Bull. Osaka Women’s Univ. 24 (1987), 1-24.
- [8]
- J. W. P. Hirschfeld and L. Storme, “The Packing Problem in Statistics, Coding Theory and Finite Projective Spaces: Update 2001”, Developments in Mathematics 201 (2001) DOI
- [9]
- J. Bierbrauer, Introduction to Coding Theory (Chapman and Hall/CRC, 2016) DOI
- [10]
- V. Lakshmibai and J. Brown, The Grassmannian Variety (Springer New York, 2015) DOI
- [11]
- R. C. Bose (1947). Mathematical theory of the symmetrical factorial design. Sankhyā: The Indian Journal of Statistics, 107-166.
- [12]
- S. M. Dodunekov and I. N. Landgev, “On near-MDS codes”, Proceedings of 1994 IEEE International Symposium on Information Theory 427 DOI
- [13]
- A. Beutelspacher and U. Rosenbaum. Projective geometry: from foundations to applications. Cambridge University Press, 1998.
- [14]
- A. V. Iampolskaia, A. N. Skorobogatov, and E. A. Sorokin, “Formula for the number of [9,3] MDS codes”, IEEE Transactions on Information Theory 41, 1667 (1995) DOI
- [15]
- W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
- [16]
- A. E. Brouwer, “Two-weight Codes.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [17]
- A. E. Brouwer and M. van Eupen, Designs, Codes and Cryptography 11, 261 (1997) DOI
- [18]
- R. Calderbank and W. M. Kantor, “The Geometry of Two-Weight Codes”, Bulletin of the London Mathematical Society 18, 97 (1986) DOI
- [19]
- D. Jungnickel and V. D. Tonchev, “The classification of antipodal two-weight linear codes”, Finite Fields and Their Applications 50, 372 (2018) DOI
- [20]
- M. Shi, T. Honold, P. Sole, Y. Qiu, R. Wu, and Z. Sepasdar, “The Geometry of Two-Weight Codes Over ℤ\({}_{\text{\textit{p}}}\)\({}^{\text{\textit{m}}}\)”, IEEE Transactions on Information Theory 67, 7769 (2021) DOI
- [21]
- T. Honold and I. Landjev, “Linear Codes over Finite Chain Rings and Projective Hjelmslev Geometries”, Codes Over Rings 60 (2009) DOI
- [22]
- T. Ericson, and V. Zinoviev, eds. Codes on Euclidean spheres. Elsevier, 2001.
- [23]
- J. Bierbrauer, G. Faina, M. Giulietti, S. Marcugini, and F. Pambianco, “The geometry of quantum codes”, Innovations in Incidence Geometry: Algebraic, Topological and Combinatorial 6, 53 (2008) DOI
- [24]
- S. Ball, A. Centelles, and F. Huber, “Quantum error-correcting codes and their geometries”, Annales de l’Institut Henri Poincaré D, Combinatorics, Physics and their Interactions 10, 337 (2023) arXiv:2007.05992 DOI
- [25]
- D. G. Glynn, T. A. Gulliver, J. G. Maks, and M. K. Gupta, “The geometry of additive quantum codes.” submitted to Springer-Verlag (2004).
- [26]
- S. Ball and P. Puig, “The geometry of non-additive stabiliser codes”, (2021) arXiv:2107.11281
- [27]
- S. Ball, “Stabiliser codes and quantum sets of lines.” Finite Geometries Sixth Irsee Conference. 2022.
Page edit log
- Victor V. Albert (2022-08-09) — most recent
Cite as:
“Projective geometry code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/projective