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

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.

Notes

See corresponding definition in MinT.

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 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

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: projective

Cite as:
“Projective geometry code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/projective
BibTeX:
@incollection{eczoo_projective, title={Projective geometry code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/projective} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/projective

Cite as:

“Projective geometry code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/projective

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/q-ary_digits/projective/projective.yml.