[Jump to code hierarchy]

Griesmer code [1–3]

Description

A \(q\)-ary linear code whose parameters satisfy the Griesmer bound with equality.

A \([n,k,d]_q\) code is a Griesmer code if parameters \(n\), \(k\), \(d\), and \(q\) are such that the Griesmer bound \begin{align} n\geq\sum_{j=0}^{k-1}\left\lceil \frac{d}{q^{j}}\right\rceil ~,\tag*{$(1)$} \end{align}where \(\left\lceil x\right\rceil \) is the ceiling function, becomes an equality.

An \([n,2,d]_q\) code exists if and only if it is not excluded by the Griesmer bound. Every Griesmer code is generated by its minimum-weight codewords [4].

Cousins

  • Divisible code— If a \(p\)-ary Griesmer code with \(p\) prime is such that a power of \(p\) divides the distance, then the code is divisible by that power [5].
  • Anticode— Several anticode (e.g., [6,7]) and related [8] constructions saturate the Griesmer bound; see Refs. [9–11] for more details.
  • \([2^{2r}-1, 3r, 2^{2r-1} - 2^{r-1} ]\) Kasami code— Kasami codes satisfy the Griesmer bound for certain parameters [12].
  • Projective RM (PRM) code— PRM codes for \(r=1\) attain the Griesmer bound for all \(m\) [13].
  • Grassmannian evaluation code— The \([35,6,16]\) Grassmannian evaluation code, whose points lie on the Grassmannian \({\mathbb{G}(2,4)}\), attains the Griesmer bound [13].
  • Projective geometry code— Arcs corresponding to Griesmer codes are called Griesmer arcs [14; pg. 248]. There is a one-to-one correspondence between Griesmer codes and minihypers [15,16]; see [18][17; Sec. 14.2.4] for more details.
  • Galois-qudit CSS code— A quantum version of the Griesmer bound has been derived for Galois-qudit CSS codes [19] and Galois-qudit stabilizer codes [20].

Primary Hierarchy

Parents
Griesmer code
Children
First-order RM codes saturate the Griesmer bound [21; Thm. 1.9.18] since \(\sum_{i=0}^{m}\lceil 2^{m-1}/2^{i}\rceil = 2^m\).
The \([7,4,3]\) Hamming code saturates the Griesmer bound, since \(7=3+2+1+1\). Starting with the \([6,3,3]\) shortened Hamming code and applying the \((u|u+v)\) construction recursively using the repetition code yields a family of \([3\cdot 2^m,m+2,3\cdot 2^{m-1}]\) codes for \(m\geq1\) that saturate the Griesmer bound [9; pg. 90].
The Griesmer bound implies the Singleton bound, and MDS codes attain both. For \(k\geq 2\), this follows because MDS codes have distance \(d\leq q\) [11; Ch. 11].
Simplex codes saturate the Griesmer bound ( [9], Exer. 5.1.11).

References

  1. [1]

    J. H. Griesmer, “A Bound for Error-Correcting Codes”, IBM Journal of Research and Development 4, 532 (1960) DOI

  2. [2]

    G. Solomon and J. J. Stiffler, “Algebraically punctured cyclic codes”, Information and Control 8, 170 (1965) DOI

  3. [3]

    R. R. Varshamov, “On the general theory of linear coding”, PhD thesis, Moscow State University, 1959

  4. [4]

    S. Dodunekov, “Optimal linear codes”, PhD thesis, Sofia, 1985

  5. [5]

    H. N. Ward, “Divisibility of Codes Meeting the Griesmer Bound”, Journal of Combinatorial Theory, Series A 83, 79 (1998) DOI

  6. [6]

    B. I. Belov, V. N. Logachev, and V. P. Sandimirov, “Construction of a Class of Linear Binary Codes Achieving the Varshamov-Griesmer Bound”, Problemy Peredachi Informatsii 10(3), 36–44 (1974); Problems of Information Transmission 10(3), 211–217 (1974)

  7. [7]

    R. Hill, “Optimal Linear Codes” in: C. Mitchell (Ed.) Cryptography and Coding, (1992): 75-104

  8. [8]

    B. I. Belov, “A conjecture on the Griesmer bound”, Optimization Methods and Their Applications,(Russian), Sibirsk. Energet. Inst. Sibirsk. Otdel. Akad. Nauk SSSR, Irkutsk 182, 100-106 (1974)

  9. [9]

    J. Bierbrauer, Introduction to Coding Theory (Chapman and Hall/CRC, 2016) DOI

  10. [10]

    I. N. Landjev, “Linear codes over finite fields and finite projective geometries”, Discrete Mathematics 213, 211 (2000) DOI

  11. [11]

    F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes (Elsevier, 1977)

  12. [12]

    T. Helleseth and P. Vijay Kumar, “The weight hierarchy of the Kasami codes”, Discrete Mathematics 145, 133 (1995) DOI

  13. [13]

    J. B. Little, “Algebraic geometry codes from higher dimensional varieties”, (2008) arXiv:0802.2349

  14. [14]

    I. N. Landjev, “The Geometric Approach to Linear Codes”, Developments in Mathematics 247 (2001) DOI

  15. [15]

    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

  16. [16]

    N. Hamada, Characterization of minihypers in a finite projective geometry and its applications to error-correcting codes, Bull. Osaka Women’s University 24 (1987), 1-24

  17. [17]

    L. Storme, “Coding Theory and Galois Geometries”, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021), pp. 285-310 DOI

  18. [18]

    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

  19. [19]

    P. Sarvepalli and A. Klappenecker, “Degenerate quantum codes and the quantum Hamming bound”, Physical Review A 81, (2010) arXiv:0812.2674 DOI

  20. [20]

    J. S. Gundersen, R. B. Christensen, M. Grassl, P. Popovski, and R. Wisniewski, “Puncturing Quantum Stabilizer Codes”, IEEE Journal on Selected Areas in Information Theory 6, 74 (2025) DOI

  21. [21]

    W. C. Huffman, J.-L. Kim, and P. Solé, “Basics of coding theory”, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021), pp. 3-44 DOI

Page edit log

Your contribution is welcome!

on github.com (edit & pull request)

— see instructions

Zoo Code ID: griesmer

Cite as:
“Griesmer code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2026. https://errorcorrectionzoo.org/c/griesmer, arXiv:2606.11484
BibTeX:
@incollection{eczoo_griesmer,
title={Griesmer 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/griesmer}
}
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/griesmer

Cite as:

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

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