[Jump to code hierarchy]

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 \(\mathbb{F}_q^n\) for fixed \(k\). Constant-dimension codes are equivalent to linear authentication codes [2; Thm. 4.1].

Each \(k\)-dimensional subspace of \(\mathbb{F}_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]. Optimal FDRM codes in the multilevel construction [6], in some cases with pending blocks [7,8], improve the best known lower bounds on code size for several parameters [9]. One such case is codes of \(7\)-dimensional subspaces of \(\mathbb{F}_q^{n}\) with \(n\in\{17,18,19\}\), subspace distance \(6\), and \(q\geq 3\) [9; Cor. 1].

Realizations

Linear authentication [2].

Notes

See Ref. [10] for tables of the best known bounds on the sizes of constant-dimension codes.

Cousins

  • Grassmannian code— The finite-field Grassmannian is a finite analogue of the compact Grassmannians.
  • Rank-metric code— Rank-metric codes can be lifted to make constant-dimension codes [11,12]; 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.
  • Ferrers diagram rank-metric (FDRM) code— The multilevel construction lifts an FDRM code on the echelon-form diagram of each identifying vector of a binary constant-weight code [6]. When the identifying vectors have pairwise Hamming distance at least \(2\delta\) and the FDRM codes have rank distance \(\delta\), the union of the lifted codes has subspace distance \(2\delta\) [6].
  • Grassmannian evaluation code— Grassmannian evaluation codes and constant-dimension codes are both built from the finite-field Grassmannian: the former evaluate functions on its points, while the latter use its \(k\)-dimensional subspaces themselves as codewords [13,14].
  • Projective geometry code— The projective plane \(PG(k-1,q)\) is a special case of the finite-field Grassmannian [14].

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,\mathbb{F}_q)\) [14][15; Sec. 4.2.1][16; Table 2][17; Ch. 9][4; Sec. 8.6].
Constant-dimension code
Children

References

  1. [1]

    R. Koetter and F. Kschischang, “Coding for Errors and Erasures in Random Network Coding”, (2008) arXiv:cs/0703061

  2. [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. [3]

    A. Khaleghi, D. Silva, and F. R. Kschischang, “Subspace Codes”, Lecture Notes in Computer Science 1 (2009) DOI

  4. [4]

    T. Ceccherini-Silberstein, F. Scarabotti, and F. Tolli, Harmonic Analysis on Finite Groups (Cambridge University Press, 2008) DOI

  5. [5]

    S.-T. Xia and F.-W. Fu, “Johnson Type Bounds on Constant Dimension Codes”, (2007) arXiv:0709.1074

  6. [6]

    T. Etzion and N. Silberstein, “Error-Correcting Codes in Projective Spaces via Rank-Metric Codes and Ferrers Diagrams”, (2009) arXiv:0807.4846

  7. [7]

    N. Silberstein and A.-L. Trautmann, “New lower bounds for constant dimension codes”, 2013 IEEE International Symposium on Information Theory 514 (2013) arXiv:1301.5961 DOI

  8. [8]

    N. Silberstein and A.-L. Trautmann, “Subspace Codes based on Graph Matchings, Ferrers Diagrams and Pending Blocks”, (2015) arXiv:1404.6723

  9. [9]

    F.-W. Fu, X. Gao, S. Mesnager, and G. Wang, “Optimal Ferrers Diagram Rank-Metric Codes: New Constructions, Diagram Combinations, and Applications to Constant-Dimension Subspace Codes”, (2026) arXiv:2609.24239

  10. [10]

    D. Heinlein, M. Kiermaier, S. Kurz, and A. Wassermann, “Tables of subspace codes”, (2019) arXiv:1601.02864

  11. [11]

    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) arXiv:0711.0708 DOI

  12. [12]

    F. R. Kschischang, “Network Codes”, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021), pp. 685-714 DOI

  13. [13]

    D. Yu. Nogin, “Codes associated to Grassmannians”, Arithmetic, Geometry, and Coding Theory DOI

  14. [14]

    V. Lakshmibai and J. Brown, The Grassmannian Variety (Springer New York, 2015) DOI

  15. [15]

    C. Bachoc, “Semidefinite programming, harmonic analysis and coding theory”, (2010) arXiv:0909.4767

  16. [16]

    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

  17. [17]

    J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI

Page edit log

Your contribution is welcome!

on github.com (edit & pull request)

— see instructions

Zoo Code ID: finite_grassmann

Cite as:
“Constant-dimension code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2026. https://errorcorrectionzoo.org/c/finite_grassmann, arXiv:2606.11484
BibTeX:
@incollection{eczoo_finite_grassmann,
title={Constant-dimension code},
booktitle={The Error Correction Zoo},
year={2026},
editor={Albert, Victor V. and Faist, Philippe},
eprint={2606.11484},
doi={10.48550/arXiv.2606.11484},
url={https://errorcorrectionzoo.org/c/finite_grassmann}
}
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/finite_grassmann

Cite as:

“Constant-dimension code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2026. https://errorcorrectionzoo.org/c/finite_grassmann, arXiv:2606.11484

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/matrices/subspace/finite_grassmann.yml.