Constant-dimension code[1]
Alternative names: Linear authentication code, Code in the \(q\)-Johnson scheme, Finite-field Grassmannian code, Grassmannian variety code, Finite Grassmannian code, Discrete Grassmannian code.
Description
A subspace code whose codewords are \(k\)-dimensional subspaces of \(GF(q)^n\) for fixed \(k\). Constant-dimension codes are equivalent to linear authentication codes [2; Thm. 4.1].
Each \(k\)-dimensional subspace of \(GF(q)^n\) is a point on the finite-field Grassmannian (a.k.a. Grassmannian variety or \(q\)-Johnson space). The number of such subspaces is a \(q\)-binomial coefficient [3][4; Sec. 8.6].
Protection
Johnson-type bounds have been developed [5].Realizations
Linear authentication [2].Cousins
- Grassmannian code— The finite-field Grassmanian is a finite analogue of the compact Grassmannians.
- Rank-metric code— Rank-metric codes can be lifted to make constant-dimension codes [6,7]; see review [3].
- Constant-weight code— Codewords of length \(n\) and weight \(w\) are in one-to-one correspondence with subsets of \(n\) objects with \(w\) elements. The \(q\)-Johnson spaces generalize this notion to subspaces and reduce to Johnson spaces at \(q=1\). In other words, \((q=2)\)-Johnson space is not the same as (binary) Johnson space since the former indexes subspaces, while the latter indexes subsets.
- Grassmannian evaluation code— Grassmannian evaluation codes are evaluation codes of polynomials evaluated on points lying on a finite-field Grassmannian embedded into projective space using the Plucker embedding [8,9].
- Projective geometry code— The projective plane \(PG(k-1,q)\) is a special case of the finite-field Grassmannian [9].
Member of code lists
Primary Hierarchy
Parents
Subspace codes of constant dimension reduce to constant-dimension codes.
The finite-field Grassmannian (a.k.a. \(q\)-Johnson space) can be regarded as a finite two-point homogeneous space \(G/H\) where \(G = GL(n,GF(q))\) [9,10][11; Table 2][12; Ch. 9][4; Sec. 8.6].
Constant-dimension code
Children
References
- [1]
- R. Koetter and F. Kschischang, “Coding for Errors and Erasures in Random Network Coding”, (2008) arXiv:cs/0703061
- [2]
- Huaxiong Wang, Chaoping Xing, and R. Safavi-Naini, “Linear authentication codes: bounds and constructions”, IEEE Transactions on Information Theory 49, 866 (2003) DOI
- [3]
- A. Khaleghi, D. Silva, and F. R. Kschischang, “Subspace Codes”, Lecture Notes in Computer Science 1 (2009) DOI
- [4]
- T. Ceccherini-Silberstein, F. Scarabotti, and F. Tolli, Harmonic Analysis on Finite Groups (Cambridge University Press, 2008) DOI
- [5]
- S.-T. Xia and F.-W. Fu, “Johnson Type Bounds on Constant Dimension Codes”, (2007) arXiv:0709.1074
- [6]
- D. Silva, F. R. Kschischang, and R. Koetter, “A Rank-Metric Approach to Error Control in Random Network Coding”, IEEE Transactions on Information Theory 54, 3951 (2008) DOI
- [7]
- F. R. Kschischang, “Network Codes.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [8]
- D. Yu. Nogin, “Codes associated to Grassmannians”, Arithmetic, Geometry, and Coding Theory DOI
- [9]
- V. Lakshmibai and J. Brown, The Grassmannian Variety (Springer New York, 2015) DOI
- [10]
- C. Bachoc, “Semidefinite programming, harmonic analysis and coding theory”, (2010) arXiv:0909.4767
- [11]
- C. Bachoc, D. C. Gijswijt, A. Schrijver, and F. Vallentin, “Invariant Semidefinite Programs”, International Series in Operations Research & Management Science 219 (2011) arXiv:1007.2905 DOI
- [12]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
Page edit log
- Victor V. Albert (2025-10-23) — most recent
Cite as:
“Constant-dimension code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2025. https://errorcorrectionzoo.org/c/finite_grassmann