Projective geometry code
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
- \([7,4,3]\) Hamming code — The \([7,4,3]\) Hamming code parity-check matrix corresponds to points in the Fano plane \(PG_2(2)\). Columns of a general Hamming parity-check matrix correspond to one-dimensional subspaces of \(GF(2)^n\).
- Ovoid code
- Denniston code — Columns of Denniston code generator matrices represent points of a Denniston arc.
- Hill projective-cap code
- Hyperoval code
- Incidence-matrix projective code
- Simplex code — Columns of the simplex code's generator matrix are in one-to-one correspondence with elements of a projective space.
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 Ref. [3], Sec. 14.2.4 and Ref. [6] 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 [8][6]. The dual of a MDS code is an MDS code, so MDS codes are projective.
- \(q\)-ary Hamming code — Columns of a Hamming parity-check matrix correspond to one-dimensional subspaces of \(GF(q)^n\).
- Ternary Golay Code — The extended ternary Golay code admits a projective geometric construction ([7], pg. 296).
- Cameron-Goethals-Seidel (CGS) isotropic subspace code — CSG isotropic subspace codes are constructed from incidence matrices of \(PG_5(q)\) [9; 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]
- W. C. Huffman, J.-L. Kim, and P. Solé, 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]
- 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