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

The weight enumerator of the code comes from the Tutte polynomial associated with the projective code [3].

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 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 [4; 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 [4; 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 [5,6]; see [7][4; Sec. 14.2.4] for more details.
  • Anticode — There is a relation between anticodes and minihypers ([8], 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)\) [4; Thm. 14.3.3].
  • Subspace code — Subspace codes are sets of subspaces of a projective space \(PG(n-1,q)\).
  • 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 [7,9–11]. The dual of a MDS code is an MDS code, so MDS codes are projective. All \([[9,3]]\) MDS codes have been tabulated [12] in terms of 9-arcs in the projective plane.
  • Ternary Golay code — The extended ternary Golay code admits a projective geometric construction ([8], pg. 296).
  • Two-weight code — There are several correpondences between projective and two-weight codes [13–15].
  • Cameron-Goethals-Seidel (CGS) isotropic subspace code — CSG isotropic subspace codes are constructed from incidence matrices of \(PG_5(q)\) [16; Ex. 9.4.5].
  • Purity-testing stabilizer code — Purity-testing stabilizer codes are constructed from normal rational curves.
  • Finite-geometry (FG) 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.

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]
L. Storme, "Coding Theory and Galois Geometries." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[5]
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
[6]
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.
[7]
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
[8]
J. Bierbrauer, Introduction to Coding Theory (Chapman and Hall/CRC, 2016) DOI
[9]
R. C. Bose (1947). Mathematical theory of the symmetrical factorial design. Sankhyā: The Indian Journal of Statistics, 107-166.
[10]
S. M. Dodunekov and I. N. Landgev, “On near-MDS codes”, Proceedings of 1994 IEEE International Symposium on Information Theory DOI
[11]
Beutelspacher, Albrecht, and Ute Rosenbaum. Projective geometry: from foundations to applications. Cambridge University Press, 1998.
[12]
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
[13]
A. E. Brouwer and M. van Eupen, Designs, Codes and Cryptography 11, 261 (1997) DOI
[14]
R. Calderbank and W. M. Kantor, “The Geometry of Two-Weight Codes”, Bulletin of the London Mathematical Society 18, 97 (1986) DOI
[15]
D. Jungnickel and V. D. Tonchev, “The classification of antipodal two-weight linear codes”, Finite Fields and Their Applications 50, 372 (2018) DOI
[16]
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)— see instructions

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/edit/main/codes/classical/q-ary_digits/projective/projective.yml.