Description
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.
Recall that a linear code encodes a message \(h\) into a codeword \(c = hG\). The \(i\)th coordinate of a codeword is given 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 said hyperplane.
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; [2]). Multisets can also be used to construct parity-check matrices of linear codes.
Protection
Notes
Parent
- Linear \(q\)-ary code — 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).
Children
Cousins
- Evaluation code — Codewords of an evaluation code of multivariate polynomials up to degree one evaluated at points in projective space yields 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 [3; Def. 14.2.6].
- Griesmer code — Acrs corresponding to Griesmer codes are called Griesmer arcs [1; pg. 248]. There is a one-to-one correspondence between Griesmer codes and minihypers [4,5]; see [6][3; Sec. 14.2.4] for more details.
- Anticode — There is a relation between anticodes and minihypers ([7], pg. 295).
- 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)\) [3; 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 [6,8]. The dual of a MDS code is an MDS code, so MDS codes are projective.
- Ternary Golay code — The extended ternary Golay code admits a projective geometric construction ([7], pg. 296).
- Two-weight code — There are several correpondences between projective and two-weight codes [9–11].
- Cameron-Goethals-Seidel (CGS) isotropic subspace code — CSG isotropic subspace codes are constructed from incidence matrices of \(PG_5(q)\) [12; Ex. 9.4.5].
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]
- L. Storme, "Coding Theory and Galois Geometries." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [4]
- 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
- [5]
- 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.
- [6]
- 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
- [7]
- J. Bierbrauer, Introduction to Coding Theory (Chapman and Hall/CRC, 2016) DOI
- [8]
- S. M. Dodunekov and I. N. Landgev, “On near-MDS codes”, Proceedings of 1994 IEEE International Symposium on Information Theory DOI
- [9]
- A. E. Brouwer and M. van Eupen, Designs, Codes and Cryptography 11, 261 (1997) DOI
- [10]
- R. Calderbank and W. M. Kantor, “The Geometry of Two-Weight Codes”, Bulletin of the London Mathematical Society 18, 97 (1986) DOI
- [11]
- D. Jungnickel and V. D. Tonchev, “The classification of antipodal two-weight linear codes”, Finite Fields and Their Applications 50, 372 (2018) DOI
- [12]
- T. Ericson, and V. Zinoviev, eds. Codes on Euclidean spheres. Elsevier, 2001.
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