Griesmer code

Griesmer code[1–3]

Description

A type of \(q\)-ary 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.
Binary BCH code— The \([15,5,7]\) BCH code extended with a parity check saturates the Griesmer bound [9; pg. 157].
\([2^{2r}-1, 3r, 2^{2r-1} - 2^{r-1} ]\) Kasami code— Kasami codes satisfy the Griesmer bound for certain parameters [12].
\([7,4,3]\) Hamming code— 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 \([2^m,m+1,2^{m-1}]\) codes for \(m\geq1\) that saturate the Griesmer bound [9; pg. 90].
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].

Member of code lists

Primary Hierarchy

Classical Domain

Galois-field Kingdom

\(q\)-ary codeECC

Additive \(q\)-ary codeECC

Linear \(q\)-ary codeECC

Maximum distance separable (MDS) codeOA LRC Distributed-storage Universally optimal ECC \(t\)-design

Parents

Maximum distance separable (MDS) code

Singleton bound implies the Griesmer bound.

Griesmer code

Children

Denniston code

\(q\)-ary simplex code

Simplex codes saturate the Griesmer bound ([9], Exer. 5.1.11).

References

[1]: J. H. Griesmer, “A Bound for Error-Correcting Codes”, IBM Journal of Research and Development 4, 532 (1960) DOI
[2]: G. Solomon and J. J. Stiffler, “Algebraically punctured cyclic codes”, Information and Control 8, 170 (1965) DOI
[3]: R. R. Varshamov, “On the general theory of linear coding”, PhD thesis, Moscow State University, 1959.
[4]: S. Dodunekov, Optimal linear codes, PhD thesis, Sofia, 1985.
[5]: H. N. Ward, “Divisibility of Codes Meeting the Griesmer Bound”, Journal of Combinatorial Theory, Series A 83, 79 (1998) DOI
[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 (1974), 36–44; Problems of Information Transmission, 10:3 (1974), 211–217.
[7]: R. Hill, “Optimal Linear Codes in: C. Mitchell (Ed.) Cryptography and Coding.” (1992): 75-104.
[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 (1974): 100-106.
[9]: J. Bierbrauer, Introduction to Coding Theory (Chapman and Hall/CRC, 2016) DOI
[10]: I. N. Landjev, “Linear codes over finite fields and finite projective geometries”, Discrete Mathematics 213, 211 (2000) DOI
[11]: F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
[12]: T. Helleseth and P. Vijay Kumar, “The weight hierarchy of the Kasami codes”, Discrete Mathematics 145, 133 (1995) DOI
[13]: J. B. Little, “Algebraic geometry codes from higher dimensional varieties”, (2008) arXiv:0802.2349
[14]: I. N. Landjev, “The Geometric Approach to Linear Codes”, Developments in Mathematics 247 (2001) DOI
[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]: 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.
[17]: L. Storme, “Coding Theory and Galois Geometries.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[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]: P. Sarvepalli and A. Klappenecker, “Degenerate quantum codes and the quantum Hamming bound”, Physical Review A 81, (2010) arXiv:0812.2674 DOI
[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

Page edit log

Victor V. Albert (2022-08-08) — most recent

Cite as:

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

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