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

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.